运动规划

Template:NoteTA 运动规划（Template:Lang-en）是一个过程，用来寻找从起始状态到目标状态的移动步骤。常需要在运动受到约束的条件下找到最优解。运动规划多用于机器人学。例如，一个清洁机器人在楼层里打扫，它不能撞墙，也不能从楼梯口掉下去。给定一个任务，运动規劃算法计算出一个动作序列，告诉机器人前进多少米，然后左转右转多少度。如果机器人要操作物品或者探测未知地形等等，运动规划就变得很复杂了。除了机器人学，运动规划在电脑游戏里也用来模拟人物或车辆的运动。

概念

机器人所在的世界（Template:Lang-en）

基本的运动规划问题是通过连续的动作从起始位形s到达目标位形g，并且过程中要避开障碍物。机器人和障碍物可以抽象为二维或三维的几何图形，动作则被表示为位形空间中的路径。

自由空间

将世界抽象为位形空间，灰色区域表示障碍物，白色区域为自由空间（$C_{free}$）。

如果机器人采用某个位形时不会碰到障碍物，那么这个位形属于自由位形空间，简称自由空间（英文写作$C_{free}$）。自由空间的补集即障碍空间。

测试一个位形是否属于自由空间，先用正向运动学确定机器人的轮廓，然后查看机器人是否与障碍物碰撞。

算法

低维度的运动规划问题可以用基于格点的算法求解，如A*算法。

外部連結

• "Open Robotics Automation Virtual Environment", -{R|http://openrave.org/}- Template:Wayback
• Jean-Claude Latombe talks about his work with robots and motion planning, 5 April 2000
• "Open Motion Planning Library (OMPL)", -{R|http://ompl.kavrakilab.org}- Template:Wayback
• "Motion Strategy Library", -{R|http://msl.cs.uiuc.edu/msl/}- Template:Wayback
• "Motion Planning Kit", -{R|https://ai.stanford.edu/~mitul/mpk}- Template:Wayback
• "Simox", -{R|http://simox.sourceforge.net}- Template:Wayback
• "Robot Motion Planning and Control", -{R|http://www.laas.fr/%7Ejpl/book.html}- Template:Wayback