Efficient physics-based planning: sampling search via non-deterministic tactics and skills

ABSTRACT

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.

REFERENCES

• 1: D. Baraff. Physically Based Modeling: Rigid Body Simulation. ACM SIGGRAPH Course Notes, 2001.
• 2: Sven Behnke , Raúl Rojas, A Hierarchy of Reactive Behaviors Handles Complexity, Balancing Reactivity and Social Deliberation in Multi-Agent Systems, From RoboCup to Real-World Applications (selected papers from the ECAI 2000 Workshop and additional contributions), p.125-126, January 2001
• 3: B. Browning, J. Bruce, M. Bowling, and M. Veloso. STP: Skills, Tactics and Plays for Multi-Robot Control in Adversarial Environments. IEEE Journal of Control and Systems Engineering, 219:33--52, 2005.
• 4: J. Bruce, M. Bowling, B. Browning, and M. Veloso. Multi-Robot Team Response to a Multi-Robot Opponent Team. In Proceedings of the IEEE International Conference on Robotics and Automation, 2003.
• 5: J. Bruce and M. Veloso. Safe Multi-Robot Navigation within Dynamics Constraints. Proceedings of the IEEE, 2006.
• 6: J. Bruce, S. Zickler, M. Licitra, and M. Veloso. CMDragons: Dynamic Passing and Strategy on a Champion Robot Soccer Team. In Proceedings of IEEE International Conference on Robotics and Automation, 2008.
• 7: Bruce, J. and Veloso, M. Real-Time Randomized Path Planning for Robot Navigation. Proceedings of IROS-2002, October 2002.
• 8: R. D'Andrea. The Cornell RoboCup Robot Soccer Team: 1999--2003. New York, NY: Birkhauser Boston, Inc, 2005., pages 793--804, 2005.
• 9: Manfred Lau , James J. Kuffner, Behavior planning for character animation, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073408]
• 10: T. Laue and T. Röfer. A Behavior Architecture for Autonomous Mobile Robots Based on Potential Fields. 8th RoboCup Symposium, 2004.
• 11: S. LaValle. Rapidly-exploring random trees: A new tool for path planning. Computer Science Dept, Iowa State University, Tech Report, 1998.
• 12: S. LaValle and J. Kuffner Jr. Randomized Kinodynamic Planning. The International Journal of Robotics Research, 20(5):378, 2001.
• 13: N. Melchior, J. Kwak, and R. Simmons. Particle RRT for Path Planning in very rough terrain. In NASA Science Technology Conference (NSTC), 2007.
• 14: L. Parker. ALLIANCE: an architecture for fault tolerant multirobot cooperation. IEEE Transactions on Robotics and Automation, 14(2):220--240, 1998.
• 15: N. Vahrenkamp, C. Scheurer, T. Asfour, J. Kuffner, and R. Dillmann. Adaptive motion planning for humanoid robots. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 2127--2132, 2008.
• 16: Katsu Yamane , James J. Kuffner , Jessica K. Hodgins, Synthesizing animations of human manipulation tasks, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 17: S. Zickler and M. Veloso. Playing Creative Soccer: Randomized Behavioral Kinodynamic Planning of Robot Tactics. In Proceedings of the RoboCup Symposium, 2008.
• 18: M. Zucker, J. Kuffner, and M. Branicky. Multipartite rrts for rapid replanning in dynamic environments. Proc. IEEE Int. Conf. on Robotics and Automation, pages 1603--1609, 2007.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

Keywords:
behavioral, control, kinodynamic, physics-based, planning, rigid body, robot, tactics