Leveraging experience in lazy search
Leveraging experience in lazy search
复制标题
利用惰性搜索的经验
作者：
M. Bhardwaj;Sanjiban Choudhury;Byron Boots;S. Srinivasa
懒惰图搜索算法在解决运动规划问题时效率很高，其中边评估是计算瓶颈。这些算法通过懒惰地计算最短的潜在可行路径、评估该路径上的边，并重复此过程直到找到可行路径来工作。边的选择顺序对于最小化边评估的总数至关重要：一个好的边选择器选择的边不仅可能是无效的，而且还能排除未来要考虑的路径。我们希望通过利用先前的经验来学习这样一个选择器。我们将这个问题表述为关于搜索问题状态的马尔可夫决策过程（MDP）。虽然解决这个大型MDP通常是棘手的，但我们表明我们可以计算出在训练期间能够解决MDP的神谕选择器。有了这些神谕，我们使用模仿学习来找到有效的策略。如果新的搜索问题与训练期间解决的问题足够相似，学习到的策略将选择一个良好的边评估顺序，并快速解决运动规划问题。我们在广泛的二维和七维问题上评估我们的算法，并表明学习到的选择器优于常用的基线启发式算法。我们还在贝叶斯框架下对懒惰搜索提供了一种新颖的理论分析，以及对我们基于模仿学习的运动规划方法的遗憾保证。
Lazy graph search algorithms are efficient at solving motion planning problems where edge evaluation is the computational bottleneck. These algorithms work by lazily computing the shortest potentially feasible path, evaluating edges along that path, and repeating until a feasible path is found. The order in which edges are selected is critical to minimizing the total number of edge evaluations: a good edge selector chooses edges that are not only likely to be invalid, but also eliminates future paths from consideration. We wish to learn such a selector by leveraging prior experience. We formulate this problem as a Markov Decision Process (MDP) on the state of the search problem. While solving this large MDP is generally intractable, we show that we can compute oracular selectors that can solve the MDP during training. With access to such oracles, we use imitation learning to find effective policies. If new search problems are sufficiently similar to problems solved during training, the learned policy will choose a good edge evaluation ordering and solve the motion planning problem quickly. We evaluate our algorithms on a wide range of 2D and 7D problems and show that the learned selector outperforms baseline commonly used heuristics. We further provide a novel theoretical analysis of lazy search in a Bayesian framework as well as regret guarantees on our imitation learning based approach to motion planning.
运动规划中惰性的可证明的优点
DOI：
--
发表时间：
2018
期刊：
ICAPS 2018
影响因子：
--
作者：
Haghtalab, N.;Mackenzie, S.;Procaccia, A. D.;Salzman, O.;Srinivasa, S.
通讯作者：
Srinivasa, S.
DOI：
--
发表时间：
2018-05
期刊：
ArXiv
影响因子：
--
作者：
Ching-An Cheng;Xinyan Yan;Nolan Wagener;Byron Boots
通讯作者：
Ching-An Cheng;Xinyan Yan;Nolan Wagener;Byron Boots
DOI：
10.1109/tnnls.2020.2978386
发表时间：
2021-01-01
影响因子：
10.4
作者：
Wu, Zonghan;Pan, Shirui;Yu, Philip S.
通讯作者：
Yu, Philip S.