During the last decade, incremental sampling-based motion planning algorithms such as Rapidly-exploring Random Trees (RRTs) have been widely used for robotic applications. For example, the MIT entry to the 2007 DARPA Urban Challenge, which finished the competition in 4th place, used an RRT-like planning and control algorithm that performed flawlessly throughout the 60-mile race. While very effective, both in theory and in practice, at finding feasible paths for a dynamical systems through a complicated environment, RRTs have a number of limitations, among which (i) no characterization of the “quality” of the solution provided, and (ii) no ability to deal with tasks other than reaching a point while avoiding obstacles. The subject of the talk will be recent advances in the above directions. First, a negative result is given: it is proven that the cost of the best path in a RRT converges almost surely to a sub-optimal value, as the number of samples n increases. Based on the insight gained through the proof of this result, a new algorithm, called RRT* is proposed, which provably yields paths whose cost converges almost surely to the optimum. The computational overhead of RRT* is shown to be O (log n) with respect to the standard algorithm. Finally, we consider the problem of computing plans that satisfy a class of temporal logic specifications, describing, e.g., rules of the road or mission objectives. The proposed algorithms, generalizing sampling-based methods, incrementally build finite transition systems representing a discrete subset of dynamically feasible trajectories. At each iteration, local mu-calculus model-checking methods are used to establish whether the current transition system satisfies the specifications. Efficient sampling strategies are presented, ensuring the probabilistic completeness of the algorithms.
Emilio Frazzoli is an Associate Professor of Aeronautics and Astronautics with the Laboratory for Information and Decision Systems at the Massachusetts Institute of Technology. He received a Laurea degree in Aerospace Engineering from the University of Rome, “Sapienza”, Italy, in 1994, and a Ph. D. degree in Navigation and Control Systems from the Department of Aeronautics and Astronautics of the Massachusetts Institute of Technology, in 2001. Between 1994 and 1997 he worked as an officer in the Italian Navy, and as a spacecraft dynamics specialist for the European Space Agency Operations Centre (ESOC) in Darmstadt, Germany, and Telespazio, in Rome, Italy. From 2001 to 2004 he was an Assistant Professor of Aerospace Engineering at the University of Illinois at Urbana - Champaign. From 2004 to 2006 he was an Assistant Professor of Mechanical and Aerospace Engineering at the University of California, Los Angeles. He was the recipient of a NSF CAREER award in 2002. He is an Associate Fellow of the American Institute of Aeronautics and Astronautics and a Senior Member of the Institute for Electrical and Electronics Engineers. He is currently serving as an Associate Editor for the AIAA Journal of Guidance, Control, and Dynamics.
