Ph.D Thesis

Ph.D StudentManor Gil
SubjectAutonomous Mobile Robot Navigation with Velocity Constraints
DepartmentDepartment of Mechanical Engineering
Supervisor PROF. Elon Rimon
Full Thesis textFull thesis text - English Version


Navigation is an important aspect in mobile robotics. Recently, we see a trend in robotic systems leaving laboratories and clean rooms and moving to real world environments. At this point, it is critical to ensure the safety of the robotic system as well as the environment in which it travels. One of the most common approaches to this problem is modeling a configuration space of permitted positions and orientations of the robot, then searching for a free collision path in this space.

However, the problem of navigating a mobile robot between obstacles while taking into account the dynamic characteristics of the robot while satisfying some quality measure of the path, remains with no certain unique solution.

One quality measure for paths is their total travel time. Traveling with high speed imposes two main safety concerns that should be taken into account when planning the path. (1) A speed dependant safe braking constraint; (2) A turning radius constraint that prevents sliding affects or tipping over.  In this research we synthesize the speed dependant safety constraints and the geometric path selection into a single framework.

The first approach, suggests modeling an augmented configuration space for the robot with the parameters x, y and the robot's speed. The speed dependant safe braking constraint is modeled in this space and represented by towering columns whose interior coordinates are states of the robot which lead to an imminent collision with the surrounding obstacles. A cellular decomposition of this augmented space induces an adjacency graph along which an approximated time optimal path is computed in a highly efficient way in terms of computational time.

The second approach uses calculus of variations and applies convexity properties of these paths to compute the globally time optimal path in the environment. In this approach, basic optimal path segments are composed into a "speed graph" whose edges are time optimal path segments connecting each individual pair of nodes. A time optimal path candidate is then selected using a graph search algorithm. Next, convexity properties of these paths are used to smooth the optimal candidate and to derive the globally time optimal path in the environment.