Efficient Physics-Based Planning: Sampling Search via Non-Deterministic Tactics and Skills (ACM)
Motion planning for mobile agents, such as robots, acting in the physical world is a challenging task, which traditionally concerns safe obstacle avoidance. We are interested in physics-based planning beyond collision-free navigation goals, in which the agent also needs to achieve its goals, including purposefully manipulate non-actuated bodies, in environments that contain multiple physically interacting bodies with varying degrees of controllability. Physics-based planning is computationally hard due to the large number of continuous motion actions and to the difficulty in accurately modeling the rich interactions of such controlled, manipulatable, and uncontrolled, potentially adversarial, bodies. We contribute an efficient physics-based planning algorithm that uses the agent‘s high-level behaviors to reduce its motion action space. We first discuss the general physics-based planning problem. We then introduce Tactics and Skills as a model for infusing goal-driven, higher level behaviors into a randomized motion planner. We present a physics-based state and transition model that employs rigid body simulations to approximate real-world interbody-dynamics. We introduce and compare two variations of our tactics-driven, physics-based planning algorithm, namely Behavioral Kinodynamic Balanced Growth Trees and Behavioral Kinodynamic Rapidly-Exploring Random Trees. We tested our physics-based planners in a variety of rich domains and show results in simulated domains where the agent manipulates an object in a dynamic non-adversarial and adversarial environment, namely in a robot minigolf and robot soccer domain, respectively.
Paper available at ACM.