Abstract
We present a novel approach for planning and directing heterogeneous groups of virtual agents based on techniques from linear programming. Our method efficiently identifies the most promising paths in both time and space and provides an optimal distribution of the groups’ members over these paths such that their average traveling time is minimized. The computed space-time plan is combined with an agent-based steering method to handle collisions and generate the final motions of the agents. Our overall solution is applicable to a variety of virtual environment applications, such as computer games and crowd simulators. We highlight its potential on different scenarios and evaluate the results from our simulations using a number of quantitative quality metrics. In practice, our system runs at interactive rates and can solve complex planning problems involving one or multiple groups.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bayazit, O.B., Lien, J.M., Amato, N.M.: Better group behaviors in complex environments using global roadmaps. In: Artificial Life, pp. 362–370 (2003)
Fleischer, L., Skutella, M.: Quickest flows over time. SIAM J. on Computing 36(6), 1600–1630 (2007)
Ford Jr., L.R., Fulkerson, D.R.: A suggested computation for maximal multi-commodity network flows. Management Science, 97–101 (1958)
Geraerts, R.: Planning short paths with clearance using explicit corridors. In: IEEE Int. Conf. on Robotics and Automation, pp. 1997–2004 (2010)
Geraerts, R., Overmars, M.H.: The corridor map method: Real-time high-quality path planning. In: IEEE Int. Conf. on Robotics and Automation, pp. 1023–1028 (2007)
Guy, S.J., Chhugani, J., Curtis, S., Pradeep, D., Lin, M., Manocha, D.: PLEdestrians: A least-effort approach to crowd simulation. In: Symp. on Computer Animation, pp. 119–128 (2010)
Helbing, D., Buzna, L., Werner, T.: Self-organized pedestrian crowd dynamics and design solutions. Traffic Forum 12 (2003)
Kamphuis, A., Overmars, M.H.: Finding paths for coherent groups using clearance. In: Symp. on Computer Animation, pp. 19–28 (2004)
Karamouzas, I.: Motion planning for human crowds: from individuals to groups of virtual characters. Ph.D. thesis, Utrecht University, the Netherlands (2012)
Karamouzas, I., Geraerts, R., Overmars, M.: Indicative routes for path planning and crowd simulation. In: Foundations of Digital Games, pp. 113–120 (2009)
Karamouzas, I., Heil, P., van Beek, P., Overmars, M.H.: A Predictive Collision Avoidance Model for Pedestrian Simulation. In: Egges, A., Geraerts, R., Overmars, M. (eds.) MIG 2009. LNCS, vol. 5884, pp. 41–52. Springer, Heidelberg (2009)
Karamouzas, I., Overmars, M.: Simulating and evaluating the local behavior of small pedestrian groups. IEEE Trans. Vis. Comput. Graph. 18(3), 394–406 (2012)
Kwon, T., Lee, K.H., Lee, J., Takahashi, S.: Group motion editing. ACM Trans. on Graphics 27(3), 1–8 (2008)
Lee, K.H., Choi, M.G., Hong, Q., Lee, J.: Group behavior from video: a data-driven approach to crowd simulation. In: Symp. on Computer Animation, pp. 109–118 (2007)
Li, T.Y., Chou, H.C.: Motion planning for a crowd of robots. In: IEEE Int. Conf. on Robotics and Automation, pp. 4215–4221 (2003)
Patil, S., van den Berg, J., Curtis, S., Lin, M.C., Manocha, D.: Directing crowd simulations using navigation fields. IEEE Trans. Vis. Comput. Graph. 17, 244–254 (2011)
Peng, J., Akella, S.: Coordinating multiple robots with kinodynamic constraints along specified paths. Int. J. of Robotics Research 24, 295–310 (2005)
Peters, C., Ennis, C.: Modeling groups of plausible virtual pedestrians. IEEE Computer Graphics and Applications 29(4), 54–63 (2009)
Reynolds, C.W.: Flocks, herds, and schools: A distributed behavioral model. Computer Graphics 21(4), 24–34 (1987)
Sánchez, G., Latombe, J.C.: Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. In: IEEE Int. Conf. on Robotics and Automation, pp. 2112–2119 (2002)
Silver, D.: Cooperative pathfinding. In: Artificial Intelligence and Interactive Digital Entertainment, pp. 117–122 (2005)
Simeon, T., Leroy, S., Laumond, J.P.: Path coordination for multiple mobile robots: A resolution-complete algorithm. IEEE Trans. on Robotics and Automation 18(1), 42–49 (2002)
Singh, S., Kapadia, M., Hewlett, B., Reinman, G., Faloutsos, P.: A modular framework for adaptive agent-based steering. In: ACM Symp. on I3D, pp. 141–150 (2011)
Sung, M., Kovar, L., Gleicher, M.: Fast and accurate goal-directed motion synthesis for crowds. In: Symp. on Computer Animation, pp. 291–300 (2005)
Treuille, A., Cooper, S., Popović, Z.: Continuum crowds. ACM Trans. on Graphics 25(3), 1160–1168 (2006)
van den Akker, M., Geraerts, R., Hoogeveen, H., Prins, C.: Path Planning for Groups Using Column Generation. In: Boulic, R., Chrysanthou, Y., Komura, T. (eds.) MIG 2010. LNCS, vol. 6459, pp. 94–105. Springer, Heidelberg (2010)
van den Berg, J., Guy, S.J., Lin, M.C., Manocha, D.: Reciprocal n-body collision avoidance. In: Int. Symp. on Robotics Research, pp. 3–19 (2009)
van den Berg, J., Lin, M., Manocha, D.: Reciprocal velocity obstacles for real-time multi-agent navigation. In: IEEE Int. Conf. on Robotics and Automation, pp. 1928–1935 (2008)
van den Berg, J., Overmars, M.H.: Prioritized motion planning for multiple robots. In: IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 2217–2222 (2005)
van den Berg, J., Overmars, M.H.: Roadmap-based motion planning in dynamic environments. IEEE Trans. on Robotics and Automation 21, 885–897 (2005)
van den Berg, J., Patil, S., Sewall, J., Manocha, D., Lin, M.C.: Interactive navigation of multiple agents in crowded environments. In: ACM Symp. on I3D, pp. 139–147 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karamouzas, I., Geraerts, R., van der Stappen, A.F. (2013). Space-Time Group Motion Planning. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds) Algorithmic Foundations of Robotics X. Springer Tracts in Advanced Robotics, vol 86. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36279-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-36279-8_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36278-1
Online ISBN: 978-3-642-36279-8
eBook Packages: EngineeringEngineering (R0)