Speeding Up Search-Based Motion Planning using Expansion Delay Heuristics
| Learning Heuristics Motion Planning Heuristic Search |
PaperID: 353
pdf
poster
|
| Suboptimal search algorithms are a popular way to find solutions to planning problems faster by trading off solution optimality for search time. This is often achieved with the help of inadmissible heuristics. Prior work has explored ways to learn such inadmissible heuristics. However, it has focused on learning the heuristic value as an estimate of the cost to reach a goal. In this paper, we present a different approach that computes inadmissible heuristics by learning Expansion Delay for transitions in the state space. Expansion Delay is defined as the number of states expanded during the search between two consecutive states. Expansion Delay can be used as a measure of the depth of local minima regions i.e., regions where the heuristic(s) are weakly correlated with the true cost-to-goal (Vats, Narayanan and Likhachev 2017). Our key idea is to learn this measure in order to guide the search such that it reduces the total Expansion delay for reaching the goal and hence, avoid local minima regions in the state space. We analyze our method on 3D (x, y, theta) planning and Humanoid footstep planning. We find that the heuristics computed using our technique result in finding feasible plans faster. | |
Session 6: Search
Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge
Authors: Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Daniel Harabor, Peter J. Stuckey, Hang Ma and Sven Koenig
Keywords:
Multi-agent path findingRail planningRobust planning under uncertainty
A Competitive Analysis of Online Multi-Agent Path Finding
Authors: Hang Ma
Keywords:
multi-agent path findingcompetitive analysisonline algorithms
Conflict-Based Increasing Cost Search
Authors: Thayne T. Walker, Nathan Sturtevant, Han Zhang, Jiaoyang Li, Sven Koenig, Ariel Felner and T. K. Satish Kumar
Keywords:
multi-agentsearchheuristic searchplanning
Speeding Up Search-Based Motion Planning using Expansion Delay Heuristics
Authors: Jasmeet Kaur, Ishani Chatterjee and Maxim Likhachev
Keywords:
Learning HeuristicsMotion PlanningHeuristic Search