Situation
FIT5222, Planning and Automated Reasoning. Up to 150 trains on a rail grid where every cell holds at most one train and rails are directional, so the moves available in a cell depend on the direction you entered it from. Each train has an expected arrival time and arriving late costs a penalty.
The evaluator injects a malfunction roughly every ten timesteps and calls back into a replan function. A stopped train blocks everything behind it, so the plan you start the episode with is obsolete almost immediately.
Task
Write the solver. The simulator, the scaffold and the test instances are course material and are not mine. Submissions were scored on a contest server against a fixed staff implementation across 56 held out instances.
The thing that shapes every decision is the scoring function. A train that arrives 50 steps late adds 50 to the cost. A train that never arrives is charged the full episode limit, around 2,400, and picks up no lateness penalty because it never arrived. So one stranded train is worth roughly fifty late ones.
That rules out chasing optimal plans and rules in a fast per train search with a repair loop around it.
Action
A state is a cell, a heading and a timestep. Position alone is not a state, because a rail only connects to the rail you arrived on, so closing the search on the cell seals off a junction the first time it is touched and silently loses routes. Putting time in the state also makes g equal the timestep, so there is no separate cost bookkeeping to get wrong.
Distance to goal comes from a table rather than from arithmetic. Manhattan distance is admissible but weak on a rail map, because rails do not run in straight lines. One backward breadth first search from the goal over reversed transitions gives the exact rail distance from every state. That took Q2 from 966 seconds to 124 on the same instances with identical output.
Trains are planned one at a time, each around the paths already committed. Prioritised planning is incomplete and sensitive to ordering, so while any train is stranded the order gets reshuffled and replanned inside a fixed time budget. When a malfunction fires, only the blocked trains are replanned rather than the whole fleet.
Failing searches are capped. An A* search that cannot find a path will happily expand millions of time expanded states and take the process down with it. Capping expansions turned an out of memory kill on the server into a clean failure, and cut a local run from 1,512 seconds to 160 with byte identical output.
Result
Q1 scored 15 out of 15, Q2 25 out of 25, and Q3 50.22 out of 60. On Q3 that is a final SIC of 463,546 with 2,827 of 2,832 trains delivered, where SIC is the sum of individual costs and lower is better. The leading submissions came in roughly 10% ahead, about 32,000 SIC and five trains.
Two bugs were worth 505 trains between them, and neither was visible in the score. The leaderboard gives you one number and never tells you why, so the run logs count trains home, plan time and replan calls per instance separately. Replan calls was the measurement that cracked both.
The first: during repair the solver read each train’s position from the path it was supposed to be following rather than from where the simulator said it actually was. After a malfunction those two disagree. Reading position from the simulator brought 409 more trains home.
The second: a train that had arrived was still physically sitting on its goal cell, but its recorded path had ended, so every other train’s collision check read that cell as free, routed through it, collided and triggered another repair. On some instances that was 2,300 replans in an episode where 20 would have been plenty. Padding a finished train’s path so it stays occupied took replans to around 20 and brought 96 more trains home.
Two changes made the plan measurably better and the result measurably worse, and those were more useful than most of what worked. Running the order search on every instance rather than only when a train was stranded improved plan quality almost everywhere, and came out 21% worse with 41 fewer trains home. Ordering trains by slack, tightest deadline first, improved plan quality again and came out 9.3% worse.
The reason is the same both times. A tighter plan is a plan with no slack in it, and slack is what absorbs a breakdown. With a malfunction every ten timesteps, the schedule that looks best on paper is the one that shatters first. The stranding gate I had written as a speed guard was doing robustness work by accident, and the only way to see that was to measure the finished episode rather than the plan.
Where it still breaks down: prioritised planning is incomplete, so if an early train parks across the only corridor no later train recovers and no amount of repair undoes it. The order search is local and settles into the first decent order it finds. Repair is greedy and one way, so an early malfunction on a busy instance sets the quality of everything after it.
The next move is to stop searching over orderings and start searching over subsets: release a handful of conflicting trains, replan them together, keep the result if the episode improves. That is large neighbourhood search, and it attacks the incompleteness rather than working around it. I would also change the test loop to inject malfunctions locally and score the finished episode instead of the plan, because both negative results above would have shown up in minutes rather than costing two full evaluation runs.
Published as a record of the approach rather than as something to reuse.