Motion planning for humanoid robot anticipating environmental changes

我们已经开发了一个新的运动规划框架使用的数学概念的一个空间，通过删除一个维度，以提高计算效率。平行空间是一个简化的空间，它是通过声明空间中的点是等价的，然后将它们组合在一起成为平行空间的一个点而创建的。这种简化是通过机器人嵌套的思想实现的，这种方法适用于任何机器人。对于一个机械臂，我们在原机械臂内嵌套一系列低维机械臂，每个低维机械臂都是通过去除机械臂的一个连杆来创建的。机器人的嵌套创建了一系列的约束空间，这些空间都嵌套在原配置空间内。我们随后开发了一种新的算法，称为约束空间路线图规划器（QMP），它能够利用约束空间。我们的计划是独特的，因为它使用简化，同时是完整的。完备性意味着我们将为规划问题找到一条路径，只要一条路径存在。我们的算法QMP首先将配置分解到它的等价空间。然后我们开始在最低维的平行空间上生长一个图，直到找到一条可行的路径。一旦找到了这样的路径，我们就开始在下一个平行空间上生长第二个图。两个图同时生长，直到在下一个连续空间上找到可行路径。这个过程一直持续到我们在配置空间本身上找到一条路径。

We have developed a new motion planning framework using the mathematical concept of a quotient-space, through removal of a dimension to improve the efficiency of computation. A quotient-space is a simplified space, which is created by declaring points in a space as being equivalent, and then grouping them together into a single point of the quotient-space. We realized this simplification through the idea of nesting robots in each other.Our approach is general to be applied to any robot. Fo a manipulator arm, we nest a series of lower-dimensional manipulator arms inside the original arm, whereby each lower-dimensional arm is created by removing a link of the arm. This nesting of robots creates a series of quotient-spaces, which are all nested inside the original configuration space.We have subsequently developed a new algorithm, called the quotient-space roadmap planner (QMP), which is able to exploit quotient-spaces. Our planner is unique in that it uses simplifications while being complete. Being complete means that we will find a path for a planning problem, whenever one exists.Our algorithm QMP works by first decomposing the configuration into its quotient-spaces. Then we start growing a graph on the lowest-dimensional quotient-space until we find a feasible path. Once such a path has been found, we start growing a second graph on the next quotient-space. Both graphs are simultaneously grown until a feasible path is found on the next quotient-space. This process is continued until we find a path on the configuration space itself.