Artificial intelligence · Automated planning
Lightsout
An automated-planning study for solving Lightsout and comparing the cost of finding solutions with fewer moves.
My contribution
My colleague and I worked together on the code, experiments and report, without a fixed division of tasks.
- Planning with PDDL
- Comparing runtime and plan length
Modelling the problem
In the variant we studied, the board starts with every light off and the goal is to turn them all on. Each press toggles a cell and its orthogonal neighbours.
We modelled states and actions with PDDL and Unified Planning for Fast Downward. We then implemented a modified breadth-first search with a heuristic prioritising states with more lights on.
Fewer moves, more search time
The heuristic retains N successors at each expansion. Increasing N explores more alternatives but raises runtime. These are the documented results for the 5 × 5 test case:
| Method | Moves | Runtime |
|---|---|---|
| Fast Downward | 49 | 0.61 s |
| BFS · N = 2 | 25 | 0.99 s |
| BFS · N = 3 | 17 | 14.20 s |
| BFS · N = 4 | 15 | 58.95 s |
| BFS · N = 5 | 15 | 175.63 s |
What the experiment showed
With N = 2, the solver took 25 moves in under a second. With N = 4, it found a 15-move plan but took approximately 59 seconds. These are separate configurations: the largest reduction was not achieved at sub-second runtime.
Successor pruning limits the search. These results do not prove general optimality or that the algorithm outperforms Fast Downward on every problem. We worked jointly on both the implementation and the report.
Documented from the academic report and presentation. No public source repository is linked.