Abstract
Navigation of a group of autonomous agents that are required to maintain a formation is a challenging task which has not been studied much especially in 3-D terrains. This paper presents a novel approach to collision free path finding of multiple agents preserving a predefined formation in 3-D terrains. The proposed method could be used in many areas like navigation of semi-automated forces (SAF) at unit level in military simulations and non-player characters (NPC) in computer games. The proposed path finding algorithm first computes an optimal path from an initial point to a target point after analyzing the 3-D terrain data from which it constructs a weighted graph. Then, it employs a real-time path finding algorithm specifically designed to realize the navigation of the group from one waypoint to the successive one on the optimal path generated at the previous stage, preserving the formation and avoiding collision. Software was developed to test the methods discussed here.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bahceci E, Soysal O, Sahin E (2003) A review: pattern formation and adaptation in multi-robot systems. Technical report, Robotics Institute, Carnegie Mellon University
Balch T, Arkin RC (1998) Behavior-based formation control for multirobot teams. IEEE Trans Robot Autom 14(6):926–939
Bayrak AG, Polat F (2008) Formation preserving navigation of agent teams in 3-d terrains. In: Proceedings of industrial simulation conference (ISC), pp 148–155
Berg MD, Krefeld MV, Overmars M, Schwarzkopf O (2000) Computational geometry: algorithms and applications. Springer, Berlin
Bourgeot J-M, Cislo N, Espiau B (2002) Path-planning and tracking in a 3d comlex environment for an anthropomorphic biped robot. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems IROS, Lausanne, Switzerland, pp 2509–2514
Bresenham JE (1965) Algorithm for computer control of a digital plotter. IBM Syst J 4(1):25–30
Dain RA (1998) Robot wall-following algorithms using genetic programming. Appl Intell 8(1):33–41
Dawson C (2002) Formations. AI Game Programming Wisdom. AI Wisdom, pp 272–281. Charles River Media, Boston
Desai JP, Kumar V, Ostrowski JP (1999) Control of changes in formation for a team of mobile robots. In: Proceedings of IEEE international conference on robotics and automation, vol 2, pp 1556–1561
Fugere J, LaBoissonniere F, Liang Y (1999) An approach to design autonomous agents within modsaf. In: Proceedings of IEEE SMC’99 conference on systems, man, and cybernetics, Tokyo, Japan, vol 2, pp 534–539
Geraerts R, Overmars MH (2002) A comparative study of probabilistic roadmap planners. In: Workshop on the algorithmic foundations of robotics (WAFR’02). Springer, Berlin, pp 43–57
Helbing D, Buzna L, Johansson A, Werner T (2005) Self-organized pedestrian crowd dynamics: experiments, simulations, and design solutions. Transp Sci 39(1):1–24
Hsu C.-H., Liu A (2005) Multiagent-based multi-team formation control for mobile robots. J Intell Robot Syst 42(4):337–360
Kambhampati S, Davis L (1986) Multiresolution path planning for mobile robots. IEEE J Robot Autom 2(3):135–145
Kavraki L, Latombe JC (1998) Probabilistic roadmaps for robot path planning. In: Practical motion planning in robotics: current and future directions. Addison-Wesley, Reading, pp 33–53
Lewis MA, Tan KH (1997) High precision formation control of mobile robots using virtual structures. Auton Robots 4(4):387–403
Loscos C, Marchal D, Meyer A (2003) Intuitive crowd behavior in dense urban environments using local law. In: Proceedings theory practice of computer graphics (TPCG 03), pp 122–129
McIlroy D, Smith B, Heinze C, Turner M (1997) Air defence operational analysis using the SWARMM model. In: Asia pacific operations research symposium
Ngo VT, Nguyen AD, Ha QP (2005) Toward a generic architecture for robotic formations: planning and control. In: Proceedings of the sixth international conference on intelligent technologies, pp 89–96
OGRE—Open Source 3D Graphics Engine. http://www.ogre3d.org
Parsons D, Surdu J, Jordan B (2005) Onesaf: a next generation simulation modeling the contemporary operating environment. In: Proceedings of Euro-simulation interoperability workshop
Pradhan SK, Parhi DR, Panda AK, Behera RK (2006) Potential field method to navigate several mobile robots. Appl Intell 25(3):321–333
Reece DA (2003) Movement behavior for soldier agents on a virtual battlefield. Presence 12(4):387–410
Reynolds CW (1987) Flocks, herds, and schools: a distributed behavioral model. Comput Graph 21(4):25–34
Russell S, Norvig P (2003) Artificial intelligence a modern approach. Prentice Hall, New York
Sahli N, Moulin B (2009) Ekemas, an agent-based geo-simulation framework to support continual planning in the real-word. Appl Intell 31(2):188–209
Sanchez G, Ramos F, Frausto J (1999) Locally-optimal path planning by using probabilistic roadmaps and simulated annealing. In: Proceedings IASTED robotics and applications international conference
Stentz A (1994) Optimal and efficient path planning for partially-known environments. In: Proceedings of the IEEE international conference on robotics and automation, vol 4, pp 3310–3317
Tomlinson SL (2004) The long and short of steering in computer games. Int J Simul 1–2(5):33–46
Treuille A, Cooper S, Popović Z (2006) Continuum crowds. ACM Trans Graph 25(3):1160–1168
Undeger C, Polat F (2007) Rttes: real-time search in dynamic environments. Appl Intell 27(2):113–129
Vaughan J, Connell R, Lucas A, Ronnquist R (2003) Towards complex team behavior in multi-agent systems using a commercial agent platform. In: Lecture notes in computer science, vol 2564. Springer, Berlin, pp 175–185
Verth JV, Brueggemann V, Owen J, McMurry P (2000) Formation-based pathfinding with real-world vehicles. In: Proceedings of the game developers conference
Voorbrk F, Massion N (2001) Decision-theoretic planning for autonomous robotic surveillance. Appl Intell 14(3):252–262
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bayrak, A.G., Polat, F. Formation preserving path finding in 3-D terrains. Appl Intell 36, 348–368 (2012). https://doi.org/10.1007/s10489-010-0265-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-010-0265-9