Stefan Zickler

Physics-Based Robot Motion Planning in Dynamic Multi-Body Environments Degree Type: Ph.D. in Computer Science
Advisor(s): Manuela Veloso
Graduated: May 2010

Abstract:

Traditional motion planning focuses on the problem of safely navigating a robot through an obstacle-ridden environment. In this thesis, we address the question of how to perform robot motion planning in complex domains, with goals that go beyond collision-free navigation. Specifically, we are interested in problems that impose challenging constraints on the intermediate states of a plan, and problems that require the purposeful manipulation of non-actuated bodies, in environments that contain multiple, physically interacting bodies with varying degrees of controllability and predictability. Examples of such domains include physical games, such as robot soccer, where the controlled robot has to deliver the ball into the opponent's goal. For these domains, navigation only constitutes a small part of the overall planning problem. Additional planning challenges include accurately modeling and exploiting the dynamic interactions with other non-actuated bodies (e.g., dribbling a ball), and the problem of predicting and avoiding foreign-controlled bodies (e.g., opponent robots).

To plan in such domains, this thesis introduces physics-based planning methods, relying on rich models that aim to reflect the detailed dynamics of the real physical world. We introduce non-deterministic Skills and Tactics as an intelligent action sampling model for effectively reducing the size of the searchable action space. We contribute two efficient Tactics-driven planning algorithms, BK-RRT and BK-BGT, and we evaluate their performance across several challenging domains. We contribute a physics model parameter optimization method for increasing the planner's physical prediction accuracy, resulting in significantly improved real-world execution success rates. Additionally, we contribute Variable Level-Of-Detail (VLOD) planning, a method for reducing overall planning time in uncertain multi-body execution environments.

Besides relying on an extensive simulated testbed, we apply and evaluate our planning approaches in two challenging real-world robot domains. We contribute the robot minigolf domain, where a robot uses physics-based planning methods to solve freely configurable minigolf-like courses, e.g., by purposefully bouncing a ball off from obstacles. We furthermore contribute a robot soccer attacker behavior that uses physics-based planning to out-dribble opponents, which has been successfully tested as part of the "CMDragons" robot soccer Small Size League team at the RoboCup world cup in 2009.

Thesis Committee:
Manuela M Veloso (Chair)
Jessica K. Hodgins
James J. Kuffner Jr.
John E. Laird (University of Michigan)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Robot motion planning, physics-based planning, uncertainty, replanning, robot soccer, robot minigolf