Simon Fraser University
Geodesics for Mobile Robots

Dr. Hamidreza Chitsaz
Thursday, March 19, 2009 at 2:00PM
Place: ASB 9705 Seminar Room

Planning optimal motions and devising optimal coordination strategies
are important and challenging fundamental problems in mobile robotics,
which have received significant attention in the last couple of
decades. Those problems can be reduced to shortest path, or
equivalently geodesic, problems in appropriate geometric settings.
Geodesic problems have been studied in two disciplines: 1) optimal
control theory, and 2) computational geometry. Optimal control theory
has historically disregarded obstacles in the environment, and
computational geometry does not consider dynamics of the robotic
system, various optimality criteria, or multi-objective optimality.
While each discipline has its own powerful tools to address some
geodesic problems, there is a large class of problems that cannot be
solved using existing algorithms and methods. We introduce a unified
approach that is inspired by main results in both disciplines. In this
talk, we demonstrate our technique, which combines the celebrated
Pontryagin Maximum Principle from optimal control theory with
visibility graph methods from computational geometry, by
characterizing geodesics for mobile robots (the differential drive)
and geodesics for a kinematic airplane. We consider the differential
drive because it is ubiquitous in mobile robotics. To obtain a
well-defined notion of shortest, the total amount of wheel rotation is
optimized. We analytically characterize minimum wheel-rotation
trajectories in the absence of obstacles, and identify 52 different
minimum wheel-rotation trajectories. Nonholonomic visibility graphs
are introduced to compute minimum wheel-rotation trajectories among
obstacles. A new kinematic airplane model is also introduced which is
a natural extension of the Dubins car. It extends the Dubins car with
an additional configuration variable for the altitude. To obtain a
notion of shortest, time is optimized.

Hamidreza Chitsaz is a Postdoctoral Fellow at the School of Computing
Science, Simon Fraser University. He has worked in the general area of
RNA-RNA interaction prediction and RNA folding under the supervision
of S. Cenk Sahinalp. Before joining Sahinalp’s group, Dr. Chitsaz
earned his Ph.D. in Computer Science from University of Illinois at
Urbana-Champaign in 2008. His doctoral thesis characterized geodesics
for mobile robots which is an important long-standing open area in
mobile robotics. He also won best engineering challenge award and
championships in international RoboCup (robot soccer world cup)
competitions. His research interests are generally mobile robotics and
applications of motion planning methods in computational biology.
Specifically, he is interested in computational subriemannian geometry
for mobile robots, motion planning for nonholonomic mobile mechanisms,
RNA-RNA interaction prediction, applying machine learning methods to
RNA structure prediction, and integrating gene regulation dynamics
into metabolic networks.