“Space-Time Planning With Parameterized Locomotion Controllers” by Levine, Lee, Koltun and Popovic

We present a technique for efficiently synthesizing animations for characters traversing complex dynamic environments. Our method uses parameterized locomotion controllers that correspond to specific motion skills, such as jumping or obstacle avoidance. The controllers are created from motion capture data with reinforcement learning. A space-time planner determines the sequence in which controllers must be executed to reach a goal location, and admits a variety of cost functions to produce paths that exhibit different behaviors. By planning in space and time, the planner can discover paths through dynamically changing environments, even if no path exists in any static snapshot. By using parameterized controllers able to handle navigational tasks, the planner can operate efficiently at a high level, leading to interactive replanning rates.

1. Arikan, O. and Forsyth, D. A. 2002. Interactive motion generation from examples. In ACM SIGGRAPH 2002 Papers. 483–490.
2. Choi, M. G., Lee, J., and Shin, S. Y. 2003. Planning biped locomotion using motion capture data and probabilistic roadmaps. ACM Trans. Graph. 22, 2, 182–203.
3. Coros, S., Beaudoin, P., and Van De Panne, M. 2009. Robust task-based control policies for physics-based characters. In ACM SIGGRAPH 2009 Papers. ACM Press.
4. Fiorini, P. and Shiller, Z. 1998. Motion planning in dynamic environments using velocity obstacles. Int. J. Robot. Res. 17, 7, 760–772.
5. Fraichard, T. 1999. Trajectory planning in a dynamic workspace: A ‘state-time space’ approach. Adv. Robot. 13.
6. Geraerts, R. and Overmars, M. 2004. Clearance based path optimization for motion planning. In Proceedings of the IEEE International Conference on Robotics and Automation. 2386–2392.
7. Geraerts, R. and Overmars, M. 2006. Creating high-quality roadmaps for motion planning in virtual environments. In Proceedings of the IEEE/RSJ’06 International Conference on Intelligent Robots and Systems. 4355–4361.
8. Hsu, D., Kindel, R., and Latombe, J.-C. 2002. Randomized kinody- namic motion planning with moving obstacles. Int. J. Robot. Res. 21, 3, 233–255.
9. Kamphuis, A., Mooijekind, M., Nieuwenhuisen, D., and Overmars, M. H. 2004. Automatic construction of roadmaps for path planning in games. In Proceedings of the International Conference on Computer Games. 285–292.
10. Kavraki, L., Latombe, J.-C., Svestka, P., and Overmars, M. 1994. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’94). 171.
11. Kovar, L., Gleicher, M., and Pighin, F. 2002. Motion graphs. In ACM SIGGRAPH 2002 Papers. 473–482.
12. Lau, M. and Kuffner, J. J. 2005. Behavior planning for character ani- mation. In Proceedings of the Conference of the Science Council of Asia (SCA’05). ACM Press, 271–280.
13. Lau, M. and Kuffner, J. J. 2006. Precomputed search trees: Planning for interactive goal-driven animation. In Proceedings of the Conference of the Science Council of Asia (SCA’06). Eurographics Association, 299–308.
14. Lee, J., Chai, J., Reitsma, P. S. A., Hodgins, J. K., and Pollard, N. S. 2002. Interactive control of avatars animated with human motion data. In ACM SIGGRAPH 2002 Papers.
15. Lee, Y., Lee, S. J., and Popovic, Z. 2009. Compact character controllers. In ACM SIGGRAPH Asia 2009 Papers 28, 5, 1–8.
16. Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., and Thrun, S. 2005. Anytime dynamic a*: An anytime, replanning algorithm. In Proceedings of the International Conference on Autonomous Planning and Scheduling (ICAPS’05).
17. Lo, W.-Y. and Zwicker, M. 2008. Real-Time planning for parameterized human motion. In Proceedings of the Conference of the Science Council of Asia (SCA’08). Eurographics Association, 29–38.
18. Mccann, J. and Pollard, N. 2007. Responsive characters from motion fragments. In ACM SIGGRAPH 2007 Papers. ACM Press, 6.
19. Safonova, A. and Hodgins, J. K. 2007. Construction and optimal search of interpolated motion graphs. In ACM SIGGRAPH 2007 Papers. ACM Press, 106.
20. Sud, A., Gayle, R., Andersen, E., Guy, S., Lin, M., and Manocha, D. 2007. Real-Time navigation of independent agents using adaptive roadmaps. In Proceedings of the Conference on Virtual Reality Software and Technology (VRST’07). ACM Press, 99–106.
21. Sung, M., Kovar, L., and Gleicher, M. 2005. Fast and accurate goal- directed motion synthesis for crowds. In Proceedings of the Conference of the Science Council of Asia (SCA’05). ACM Press, 291–300.
22. Treuille, A., Lee, Y., and Popović, Z. 2007. Near-Optimal character animation with continuous control. In ACM SIGGRAPH 2007 Papers. ACM Press.
23. van den Berg, J., Ferguson, D., and Kuffner, J. 2006. Anytime path planning and replanning in dynamic environments. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’06). 2366–2371.
24. van den Berg, J., Nieuwenhuisen, D., Jaillet, L., and Overmars, M. 2005. Creating robust roadmaps for motion planning in changing environments. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’05). 1053–1059.
25. van den Berg, J. and Overmars, M. 2005. Roadmap-Based motion planning in dynamic environments. IEEE Trans. Robot. 21, 5, 885–897.
26. van den Berg, J. and Overmars, M. 2006. Path planning in repetitive environments. In Proceedings of the International Conference on Methods and Models in Automation and Robotics (MMAR’06). 657–662.
27. van den Berg, J., Patil, S., Sewall, J., Manocha, D., and Lin, M. 2008. Interactive navigation of multiple agents in crowded environments. In Proceedings of the Symposium on Interactive 3D Graphics (I3D’08). ACM Press, 139–147.
28. Zucker, M., Kuffner, J. J., and Branicky, M. S. 2007. Multipartite RRTs for rapid replanning in dynamic environments. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’07). 1603–1609.