Workshop on Algorithmic Motion Planning for Autonomous Robots in Challenging Environments by Lydia Kavraki
October 28, 2007 held during IROS 2007
Workshop Homepage
Workshop Program
Workshop Abstract
State-of-the-art algorithms for motion planning, such as sampling-based methods, have become very effective in solving challenging puzzles in simulation and they have shown promising results in fields as diverse as computational biology. Although motion planning is used in some challenging applications, such as robot soccer; in general, the application of algorithmic motion planning controlling real robotic systems, such as autonomous vehicles and humanoid robots, has been limited.
This inconsistency may be attributed to the fact that autonomous robots require a frame rate of operation that was too high for motion planners until recently. It can also be attributed to the fact that there are still many challenges to address when designing planning algorithms for realistic robotic systems. These challenges may arise from the dynamic nature or the partial observability of environments, the presence of differential constraints, uncertainty in sensing and action execution, or the presence of other mobile vehicles with unknown dynamics.
The aim of this workshop is to provide a forum for discussion on how motion planning solutions can provide a way to control autonomous robotic systems and what are the directions for future research with this goal in mind. These directions include online replanning where planners operate in a close-loop interleaved with sensing, estimation and execution, feedback planning, planning under differential constraints and planning under uncertainty.
Short Summary of the Workshop
Lydia Kavraki opened the workshop by describing the motivation and the objective of the workshop: to bring together researchers from different areas, such as algorithmic planning and mobile robotics, to investigate together how to deal with the problem of planning for real autonomous systems. She emphasized the research challenges that have to be addressed in this process, such as dealing with system dynamics, partial observability, sensing uncertainty and adversarial scenarios.
The first session of the workshop included two presentations on planning concepts and tools. Oliver Brock talked about exploitation and exploration in planning - a theme that has intrigued researchers for years. He described an algorithm that attempts to balance exploitation and exploration in problems that involve manipulators. Sven Koenig continued the workshop by discussing cell-based and graph-based motion planners. He described the advantages and disadvantages of both and ways to mitigate their disadvantages. He closed his talk by presenting a method that combines the parti-game algorithm, an example of a cell-based approach, with RRT, a graph-based planner.
The workshop continued with two talks for motivating applications of motion planning on real problems. The first talk was by Stefan Zickler, from Manuela Veloso's group, describing algorithms and techniques used in controlling the group's robots in the Robocup, the international robot soccer competition. Important characteristics of this domain are the strict real-time limitations and the necessity to be reactive to dynamic changes in the environment. Jean-Paul Laumond focused on the challenges of planning for anthropomorphic systems, both animated and real, as well as methods for these problems. These systems are highly-redundant, which causes planners to return unsatisfying paths. Moreover, the dynamics become an issue when dealing with stability but impose computational challenges, that the presenter suggested are better to be avoided as long as the planning problem can be solved.
The second session started with a talk by James Kuffner who presented planning experiments with humanoid robots. The focus was on problems where replanning is required so that the robot to be adaptive and be able to avoid dynamic obstacles. The last talk before the lunch break was by Kostas Bekris, from Lydia Kavraki's group, who described approaches on how to deal with the computational and safety challenges that arise when planning in real-time for systems with dynamic constraints. The focus was on the case of multiple communicating vehicles that have to coordinate their motion to solve a task safely.
The third session focused on problems with multiple agents. Dinesh Manocha described work on multi-agent and crowd simulation based on three tools: multi-agent navigation graphs; physically-based deforming roadmaps; and reciprocal velocity obstacles for multi-agent collision avoidance. The focus was on pushing the number of agents to high values, often necessary to simulate crowds. Nancy Amato emphasized the importance of behaviors in the selection of the motion that each agent follows using only local information from its environment and showed how motion planning techniques can be integrated with behavior-based reactive approaches to produce more sophisticated group behaviors.
The next talk, by Jing Xiao, brought the discussion to the issues that arise when planning for multiple mobile manipulators in dynamic environments. She described a general framework for planning in these scenarios and showed examples of coordinating manipulators that achieve a common task objective by planning in real-time. Manuela Veloso closed the third session on multi-agent motion planning by focusing on the challenges of planning for real robots, such as sensing/motion uncertainty and partial observability and on higher-level motion coordination issues. She used an example from the Robocup competition to emphasize an important challenge. Different members of a robotic team have simultaneously different models of the world and they have to resolve these disagreements in order to solve a common task.
The last session of the workshop included by two talks on planning under uncertainty. Tomas Lozano-Perez described work with Leslie Kaelbling on using the framework of Partially Observable Markov Decision Processes to solve manipulation problems under uncertainty. This work shows how to approach such difficult problems in order to achieve tractable formulations that can be used to solve tasks with a real manipulator. Then Ron Alterovitz followed with his work together with Ken Goldberg and Thierry Simeon on combining the framework of the Probabilistic Roadmap Method and of Markov Decision Processes in order to solve problems with motion uncertainty. Dynamic programming is used in this process in order to compute stochastically optimal plans.
The next talk by Hadas Kress-Gazit, from George Pappas' group, moved in the direction of how to translate a definition of a task to the actual sequence of controls that have to be executed to satisfy the specification. Multiple tools are needed in this process and the presenter showed how formal logic and hybrid controllers can be combined to achieve this objective. Steve LaValle closed the last session by using the problem of inferring the location of moving agents from combinatorial data as an example for the framework of information spaces. He showed how the information space for this problem collapses to a bipartite graph where queries can be solved with a maximum flow algorithm.
He closed his talk by suggesting that many interesting problems in motion planning lie in the areas of real-time performance, feedback planning, coordination, kinodynamic constraints, and most importantly with sensor-related challenges.
The workshop finished after a short discussion between the participants about important directions for future research in motion planning. The discussion, which was led by Manuela Veloso and Lydia Kavraki, was lively and underlined the differences of the approaches of researchers on the algorithmic end of motion planning and those who actually try to have robots operating in changing environments. The need to define new algorithmic problems for the community to work on, as well as the need to address pressing issues in real-time performance, feedback planning, coordination, and sensor-related challenges were discussed.