         
|
GRASP Lab Seminar 2003-2004
December 5, 11:00 AM, Levine Hall 315, hosted by Kostas Daniildis.
Steve LaValle
University of Illinios
Solving Mobile Robot Tasks without Localization and Mapping
Abstract: We have developed a dynamic data structure, called the Gap Navigation Graph (GNG), which is useful for solving tasks such as navigation and pursuit-evasion in an unknown planar environment. The guiding philosophy in this work is to avoid traditional problems such as complete map building and localization by constructing a minimal representation based entirely on critical events in on-line sensor measurements made by the robot. We present an algorithm for building the GNG in an unknown environment. The resulting data structure provides a sensor-feedback motion strategy that guides the robot between any two environment locations, and allows the search of static targets, even though there is no geometric map of the environment. In simply-connected environments, the resulting trajectory is optimal, and in multiply-connected environments, it is optimal within a homotopy class. We have also developed GNG-based algoritms that solve visibility-based pursuit-evasion problems. The GNG algorithms have been implemented, and the model was experimentally validated on a real mobile robot. Results are presented in which the robot builds the data structure on-line, and is able to use it without needing a global reference frame. Furthermore, simulation results are shown in which the robot performs optimal navigation, optimal searching for static objects, and on-line pursuit-evasion.
This is joint work with Benjamin Tovar, Luis Guilamo, and Rafael Murrieta.Biography: Steven M. LaValle received Ph.D. in Electrical Engineering from the University of Illinois at Urbana-Champaign in 1995.From 1995-1997 he was a post-doctoral researcher at Stanford, and an assistant professor at Iowa State from 1997-2001. He is an assistant professor in the Department of Computer Science and a part-time member of the Artificial Intelligence group.His fields of professional interest are robotics, artificial intelligence, algorithms, and computational biology.
