Sub-Optimal Multi-Phase Path Planning: A Method for Solving Rubik's Revenge
Rubik's Revenge, a 4x4x4 variant of the Rubik's puzzles, remains to date as an unsolved puzzle. That is to say, we do not have a method or successful categorization to optimally solve every one of its approximately $7.401 \times 10^{45}$ possible configurations. Rubik's Cube, Rubik's Revenge's predecessor (3x3x3), with its approximately $4.33 \times 10^{19}$ possible configurations, has only recently been completely solved by Rokicki et. al, further finding that any configuration requires no more than 20 moves. With the sheer dimension of Rubik's Revenge and its total configuration space, a brute-force method of finding all optimal solutions would be in vain. Similar to the methods used by Rokicki et. al on Rubik's Cube, in this paper we develop a method for solving arbitrary configurations of Rubik's Revenge in phases, using a combination of a powerful algorithm known as IDA* and a useful definition of distance in the cube space. While time-series results were not successfully gathered, it will be shown that this method far outweighs current human-solving methods and can be used to determine loose upper bounds for the cube space. Discussion will suggest that this method can also be applied to other puzzles with the proper transformations.
Code (0)
등록된 구현이 없습니다.
Tasks
Rubik's CubeTime SeriesTime Series AnalysisSimilar Papers 제목 키워드 기반
SympOCnet: Solving optimal control problems with applications to high-dimensional multi-agent path planning problems
Solving high-dimensional optimal control problems in real-time is an important but challenging problem, with applications to multi-agent path planning problems, which have drawn increased attention given the growing popu…
GPUEmbodied AI in Mobile Robots: Coverage Path Planning with Large Language Models
In recent years, Large Language Models (LLMs) have demonstrated remarkable capabilities in understanding and solving mathematical problems, leading to advancements in various fields. We propose an LLM-embodied path plann…
Natural Language UnderstandingSolving the Constrained Random Disambiguation Path Problem via Lagrangian Relaxation and Graph Reduction
We study a resource-constrained variant of the Random Disambiguation Path (RDP) problem, a generalization of the Stochastic Obstacle Scene (SOS) problem, in which a navigating agent must reach a target in a spatial envir…
Optimal Integrated Task and Path Planning and Its Application to Multi-Robot Pickup and Delivery
We propose a generic multi-robot planning mechanism that combines an optimal task planner and an optimal path planner to provide a scalable solution for complex multi-robot planning problems. The Integrated planner, thro…
Task PlanningConditional Generative Adversarial Networks for Optimal Path Planning
Path planning plays an important role in autonomous robot systems. Effective understanding of the surrounding environment and efficient generation of optimal collision-free path are both critical parts for solving path p…