Admissible Abstractions for Near-optimal Task and Motion Planning
Admissible Abstractions for Near-optimal Task and Motion Planning
复制标题
近乎最优的任务和运动规划的可接受抽象
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
N. Roy
中科院分区：
文献类型：
--
作者：
William Vega;N. Roy
我们定义了一个天使语义抽象的容许性条件，并证明了这些条件允许我们在保持找到最优运动计划的能力的同时加速规划。然后，我们推导了两个连续状态运动规划域的容许抽象。我们利用问题域的局部度量和拓扑性质提取了具体运动计划代价的上界和下界。这些上界和下界都是由问题域的局部度量和拓扑性质决定的边界指导搜索的计划，同时保持性能保证。我们表明，抽象可以显着降低搜索的复杂性相对于一个直接的运动规划器。使用我们的抽象，我们发现接近最优的运动规划规划问题涉及10^13个状态，而不使用单独的任务规划器。
We define an admissibility condition for abstractions expressed using angelic semantics and show that these conditions allow us to accelerate planning while preserving the ability to find the optimal motion plan. We then derive admissible abstractions for two motion planning domains with continuous state. We extract upper and lower bounds on the cost of concrete motion plans using local metric and topological properties of the problem domain. These bounds guide the search for a plan while maintaining performance guarantees. We show that abstraction can dramatically reduce the complexity of search relative to a direct motion planner. Using our abstractions, we find near-optimal motion plans in planning problems involving 10^13 states without using a separate task planner.