Obstacle avoidance for a mobile robot among moving obstacles. (volumes i and ii)

摘要

In this thesis we consider the problem of planning motions for a mobile robot in the presence of objects moving on unknown trajectories and with unknown velocities. The robot must follow a predefined path within a given tolerance and reach its destination by a given time without colliding with any object. Objects are represented by non-intersecting discs in the plane, and the robot by a point. The method we propose interleaves path planning with execution. A tentative path is planned using predictions of the objects' movements. While following the planned path the robot relies on sensors to track the actual movements of the objects. Whenever the actual movements deviate excessively from the predictions a new path is planned using updated predictions. We develop two systems. The first system uses simple heuristics to enable the robot to plan paths rapidly. This system is able to plan paths in both two and three dimensions. The second system uses a more theoretical approach. We prove that the path planner used by this system is guaranteed to find a solution for a large class of problems. In our analysis we take into account velocity constraints, and the time needed to process sensor data and plan motions. We also show that when our method of planning is interleaved with execution, under conditions, the system is guaranteed to terminate successfully.