Robot Path and Motion Planning
Table of Contents
1. Path Planning 简介
机器人路径规划的基本目标是以最快速度移动到目的地,且不能接触到障碍物。
一般地,机器人路径规划可分为两个层次:一个是 “全局规划” ,它的任务是提前在地图中规划一个从起始位置到达目的位置的线路,例如可以使用 A*算法等;另一个是 “局部规划” ,其主要任务是避免运行过程中遇到的障碍物。如图 1 所示。
Figure 1: Robot Path Planning Classic Two-layered Architecture
参考:
Planning Algorithms, by Steven M. LaValle: http://planning.cs.uiuc.edu/
http://ais.informatik.uni-freiburg.de/teaching/ss15/robotics/slides/19-pathplanning.pdf
1.1. Path Planning VS. Motion Planning
Path Planning 和 Motion Planning 没有本质区别,有时也混用。不过,一般来说 Path Planning 主要用于无人车、无人机等领域;而 Motion Planning 主要用于机械臂。如,我们想要机器人帮我们抄个菜,这一般归为 Motion Planning 问题。
1.2. Open Motion Planning Library (OMPL)
Open Motion Planning Library (OMPL)是用 C++开发的一个著名的运动规划库。ROS 中的 Moveit!使用了 OMPL。
2. Configuration Space (C-space)
2.1. Configuration, C-space and Workspace
The configuration of a robot system is a complete specification of the position of every point of that system. The configuration space, or C-space, of the robot system is the space of all possible configurations of the system.
The number of degrees of freedom of a robot system is the dimension of the configuration space, or the minimum number of parameters needed to specify the configuration.
We sometimes refer to this ambient space as the workspace.
Usually a configuration is expressed as a vector of positions and orientations.
参考:Principles of Robot Motion - Theory, Algorithms, and Implementations, Chapter 3 - Configuration Space
2.2. Free Space and Obstacle Region
With
常常记
Figure 2: The basic motion planning problem is conceptually very simple using C-space ideas. The task is to find a path from
图片摘自:Planning Algorithms, by Steven M. LaValle, 4.3 Configuration Space Obstacles
2.3. Two General Approaches (Sampling-Based Planning and Combinatorial Planning)
求解路径规划问题,有两类方法:
Sampling-Based planning: Avoid the explicit construction of
Combinatorial planning: Characterizes
参考:
Planning Algorithms, by Steven M. LaValle, Chapter 5 Sampling-Based Motion Planning
Planning Algorithms, by Steven M. LaValle, Chapter 6 Combinatorial Motion Planning
3. Sampling-Based Motion Planning
参考:Planning Algorithms, by Steven M. LaValle, 5. Sampling-Based Motion Planning
3.1. Rapidly-exploring Random Tree (RRT)
3.2. Probabilistic road map (PRM)
4. Collision Avoidance
机器人避障是路径规划的重要组成部分,相关算法有很多,如:
- Bug algorithm
- Vector field histogram
- The bubble band technique
- Curvature velocity techniques
- Dynamic window approaches
- The Schlegel approach to obstacle avoidance
- The ASL approach
- Nearness diagram
- Gradient method
- Adding dynamic constraints
参考:Introduction to Autonomous Mobile Robots, by Roland Siegwart, Illah Reza Nourbakhsh, 6.2.2 Obstacle avoidance
4.1. Bug Algorithm
The Bug algorithm is perhaps the simplest obstacle avoidance algorithm one could imagine. The basic idea is to follow the contour of each obstacle in the robot’s way and thus circumnavigate it.
With Bug1, the robot fully circles the object first, then departs from the point with the shortest distance toward the goal. This approach is, of course, very inefficient but guarantees that the robot will reach any reachable goal.
With Bug2 the robot begins to follow the object’s contour, but departs immediately when it is able to move directly toward the goal. In general this improved Bug algorithm will have significantly shorter total robot travel.
Figure 3: Bug1 algorithm with H1, H2, hit points, and L1, L2, leave points
Figure 4: Bug2 algorithm with H1, H2, hit points, and L1, L2, leave points
4.2. Dynamic Window Approache
In robotics motion planning, the dynamic window approach is a real-time collision avoidance strategy for mobile robots developed by Dieter Fox, Wolfram Burgard, and Sebastian Thrun in 1997.
动态窗口法的主要思想是 在速度空间
参考:
作者原始论文:https://www.ri.cmu.edu/pub_files/pub1/fox_dieter_1997_1/fox_dieter_1997_1.pdf
机器人局部避障的动态窗口法(dynamic window approach): http://blog.csdn.net/heyijia0327/article/details/44983551
4.2.1. 动态窗口法的速度采样空间
下面介绍如何确定速度
(1) 为了在最大的减速度条件下,确保机器人能够在碰到障碍物之前停下来,其速度不能太快,必须有个限制。假设
上式中,
Figure 5: Determination of the distance
说明:上面结论容易由物理公式
(2) 由于电机性能限制,存在一个 动态窗口,在该窗口内的速度是机器人能实际达到的速度。 假设
上式中,
(3) 机器人自身有一个速度限制,设为
最后,机器人速度的采样空间可以这样表述:
其中,
Figure 6: 速度采样空间
4.2.2. 动态窗口法的评价函数
在速度空间
每一个采样速度都会有一个对应的预计轨迹。采用评价函数的方式给每个轨迹打分,分数最高的轨迹对应的速度就是我们的选择。原始论文中采用的评价函数为:
其中,
(1)
(2)
(3)
4.2.3. 动态窗口法的不足
使用动态窗口法的机器人有一个不足之处:Robot does not slow down early enough to enter the doorway.
Figure 7: Problems of Dynamic Window Approache
参考:http://ais.informatik.uni-freiburg.de/teaching/ss15/robotics/slides/19-pathplanning.pdf