The past decade has amply demonstrated the remarkable functionality that can be realized by learning complex input/output relationships. Algorithmically, one of the most important and opaque relationships is that between a problem's structure and an effective solution method. Here, we quantitatively connect the structure of a planning problem to the performance of a given sampling-based motion planning (SBMP) algorithm. We demonstrate that the geometric relationships of motion planning problems can be well captured by graph neural networks (GNNs) to predict SBMP runtime. By using an algorithm portfolio we show that GNN predictions of runtime on particular problems can be leveraged to accelerate online motion planning in both navigation and manipulation tasks. Moreover, the problem-to-runtime map can be inverted to identify subproblems easier to solve by particular SBMPs. We provide a motivating example of how this knowledge may be used to improve integrated task and motion planning on simulated examples. These successes rely on the relational structure of GNNs to capture scalable generalization from low-dimensional navigation tasks to high degree-of-freedom manipulation tasks in 3d environments.
翻译:过去十年充分展示了通过学习复杂的投入/产出关系可以实现的非凡功能。 举例来说,最重要的和不透明的关系之一是问题结构与有效解决方案方法之间的关系。 在这里,我们将规划问题的结构与特定基于抽样的动作规划(SBMP)算法的绩效进行定量联系。我们证明,移动规划问题的几何关系可以通过图形神经网络(GNNSs)很好地捕捉,以预测 SBMP运行时间。通过使用算法组合,我们显示,GNN对特定问题的运行时间预测可以被利用来加速导航和操作任务的在线行动规划。此外,问题到运行时间映射可以被颠倒,以找出特定SBMPs较易解决的子问题。我们提供了一个例子,说明如何利用这种知识改进模拟实例的综合任务和动作规划。这些成功取决于GNN的关联结构,以捕捉从低维导航任务到高度自由操纵任务在3个环境中的可扩展的一般性任务。