Robotic motion planning in a dynamic environment with moving obstacles
Tai-Jee Pan · 1991
This dissertation presents a new approach to solving the mobile robot motion planning problem in a dynamic environment with moving obstacles. This approach solves the problem in three main steps: obstacle representation, collision detection, and the search for the robot's motion among obstacles. Obstacles are assumed to be polygonal and are represented using time-varying half-planes. The formula for this representation is derived to include the translational and rotational motion of obstacles. For collision detection, traversability vector theory is developed to determine the intersection of points, segments, and polygons with respect to another polygon. To find the safe motion of the robot, a path and velocity decomposition method is adopted. In this method, the physical path to bypass static obstacles is planned first, and then, the robot's velocity along the path is determined so as to avoid collision with moving obstacles. Compared with previous work done in the same area, the proposed approach is more efficient as explained below. In path planning, a route map containing distance-efficient routes is generated for the path search. The route map, a graph of size O(N), is smaller in size than the visibility graph which is of $O(N\sp2)$, where N is the total number of obstacle vertices. Consequently, path search with route maps can be done more efficiently. The algorithms for collision detection are very simple. This simplicity has made velocity planning very efficient even when obstacles are moving with both translation and rotation. The presented approach is tested through computer simulations. The path planning algorithm is also implemented on the MARGE autonomous robot developed in the Robotics and Intelligent Systems Laboratory at North Carolina State University.