The ability to navigate in everyday environments is a fundamental and necessary skill for any autonomous mobile agent that is intended to work with human users. The presence of pedestrians and other dynamic objects, however, makes the environment inherently dynamic and uncertain. To navigate in such environments, an agent must reason about the near future and make an optimal decision at each time step so that it can move safely toward the goal. Furthermore, for any application intended to carry passengers, it also must be able to move smoothly and comfortably, and the robot behavior needs to be customizable to match the preference of the individual users. Despite decades of progress in the field of motion planning and control, this remains a difficult challenge with existing methods.

Specifically, we require robot navigation in dynamic and uncertain environments to be safe, comfortable, and customizable. For safety in dynamic and uncertain environments, our algorithm guarantees probabilistic safety, rather than trying to provide absolute collision avoidance which quickly becomes impossible in cluttered and crowded environments. That is, with our algorithm the robot will (i) continually try to minimize (to near zero) the potential cost of collision due to robot motion, (ii) avoid moving when it is already in a collision state, and (iii) try to maximize the progress toward the goal if and only if there exists trajectories that are likely to be feasible. Also, for comfort and customizability, we explicitly consider the quality of motion, but without affecting our probabilistic safety guarantee, so that the robot motion matches the preference of the individual users.

In this dissertation, we show that safe, comfortable, and customizable mobile robot navigation in dynamic and uncertain environments can be achieved via stochastic model predictive control. We view the problem of navigation in dynamic and uncertain environments as a continuous decision making process, where an agent with short-term predictive capability reasons about its situation and makes an informed decision at each time step.

The problem of robot navigation in dynamic and uncertain environments is formulated as an on-line, finite-horizon policy and trajectory optimization problem under uncertainty. With our formulation, planning and control becomes fully integrated, which allows direct optimization of the performance measure. Furthermore, with our approach the problem becomes easy to solve, which allows our algorithm to run in real time on a single core of a typical laptop with off-the-shelf optimization packages.

This depends on four specific technical contributions. We define our expected cost so that we can directly incorporate the time-varying uncertain constraints and the probability of violating those constraints into the cost function, which tends to create a smooth cost surface that is easy to optimize over. The dimensionality reduction of this problem critically depends on the policy and closed-loop trajectory parameterization based on a Lyapunov-based feedback control law, which we developed for graceful motion of differential wheeled mobile robots. The stability of this stochastic model predictive control critically depends on a non-holonomic distance function, which we define as a Control-Lyapunov function for unicycle-type vehicles. We also develop a motor and friction dynamics model of the robot for more accurate forward prediction.

We demonstrate that our method generates graceful (safe, smooth, comfortable, fast, and intuitive) and customizable robot behavior in physical environments with pedestrians in real time. The work presented in this thesis extends the state-of-the-art in analytic control of mobile robots, sampling-based optimal path planning, and stochastic model predictive control. We believe that this work is a significant step toward safe and reliable autonomous navigation that is acceptable to human users.