Multi-Resolution A*
This addresses motion planning efficiency for robotics by balancing maneuverability and computational cost, though it is incremental as it builds on existing weighted-A* methods.
The paper tackles the trade-off between resolution and search efficiency in heuristic-based motion planning by proposing Multi-Resolution A* (MRA*), which runs multiple weighted-A* searches at different resolutions simultaneously, resulting in bounded suboptimality and resolution completeness across 2D, 3D grid, and 7 DOF manipulation planning domains.
Heuristic search-based planning techniques are commonly used for motion planning on discretized spaces. The performance of these algorithms is heavily affected by the resolution at which the search space is discretized. Typically a fixed resolution is chosen for a given domain. While a finer resolution allows for better maneuverability, it significantly increases the size of the state space, and hence demands more search efforts. On the contrary, a coarser resolution gives a fast exploratory behavior but compromises on maneuverability and the completeness of the search. To effectively leverage the advantages of both high and low resolution discretizations, we propose Multi-Resolution A* (MRA*) algorithm, that runs multiple weighted-A*(WA*) searches having different resolution levels simultaneously and combines the strengths of all of them. In addition to these searches, MRA* uses one anchor search to control expansions from these searches. We show that MRA* is bounded suboptimal with respect to the anchor resolution search space and resolution complete. We performed experiments on several motion planning domains including 2D, 3D grid planning and 7 DOF manipulation planning and compared our approach with several search-based and sampling-based baselines.