Skip to main content
SpringerLink
Log in

EKEMAS, an agent-based geo-simulation framework to support continual planning in the real-word

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

In this paper, we propose an agent-based geo-simulation framework EKEMAS to assist human planners when planning under strong spatial constraints in a real large-scale space. The approach consists in drawing a parallel between the real environment (for example, a forest in fire) and the simulated environment based on GIS data. This virtual environment uses software agents which are aware of the space and equipped with advanced spatial reasoning capabilities. In addition, we suggest some enhancements for the Continual Planning approach. Our aim is to demonstrate how EKEMAS, when coupled with a continual planning approach and agent’s spatial reasoning capabilities, can assist human planners overcoming obstacles related to real world constraints: dynamic, uncertain, and spatially constrained environment. We illustrate this idea on the forest firefighting problem and we use MAGS as a simulation platform and Prometheus as a fire simulator. Finally, and since plans in the studied case (wildfire fighting) are mainly paths, we also propose a new approach based on agent geo-simulation in order to solve particular Pathfinding problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Atkin M, Westbrook DL, Cohen PR, Jorstad GD (1998) AFS and HAC: domain-general agent simulation and control. In: AAAI-98 workshop on software tools for developing agents, pp 89–95

  2. Ambros-Ingerson JA, Steel S (1988) Integrating planning, execution and monitoring. In: Proceedings of the 7th (US) national conference on artificial intelligence (AAAI 88), St Paul, MN, USA. American Association for Artificial Intelligence. Morgan Kaufmann, San Mateo, pp 83–88

    Google Scholar 

  3. Avesani P, Perini A, Ricci F (2000) Interactive case-based planning for forest fire management. Appl Intell 13(1):41–57

    Article  Google Scholar 

  4. Bauzil G, Briot M, Ribes P (1981) A navigation sub-system using ultrasonic sensors for the mobile robot HILARE. In: Proceedings of the 1st international conference on robot vision and sensory controls, Stratford-upon-Avon, UK, pp 47–58, 681–698

  5. Benenson I, Torrens PM (2004) Geosimulation, automata-based modeling of urban phenomena. Wiley, New York

    Google Scholar 

  6. Birta LG, Özmizrak FN (1996) A knowledge-based approach for the validation of simulation models: the foundation. ACM Trans Model Comput Simul 6(1):76–98

    Article  Google Scholar 

  7. Boutilier C, Dean T, Hanks S (1999) Decision-theoretic planning: structural assumptions and computational leverage. J AI Res 11:1–94

    MATH  MathSciNet  Google Scholar 

  8. Cohen PR, Greenberg ML, Hart DM, Howe AE (1989) Trial by fire: understanding the design requirements for agents in complex environments. AI Mag 10(3):34–48

    Google Scholar 

  9. de la Asunción M, Castillo L, Fdez-Olivares J, García-Pérez O, González A, Palao F (2004) SIADEX: an interactive artificial intelligence planner for decision support in forest fire fighting. In: Proceedings of workshop on binding environmental sciences and artificial intelligence (BESAI 2004), European conference on artificial intelligence

  10. Delin KA, Jackson SP, Some RR (1999) Sensor webs, NASA Tech Briefs, 23, 80

  11. Desjardins ME, Durfee EH, Ortiz CL, Wolverton MJ (1999) A survey of research in distributed continual planning. AI Mag 4:13–22

    Google Scholar 

  12. Egenhofer M, Mark D (1995) Naive geography. In: Frank A, Kuhn W (eds) Spatial information theory—a theoretical basis for GIS, international conference COSIT ’95, Semmering, Austria. Lecture notes in computer science, vol 988. Springer, Berlin, pp 1–15

    Google Scholar 

  13. Feinstein AH, Cannon HM (2002) Constructs of simulation evaluation. Simul Gaming 33:425–440

    Article  Google Scholar 

  14. Firewise website (2004) http://www.firewise.org/pubs/wildfire_control/last

  15. Forbus KD (1981) A study of qualitative and geometric knowledge in reasoning about motion. Technical report, Massachusetts Institute of Technology AI Laboratory, AI-TR-615

  16. Gat E (1998) On three-layer architectures. In: Kortenkamp D, Bonnasso P, Murphy R (eds) Artificial intelligence and mobile robots. AAAI Press, Menlo Park, pp 195–210

    Google Scholar 

  17. Golden K, Etzioni O, Weld D (1994) Omnipotence without omniscience: Efficient sensor management for planning. In: Proceedings of the 12th national conference on artificial intelligence. AAAI Press, Menlo Park, pp 1048–1054

    Google Scholar 

  18. Gross D, Strand R (2000) Can agent-based models assist decisions on large-scale practical problems? A philosophical analysis. Complexity 5(6):26–33

    Article  Google Scholar 

  19. Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 2:100–107

    Article  Google Scholar 

  20. Hellstrom T (2002) Autonomous navigation for forest machines. A project pre-study in the Department of Computer Science, Umea University, Sweden

  21. Hoc JM (1987) Cognitive psychology of planning. Academic Press, New York

    Google Scholar 

  22. Horn G, Baxter J (2000) An interactive planner for tank squadron assaults. In: Proceedings of the 1st planning and scheduling special interest group workshop, Milton Keynes, UK

  23. Jennings NR (2000) On agent-based software engineering! AI J 117:277–296

    MATH  Google Scholar 

  24. Jiang X, Chen NY, Hong JI, Wang K, Takayama L, Landay JA (2004) Siren: context-aware computing for firefighting. In: Proceedings of the 2nd international conference on pervasive computing, Linz/Vienna, Austria, pp 19–23

  25. Kahneman D, Tversky A (1982) The simulation heuristic. In: Kahneman, Slovic, Tversky (eds) Judgment under uncertainty: heuristics and biases. Cambridge University Press, New York

    Google Scholar 

  26. Khatib O (1986) A unified approach for motion and force control of robot manipulators: the operational space formulation. IEEE J Robot Autom 3(1):43–54

    Article  MathSciNet  Google Scholar 

  27. Kitchin RM (1994) Cognitive maps: what are they and why study them? J Environ Psychol 14:119

    Google Scholar 

  28. Kerst SM, Howard JH, Gugerty LJ (1987) Judgment accuracy in pair-distance estimation and map sketching. Bull Psychon Soc 25(3):185–188

    Google Scholar 

  29. Knoblock B (1995) Planning, executing, sensing, and re-planning for information gathering. In: Proceedings of the 14th international joint conference on artificial intelligence, Montreal, pp 1686–1693

  30. Kray C (2001) The benefits of multi-agent systems in spatial reasoning. In: Proceedings of the conference Flairs’01, special track on spatio-temporal reasoning, Key West, USA

  31. Kremens R, Seema A, Fordham A, Luisi D, Nordgren B, VanGorden S, Vodacek A (2001) Networked, autonomous field-deployable fire sensors. In: Proceedings of the international wildland fire safety summit

  32. LaMothe A (1999) Tricks of the Windows game programming gurus. Sams, New York

    Google Scholar 

  33. LaVallee S (2006) Planning algorithms. Cambridge University Press, Cambridge, Available at http://msl.cs.uiuc.edu/planning/

    Google Scholar 

  34. Lee JJ, Fishwick PA (1994) Real-time simulation-based planning for computer generated force simulation. Simulation 63(5):299–315

    Article  Google Scholar 

  35. Lee JJ, Fishwick PA (1995) Simulation-based real-time decision making for route planning. In: Proceedings of the winter simulation conference, Crystal City, VA, December 1995, pp 1087–1095

  36. Lee JJ, Fishwick PA (1997) Simulation-based planning for multi-agent environments. In: Proceedings of the winter simulation conference, pp 405–412

  37. Lewis M, Lenox T, Payne T, Sycara K (2001) Spatial planning in teams of human and machine agents. In: Proceedings of the 2nd conference on information technology and spatial planning, Isole Tremiti, Italy

  38. Marchant JA, Hague T, Tillet ND (1997) Row-following accuracy of an autonomous vision-guided agricultural vehicle. Comput Electron Agric 16(2):165–175

    Article  Google Scholar 

  39. Minguez J, Montano L (2005) Abstracting vehicle shape and kinematics constraints from obstacle avoidance methods. Auton Robots

  40. Moulin B, Chaker W, Perron J, Pelletier P, Hogan J (2003) MAGS project: multi-agent geosimulation and crowd simulation. In: Proceedings of COSIT’2003

  41. Nickerson BG, Lu J (2004) A language for wireless sensor webs. In: 2nd annual conference on communication networks and services research CNSR

  42. Niederberger C, Gross MH (2004) Generic path planning for real-time applications. In: Proceedings of computer graphics international, Heraklion, Crete, Greece

  43. O’Connor M, Bell T, Elkaim G, Parkinson B (1996) Automatic steering of farm vehicles using GPS. In: Proceedings of the 3rd international conference on precision agriculture

  44. Olawsky D, Gini M (1990) Deferred planning and sensor use. In: Proceedings of DARPA workshop on innovative approaches to planning, scheduling, and control, pp 166–174

  45. Ören TI, Numrich SK, Uhrmacher AM, Wilson LF, Gelenbe E (2000) Agent-directed simulation—challenges to meet defense and civilian requirements. In: Proceedings of the winter simulation conference, Orlando, vol 2, pp 1757–1762

  46. Prometheus (2005) www.firegrowthmodel.com

  47. Ruskin HJ, Walshe R (2006) Emergent computing—introduction to the special theme. ERCIM News, 64, January 2006, online edition. http://www.ercim.org/publication/Ercim_News/enw64/intro-st.html

  48. Russel S, Norvig P (1995) Artificial intelligence, a modern approach. Prentice Hall, New York

    Google Scholar 

  49. Sahli N, Moulin B (2005) Real-world pathfinding using agent-based simulation. In: Proceedings of the agent-directed simulation symposium part of the 2005 spring simulation multiconference

  50. Sahli N, Moulin B (2006) Agent-based geo-simulation to support human planning and spatial cognition (extended version). In: Sichman JS, Antunes L (eds) MABS 2005. Lecture notes in artificial intelligence, vol 3891. Springer, Berlin, pp 115–132

    Google Scholar 

  51. Şerban G (2002) Real time learning in agent based systems. In: Proceedings of the 4th international workshop on symbolic and numeric algorithms for scientific computing, Timisoara, Romania

  52. Tversky B (1981) Distortions in memory for maps. Cogn Psychol 13:407–433

    Article  Google Scholar 

  53. Weynes D, Schelfthout K, Holvoet T (2005) Exploiting a virtual environment in a real-world application. In: Proceedings of workshop environment for multi-agent systems (E4MAS) in international conference AAMAS’05, Utrecht, Holland

Download references

Author information

Authors and Affiliations

  1. Telematica Instituut, P.O. Box 589, 7500 AN, Enschede, The Netherlands

    Nabil Sahli

  2. Computer Science Department, Laval University, 3908 Pav. Pouliot, Quebec, QC, G1K7P4, Canada

    Bernard Moulin

Authors
  1. Nabil Sahli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bernard Moulin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nabil Sahli.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sahli, N., Moulin, B. EKEMAS, an agent-based geo-simulation framework to support continual planning in the real-word. Appl Intell 31, 188–209 (2009). https://doi.org/10.1007/s10489-008-0122-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-008-0122-2

Keywords

Search

Navigation