Probabilistic roadmaps for path planning in high-dimensional configuration spaces
Probabilistic roadmaps for path planning in high-dimensional configuration spaces
复制标题
DOI：
10.1109/70.508439
复制
发表时间：
1996-08-01
期刊：
影响因子：
--
通讯作者：
Overmars, MH
中科院分区：
文献类型：
--
作者：
Kavraki, LE;Svestka, P;Overmars, MH
提出了一种针对静态工作空间中机器人的新运动计划方法，该方法分为两个阶段：学习阶段和查询阶段，在学习阶段，构建概率路线图并将其存储为图形，作为图形，其节点对应于无碰撞的节点配置且边缘对应于这些配置之间的可行路径，这些路径是使用简单而快速的本地计划者计算的，在查询阶段，任何给定的启动和目标配置机器人连接到路线图的两个节点；然后，将路线图搜索以连接这两个节点的路径，该方法是通用且易于实现的，它几乎可以应用于任何类型的自动机器人，它需要选择某些参数（例如，学习阶段的持续时间））价值观取决于场景，即机器人及其工作区，但是这些价值观相对容易选择，也可以通过调整方法的某些组件来实现提高效率（例如，本地规划师）对所考虑的机器人，在本文中，该方法适用于具有多个自由度的平面铰接机器人，实验结果表明，路径计划可以在当代工作站的一秒钟内完成（大致）到150 mips），在学习相对较短的时间后（几十秒）。
A new motion planning method for robots in static workspaces is presented, This method proceeds in two phases: a learning phase and a query phase, In the learning phase, a probabilistic roadmap is constructed and stored as a graph whose nodes correspond to collision-free configurations and whose edges correspond to feasible paths between these configurations, These paths are computed using a simple and fast local planner, In the query phase, any given start and goal configurations of the robot are connected to two nodes of the roadmap; the roadmap is then searched for a path joining these two nodes, The method is general and easy to implement, It can be applied to virtually any type of holonomic robot, It requires selecting certain parameters (e.g., the duration of the learning phase) whose values depend on the scene, that is the robot and its workspace, But these values turn out to be relatively easy to choose, Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the considered robots, In this paper the method is applied to planar articulated robots with many degrees of freedom, Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation (approximate to 150 MIPS), after learning for relatively short periods of time (a few dozen seconds).