On Solving the Rubik's Cube with Domain-Independent Planners Using Standard Representations
This work addresses AI researchers by making Rubik's Cube more accessible to standard planning tools, though it is incremental in comparing existing methods with a new representation.
The paper tackles the problem of solving Rubik's Cube using domain-independent planners by introducing the first PDDL representation, making it more accessible to standard tools. It compares performance across methods, finding that DeepCubeA solves all problems but only 78.5% optimally, while FastDownward with PDDL solves 56.50% problems with 79.64% optimal plans.
Rubik's Cube (RC) is a well-known and computationally challenging puzzle that has motivated AI researchers to explore efficient alternative representations and problem-solving methods. The ideal situation for planning here is that a problem be solved optimally and efficiently represented in a standard notation using a general-purpose solver and heuristics. The fastest solver today for RC is DeepCubeA with a custom representation, and another approach is with Scorpion planner with State-Action-Space+ (SAS+) representation. In this paper, we present the first RC representation in the popular PDDL language so that the domain becomes more accessible to PDDL planners, competitions, and knowledge engineering tools, and is more human-readable. We then bridge across existing approaches and compare performance. We find that in one comparable experiment, DeepCubeA (trained with 12 RC actions) solves all problems with varying complexities, albeit only 78.5% are optimal plans. For the same problem set, Scorpion with SAS+ representation and pattern database heuristics solves 61.50% problems optimally, while FastDownward with PDDL representation and FF heuristic solves 56.50% problems, out of which 79.64% of the plans generated were optimal. Our study provides valuable insights into the trade-offs between representational choice and plan optimality that can help researchers design future strategies for challenging domains combining general-purpose solving methods (planning, reinforcement learning), heuristics, and representations (standard or custom).