|
|
|
|
PLANNING IN HIGHER DIMENSIONS
Motion planning of a mobile robot is the process of determining a trajectory/path for the robot to follow, in order to reach a goal state. It is the process of generating the corresponding control inputs so that the robot reaches the destination state. By state, we mean the parameters that govern the robot's motion, for example, speed and heading. Furthermore, given an environment model in which the robot is to be placed, a path has to be planned so as to avoid any collisions with obstacles as well as boundaries. The problem is relatively simple if the robot is omni-directional. That is, if the robot can move in all possible directions, then finding a path (if one exists) is relatively trivial. However, most robots do not have the capability to move in arbitrary direction. This introduces constraints in the method of planning the path of a robot. A typical example is the parallel-car-parking routine, in which a car-like robot is supposed to park into a parking slot without colliding with any obstacles (other cars, etc.). Also, when robots have different degrees of freedom, and the environment is more complex than just a polygonal obstacle map in two dimensions, planning requires quite a lot of computational effort.
For car-like robots, performing a reverse maneuver requires coming to a halt first and then moving in the opposite direction. This implies that if a path from one state to another state requires it reverse its direction of motion too often, it takes much longer for the robot to reach the target state. Therefore, an algorithm based on A* search along with the heuristic that the path have the minimum number of reversals possible is required to obtain a good path. Another approach to determining a collision-free path in high dimensions is the use of Rapidly Exploring Random Trees due to Steve LaValle and J.J.Kuffner. In this approach, a tree data-structure is used to explore the state space in a random fashion. Random points are first generated in the state space. This is followed by determining a nearest neighbour node in the existing tree (initially consisting of the initial state only). Then the control input that takes this nearest-neighbour closest to the random state is determined. The new state thus obtained is added to the search tree (which is basically, a multiway, unordered search-tree). A typical search in 2-D euclidean space along with orientation for a car-like robot, using RR-Trees looks like this: -
|
|
Send mail to
akpandey@research.iiit.ac.in with
questions or comments about this web site.
|
