Article

Finding paths for coherent groups using clearance

Authors:

M. H. OvermarsAuthors Info & Claims

SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation

Pages 19 - 28

https://doi.org/10.1145/1028523.1028526

Published: 27 August 2004 Publication History

Abstract

Virtual environment are often populated with moving units and the paths for these units should be planned. When multiple units need to exhibit coherent behavior in a cluttered environment, current techniques often fail, i.e. the resulting paths for the units in the group lack the coherence required. In this paper, we propose a novel approach to motion planning for coherent groups of units.

The method presented uses a path for a single unit, called the backbone path, which can be generated by any motion planner. This backbone path is extended to a corridor using the clearance along the path. The units can move freely inside this corridor. By limiting the width of this corridor, and the extent along the corridor where the units can move to, the approach guarantees coherence of the group.

Experiments show that the generated paths exhibit group coherence as required, like passing on the same side of obstacles and waiting for fellow group mates to catch up. Performance measurements show that the approach is capable of generating the paths in real-time. In our implementation, the method requires just a few percent of the processor time for groups consisting of up to 100 units.

Supplementary Material

JPG File (p19-kamphuis.jpg)

Download
23.05 KB

AVI File (p19-kamphuis.avi)

Supplemental video

Download
16.38 MB

References

[1]

{BH00} Balch T., Hybinette M.: Social potentials for scalable multi-robot formations. In IEEE International Conference on Robotics and Automation (ICRA '00) (April 2000), vol. 1, pp. 73--80.

[2]

{BLA04} Bayazit O., Lien J.-M., Amato N.: Better flocking behaviors using rule-based roadmaps. In Algorithmic Foundations of Robotics V, Springer Tracts in Advanced Robotics 7 (2004), Springer-Verlag Berlin Heidelberg, pp. 95--111.

[3]

{GO04} Geraerts R., Overmars M. H.: Clearance based path optimization for motion planning. In International Conference on Robotics and Automation (ICRA) (2004), IEEE Press, San Diego, CA.

[4]

{Hel94} Helbing D.: A mathematical model for the behavior of individuals in a social field. Journal of Mathematical Sociology 19, 3 (1994), 189--219.

[5]

{HM95} Helbing D., Molnár P.: Social force model for pedestrian dynamics. Physical Review 51 (1995), 4282--4286.

[6]

{KL94} Kavraki L., Latombe J.-C.: Randomized preprocessing of configuration space for fast path planning. In International Conference on Robotics and Automation (ICRA) (1994), IEEE Press, San Diego, CA, pp. 2138--2139.

[7]

{KO04} Kamphuis A., Overmars M. H.: Motion planning for coherent groups of entities. In IEEE Int. Conf. on Robotics and Automation (2004), IEEE Press, San Diego, CA.

[8]

{KvLO96} Kavraki L., Švestka P., Latombe J.-C., Overmars M.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12 (1996), 556--580.

[9]

{LC03} Li T.-Y., Chou H.-C.: Motion planning for a crowd of robots. In International Conference on Robotics and Automation (ICRA) (2003), IEEE Press, San Diego, CA.

[10]

{LLS99} Leroy S., Laumond J.-P., Simeon T.: Multiple path coordination for mobile robots: A geometric algorithm. In International Joint Conference on Artificial Intelligence (1999), pp. 1118--1123.

Digital Library

[11]

{MD01} Musse S. R., D. Thalmann: Hierarchical model for real time simulation of virtual human crowds. IEEE Transactions on Visualization and Computer Graphics 7, 2 (2001), 152--164.

Digital Library

[12]

{Pot99a} Pottinger D.: Coordinated unit movement. Game Developer (January 1999), 42--51.

[13]

{Pot99b} Pottinger D.: Implementing coordinated movement. Game Developer (February 1999), 48--58.

[14]

{Rey87} Reynolds C.: Flocks, herds, and schools: A distributed behavioral model. Computer Graphics 21, 4 (1987), 25--34.

Digital Library

[15]

{Rey99} Reynolds C.: Steering behaviors for autonomous characters. In Game Developers Conference (1999).

[16]

{RN94} Russell S., Norvig P.: Artificial Intelligence: A Modern Approach. Prentice Hall, 1994.

Digital Library

[17]

{RW95} Reif J., Wang H.: Social potential fields: A distributed behavioral control for autonomous robots. In K. Goldberg, D. Halperin, J.-C. Latombe, and R. Wilson, editors, International Workshop on Algorithmic Foundations of Robotics (WAFR) (1995), A. K. Peters, Wellesley, MA, 1995., pp. 431--459.

Digital Library

[18]

{SL02} Sanchez G., Latombe J.: Using a prm planner to compare centralized and decoupled planning for multi-robot systems. In Proc. IEEE Int. Conf. on Robotics and Automation (2002), pp. 2112--2119.

[19]

{UT01} Ulicny B., Thalmann D.: Crowd simulation for interactive virtual environments and vr-training systems. In Eurographics Workshop on Animation and Simulation (2001), Springer-Verlag, pp. 163--170.

Digital Library

[20]

{vO98} Švestka P., Overmars M.: Coordinated path planning for multiple robots. Robotics and Autonomous Systems 23 (1998), 125--152.

Cited By

Dandoulaki MEvripiotis IGaspari MKatsaros MLinaki ESerraos K(2022)Emergency Management against Natural Hazards in the Acropolis of AthensSustainability10.3390/su14201299914:20(12999)Online publication date: 11-Oct-2022
https://doi.org/10.3390/su142012999
Kim JLee JKim S(2020)Navigating Non-Playable Characters Based on User Trajectories with Accumulation Map and Path SimilaritySymmetry10.3390/sym1210159212:10(1592)Online publication date: 25-Sep-2020
https://doi.org/10.3390/sym12101592
Ahmed SJohora FMüller J(2020)Investigating the Role of Pedestrian Groups in Shared Spaces through Simulation ModelingSimulation Science10.1007/978-3-030-45718-1_4(52-69)Online publication date: 7-Apr-2020
https://doi.org/10.1007/978-3-030-45718-1_4
Show More Cited By

Index Terms

Finding paths for coherent groups using clearance

Recommendations

Finding k Shortest Paths in Cayley Graphs of Finite Groups
Abstract
We present a new method for finding k shortest paths between any two vertices in the Cayley graph $Cay (G, S)$ of a finite group G with its generating set S closed under inverses. By using a reduced convergent rewriting system R for G, we first find ...
Finding non-dominated bicriteria shortest pairs of disjoint simple paths

In this paper we introduce a method to compute non-dominated bicriteria shortest pairs, each including two disjoint simple paths. The method is based on an algorithm for ranking pairs of disjoint simple paths by non-decreasing order of cost, that is an ...
Finding next-to-shortest paths in a graph

We study the problem of finding the next-to-shortest paths in a graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. In contrast to the situation in ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation

August 2004

388 pages

ISBN:3905673142

Conference Chairs:
Norman Badler
University of Pennsylvania
,
Mathieu Desbrun
University of Southern California
,
Ronan Boulic,
Dinesh Pai

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 27 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCA04

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA04: Symposium on Computer Animation 2004

August 27 - 29, 2004

Grenoble, France

Acceptance Rates

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
955
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dandoulaki MEvripiotis IGaspari MKatsaros MLinaki ESerraos K(2022)Emergency Management against Natural Hazards in the Acropolis of AthensSustainability10.3390/su14201299914:20(12999)Online publication date: 11-Oct-2022
https://doi.org/10.3390/su142012999
Kim JLee JKim S(2020)Navigating Non-Playable Characters Based on User Trajectories with Accumulation Map and Path SimilaritySymmetry10.3390/sym1210159212:10(1592)Online publication date: 25-Sep-2020
https://doi.org/10.3390/sym12101592
Ahmed SJohora FMüller J(2020)Investigating the Role of Pedestrian Groups in Shared Spaces through Simulation ModelingSimulation Science10.1007/978-3-030-45718-1_4(52-69)Online publication date: 7-Apr-2020
https://doi.org/10.1007/978-3-030-45718-1_4
Knob PRockenbach GJung CMusse S(2019)Optimal Group Distribution based on Thermal and Psycho-Social AspectsProceedings of the 32nd International Conference on Computer Animation and Social Agents10.1145/3328756.3328765(59-64)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1145/3328756.3328765
Vomáčka TKolingerová IMaňák M(2019)Kinetic locally minimal triangulation: theoretical evaluation and combinatorial analysisThe Visual Computer10.1007/s00371-019-01657-y36:4(757-765)Online publication date: 3-May-2019
https://doi.org/10.1007/s00371-019-01657-y
He LPan JNarang SManocha DSolenthaler BTeschner MKavan LWojtan C(2016)Dynamic group behaviors for interactive crowd simulationProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2982818.2982838(139-147)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.5555/2982818.2982838
Jaklin NGeraerts R(2016)Navigating Through Virtual WorldsHandbook of Research on Gaming Trends in P-12 Education10.4018/978-1-4666-9629-7.ch025(527-554)Online publication date: 2016
https://doi.org/10.4018/978-1-4666-9629-7.ch025
Rojas FTarnogol FYang H(2016)Dynamic social formations of pedestrian groups navigating and using public transportation in a virtual cityThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-015-1187-732:3(335-345)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1007/s00371-015-1187-7
Jaklin NKremyzas AGeraerts RZhao QThalmann DWu ELin MWang L(2015)Adding sociality to virtual pedestrian groupsProceedings of the 21st ACM Symposium on Virtual Reality Software and Technology10.1145/2821592.2821597(163-172)Online publication date: 13-Nov-2015
https://dl.acm.org/doi/10.1145/2821592.2821597
Wang SGain JNistchke GEsparcia-Alcázar A(2015)Controlling Crowd Simulations using Neuro-EvolutionProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754715(353-360)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754715
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten