运动学规划的复杂性

考虑以下问题：给定一个机器人系统，从起始位置和速度找到一条最短时间的轨迹到达目标位置和速度，同时避开障碍物并遵循速度和加速度的动态约束。考虑到牛顿力学下的点质量及其速度和加速度限制的简化案例。该点必须在2D或3D多面体障碍物中从起点飞行到目标。虽然这个问题的确切解尚不清楚，但给出了第一个经证明良好的近似算法，并显示其运行在多项式时间内。