A stochastic and adaptive motion planning methodology for autonomous mobile robots

grantor: University of TorontoThis dissertation presents a novel approach to mobile robot motion planning. It capitalizes on properties of Markov chains, harmonic functions, and the Boundary Integral Equation method to introduce a new two-level method of environment representation. This method attributes a probability value to each robot state (environment point) that will later be used in dealing with uncertainties in the planning stage. Unlike other methods of environment representation, no geometric approximation is carried out on the shape of boundaries and obstacles, and the introduced representation method can consider arbitrary-shaped geometries. The first level of environment representation, using Markov chains, leads to an adaptive and flexible way-point selection algorithm for large and structured environments. This algorithm develops a connected sequence of zones that the robot may visit in order to attain the goal state. At the second level, for navigation within each zone a collection of behaviors based on different harmonic-field representations of the environment are presented. These behaviors, which all use the hill-climbing method for global path planning produce a network of trajectories for the robot that lead it to the goal from any reachable point inside the environment. For dynamic path planning the hill-climbing method of path planning is reformulated and a novel approach is proposed, using non-holonomic constraints to model obstacles. This behavior can be used to revise trajectories both off and on-line to account for new obstacles. To address the issue of uncertainties in the environment representation a new stochastic reactive planner is developed in this work. First, an obstacle avoidance algorithm is introduced which utilizes a simple statistical tool to modify the robot heading. The change in the heading angle is optimized so that the new heading remains as close as possible to the desired one, and contact with the sensed obstacle is avoided. Second, a Markov decision making process is developed to select the robot's actual path in face of unmodeled (unexpected) obstacles. The decision making process is included in the planner for the selection of the robot's actual course, with the purpose of optimizing with respect to a measure of the risk of striking an obstacle along the path. The effectiveness of the presented motion planning methodology is demonstrated in both simulations and experiments using an RWI-B12 mobile robot.Ph.D