运动规划

运动规划(也被称为导航问题或钢琴搬运工的问题)是机器人的一个术语,用于将期望的运动任务分解成离散的运动,以满足运动的限制,并可能优化运动的某些方面。

来源:Wikipedia
简介

运动规划(也被称为导航问题或钢琴搬运工的问题)是机器人的一个术语,用于将期望的运动任务分解成离散的运动,以满足运动的限制,并可能优化运动的某些方面。

例如,考虑在建筑物内的一个移动机器人导航到一个远距离的地点。它应该执行这个任务,同时躲避墙壁,避免掉下楼梯。运动规划算法将把这些任务描述为输入,并生成发送给机器人车轮的速度和转弯命令。运动规划算法可能会解决机器人在数量更多(例如,工业操纵器),更复杂(例如对物体的操控),不同的约束(例如,一辆只能向前推进的汽车),以及不确定性(例如,环境或机器人的不完美模型)条件下的任务。

运动规划在机器人学中有很多应用,如机器人的自主性、自动化和机器人CAD设计。在其他领域同样应用广泛,如动画角色、视频游戏人工智能、建筑设计、机器人手术和生物分子的研究。

[描述来源:Wikipedia;URL:https://en.wikipedia.org/wiki/Motion_planning]

发展历史

描述

对机器人运动规划的研究始于20世纪60年代。1978年Lozano Perez和Wesley引入构型空间的概念构造规划器。1979年,Reif证明了钢琴搬运工问题的运动规划是一个PSPACE-hard问题。

传统的运动规划算法有胞分法,势场法,路径图法等。这类算法的共同特点是在参数设置合适时,可以保证规划的完备性(如果存在一条成立的路径,则算法一定能够在有限时间内找到)。但这些算法在高维姿态空间和复杂环境中使用存在较多问题。

1987年,J.P.Laumond将机械系统中的非完备性引入到机器人运动规划中解决自动泊车问题。非完备运动规划成为一个研究热点。

为解决传统算法的缺陷,兴起了一系列基于采样的运动规划算法。此类方法通过避免在状态空间中显式的构造障碍物来提供大量的计算节省。虽然基于采样的运动规划算法是非完备的,但确实概率完备的,即这些规划算法不能返回解的概率随着样本数趋近无穷而指数级衰减到零。

基于采样的运动规划算法开始于1990年Barraquand和Latombe提出的RPP(Randomized Potential Planner)算法。1994年PRM(Probabilistic Road Maps)算法和1998年RRT(Rapidly-exploring Random Tree)算法的出现,掀起了对机器人运动规划研究的新热潮。这些算法适合于解决高自由度机器人在复杂环境下的运动规划问题。

主要事件

1978

Lozano Perez和Wesley引入构型空间的概念构造规划器

Lozanoperez, T., &amp; Wesley, M. A. (1979). An algorithm for planning collision-free paths among polyhedral obstacles. <i>Communications of The ACM</i>, 22(10), 560-570.

1979

Reif证明了钢琴搬运工问题的运动规划是一个PSPACE-hard问题

Reif, J. H. (1979). Complexity of the mover's problem and generalizations. <i>foundations of computer science</i>.

1985

胞分法

Brooks, R. A., &amp; Lozanoperez, T. (1985). A subdivision algorithm in configuration space for findpath with rotation. <i>systems man and cybernetics</i>, 15(2), 224-233.

1985

势场法

Khatib, O. (1985). Real-time obstacle avoidance for manipulators and mobile robots.<i>international conference on robotics and automation</i>.

1988

路径图法

Canny, J. (1988). The complexity of robot motion planning. <i>,</i> <i>13</i>, 27-32.

1987

J.P.Laumond将机械系统中的非完备性引入到机器人运动规划中解决自动泊车问题。非完备运动规划成为一个研究热点。

Laumond, J. P., Sekhavat, S., &amp; Lamiraux, F. (1998). Guidelines in nonholonomic motion planning for mobile robots. <i>,</i> <i>229</i>, 1-53.

1990

Barraquand和Latombe提出的RPP(Randomized Potential Planner)算法

Barraquand, J., &amp; Latombe, J. (1990). A Monte-Carlo algorithm for path planning with many degrees of freedom. <i>international conference on robotics and automation</i>.

1994

PRM(Probabilistic Road Maps)算法提出

Kavraki, L. E., &amp; Latombe, J. (1994). Randomized preprocessing of configuration for fast path planning. <i>international conference on robotics and automation</i>.

1998

RRT(Rapidly-exploring Random Tree)算法提出

Lavalle, S. M. (1998). Rapidly-exploring random trees: a new tool for path planning.<i>Algorithmic &amp; Computational Robotics New Directions</i>, 293—308.

发展分析

瓶颈

虽然基于采样的规划算法速度很快,但他们也有致命的缺点,那就是由随机采样引入的随机性。利用RRT和PRM算法进行运动规划,用户无法对规划结果进行预判,每次规划的结果都不一样,这就使得自动规划的机器人无法进入工业领域(极端追求稳定性)。

未来发展方向

目前规划领域也主要集中在对PRM和RRT的改进上,大家都想要尽可能解决这类算法的不确定性,甚至能实现一些优化目标。

Contributor: Han Hao

相关人物
肯·戈德堡
肯·戈德堡
既是一名艺术家、作家,也是一名科研工作者,研究领域包括机器人学、自动化。他在博士论文中提出定向(供给)多边形部件的算法并和他的学生研究出供给、固定、抓取和装配的新算法。他曾荣获美国国家科学基金会(National Science Foundation)青年研究学者奖、美国国家科学基金会总统教员奖金、约瑟夫·F·恩格尔佰格(Joseph F. Engelberger)机器人奖及IEEE的重大教育创新奖。
Martial Hebert
Martial Hebert
卡内基梅隆大学机器人研究所主任,其研究领域包括计算机视觉领域,特别是图像和视频数据的识别;3D数据的模型构建和对象识别;以及移动机器人和智能车辆的感知等。他带领的研究团队开发了从三维视觉信息和视频信息进行场景分析和物体识别的技术,并应用到无人驾驶汽车和移动机器人当中。在智能机器人领域,他的团队也开发了人体检测、识别、跟踪与预测等技术。
丹妮拉·露丝
丹妮拉·露丝
机器人专家,计算机科学和人工智能实验室主任,以及麻省理工学院电气工程和计算机科学系教授。她的研究兴趣包括机器人学、移动计算和可编程物质。
oussama Khatib
oussama Khatib
斯坦福大学机器人专家、计算机科学教授,IEEE Fellow,研究领域包括机器人运动规划和控制、人性化机器人设计、触觉交互和人体运动合成等领域。他的工作重点是使用物理动态模型开发控制机器人系统的理论、算法和技术。
简介
相关人物