A reactive agent-based problem-solving model: Application to localization and tracking

ABSTRACT

For two decades, multi-agent systems have been an attractive approach for problem solving and have been applied to a wide range of applications. Despite the lack of generic methodology, the reactive approach is interesting considering the properties it provides. This article presents a problem-solving model based on a swarm approach where agents interact using physics-inspired mechanisms. The initial problem and its constraints are represented through agents' environment, the dynamics of which is part of the problem-solving process. This model is then applied to localization and target tracking. Experiments assess our approach and compare it to widely-used classical algorithms.

REFERENCES

• 1: Adorni, G., Cagnoni, S., Enderle, S., Kraetzschmar, G., Mordonini, M., Plagge, M., Ritter, M., Sablatnog, S., and Zell, A. 2001. Vision-based localization for mobile robots. J. Robot. Auton. Syst. 36, 2--3, 103--1191.
• 2: Baerveldt, A.-J. 2001. A vision system for object verification and localization based on local features. Robot. Auto. Syst. 34, 83--92.
• 3: Bernardino, A. and Santos-Victor, J. 1998. Visual behaviours for binocular tracking. Robot. Auton. Syst. 25. 137--146.
• 4: Bernon, C., Camps, V., Gleizes, M., and Picard, G. 2004. Designing agents behaviours within the framework of adelfe methodology. In Proceedings of Engineering Societies in the Agents World (ESAW03). Lecture Notes in Artifual Intelligence, vol. 3071, Springer Verlag, 311--32.
• 5: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 6: Christine Bourjot , Vincent Chevrier , Vincent Thomas, How social spiders inspired an approach To region detection, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544840]
• 7: Brueckner, S. 2000. Return from the ant: Synthetic eco-systems for manufacturing control. PhD. Thesis at Department of Computer Science, Humboldt University, Berlin. 2000.
• 8: Chong, C.-Y. 1998. Distributed architectures for data fusion. In Fusion '98 International Conference. In Proceedings of the International Conferance on Multisource-Multisensor Information Fusion (Fusion'98).
• 9: Colorni, A., Dorigo, M., and Maniezzo, V. 1991. Distributed optimization by ant colonies. In Proceedings of ECAL91, European Conference on Artificial Life, Paris, 134--142.
• 10: Dellaert, F., Fox, D., Burgard, W., and Thrun, S. 1999. Monte Carlo localization for mobile robots. In Proceeding of the IEEE International Conference on RObotics and Automation (ICRA).
• 11: Demirli, K. and Turksen, I. 2000. Sonar based mobile robot localization by using fuzzy triangulation. In Robot. and Auton. Syst. 33, 2--3. 109--123.
• 12: Giovanna Di Marzo Serugendo , Anthony Karageorgos , Omer F. Rana , Franco Zambonelli, Engineering Self-Organising Systems, SpringerVerlag, 2004
• 13: Drogoul, A. and Dubreuil, C. 1993. A distributed approach to n-puzzle solving. In Proceedings of the Distributed Artificial Intelligence Workshop. Seattle, WA.
• 14: Alexis Drogoul , Jacques Ferber, From Tom Thumb to the Dockers: some experiments with foraging robots, Proceedings of the second international conference on From animals to animats 2 : simulation of adaptive behavior: simulation of adaptive behavior, p.451-459, August 1993, Honolulu, Hawai, United States
• 15: Drogoul, A., Ferber, J., and Jacopin, E. 1991. Pengi: Applying eco-problem-solving for behavior modelling in an abstract eco-system. In Proceedings of the Modelling and Simulation: Councils, Copenhague, Denmark, 337--342.
• 16: Jacques Ferber, Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 17: Ferber, J. and Jacopin, E. 1991. The framework of eco-problem solving. In Proceedings of Decentralized Artificial Intelligence. 2, North-Holland. Yves Demazeau and Jean-Pierre Muller Eds. 181--193.
• 18: Dieter Fox , Wolfram Burgard , Frank Dellaert , Sebastian Thrun, Monte Carlo localization: efficient position estimation for mobile robots, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.343-349, July 18-22, 1999, Orlando, Florida, United States
• 19: Fox, D., Burgard, W., Dellaert, F., and Thrun, S. 2000. Particle filters for mobile robot localization. In Sequential Monte Carlo Methods in Practice. Springer Verlag, New York, NY.
• 20: Fox, D., Burgard, W., and Thrun, S. 2001. Active markov localization for mobile robots. Robot. Auton. Syst. 25, 195--207.
• 21: F. Gechter, Vision based localisation for a mobile robot, Proceedings of the 12th IEEE International Conference on Tools with Artificial Intelligence, p.229, November 13-15, 2000
• 22: Gechter, F., Thomas, V., and Charpillet, F. 2001. Robot localization by stochastic vision based device. In the 5th World Multi-Conference on Systemics, Cybernetics and Informatics, Orlando, FL.
• 23: Robert Grabowski , Luis E. Navarro-Serment , Christiaan J. J. Paredis , Pradeep K. Khosla, Heterogeneous Teams of Modular Robots for Mapping and Exploration, Autonomous Robots, v.8 n.3, p.293-308, June 2000 [doi>10.1023/A:1008933826411 ]
• 24: Henkel, R. 2000. Synchronization, coherence-detection and three-dimensional vision. Tech. rep., Institute of Theoretical Neurophysics, University of Bremen.
• 25: Hue, C., Cadre, J.-P. L., and Perez, P. 2000. Tracking multiple objects with particle filtering. Tech. rep., INRIA.
• 26: Jeanpierre, L. 2002. Apprentissage et adaptation pour la modélisation stochastique de systèmes dynamiques réels. PhD. thesis, UHP University Nancy 1.
• 27: James Kennedy , Russell C. Eberhart, Swarm intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 28: Kwok, C., Fox, D., and Meila, M. 2003. Adaptive real-time particle filters for robot localization. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).
• 29: Mamei, M. and Zambonelli, F. 2004. Co-fields: A physically inspired approach to distributed motion coordination. In Proceedings of the IEEE Pervasive Computing. vol. 3, no. 2.
• 30: Marco Mamei , Franco Zambonelli, Programming stigmergic coordination with the TOTA middleware, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082537]
• 31: Mataric, M. J. 1995. Designing and understanding adaptative group behavior. In Proceedings of Adaptive Behavior 4, 1, 51--80.
• 32: Muller, J.-P. 2004. Emergence of collective behavior and problem solving. In Proceedings of Engineering Societies in the Agents World, (ESAW'03). Lecture Notes in Artificial Intelligence vol. 3071. Springer Verlag, 1--21.
• 33: Muller, J.-P. and Parunak, H. 1998. Multi-agent systems and manufacturing. In Proceedings of the 9th Symposium on Information Control in Manufacturing (INCOM'98). Nancy-Metz, France.
• 34: Hans-Hellmut Nagel , A. Gehrke, Bildbereichsbasierte Verfolgung von Straßenfahrzeugen durch adaptive Schätzung und Segmentierung von Optischen-Fluß-Feldern, Mustererkennung 1998, 20. DAGM-Symposium, p.314-321, September 29-October 01, 1998
• 35: Parunak, H. 1997. Go to the ant. In Engin. Princ. Natural Agent Systems. Ann. Operat. Res.
• 36: Pourraz, F. and Crowley, J. L. 1999. Continuity properties of the appearance manifold for mobile robot position estimation. Workshop on Perception for Mobile Agents (CVPRI'99).
• 37: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.25-34, August 1987
• 38: Roumeliotis, S., Sukhatme, G., and Bekey, G. 1999. Circumventing dynamic modeling: Evaluation of the error-state kalman filter applied to mobile robot localization. IEEE ICRA. Detroit, MI.
• 39: Simonin, O. and Ferber, J. 2000. Modeling self satisfaction and altruism to handle action selection and reactive cooperation. In Proceedings of the 6th International Conference on the Simulation of Adaptative Behavior FROM ANIMALS TO ANIMATS 6. (Paris, France), 314--323.
• 40: Simonin, O. and Gechter, F. 2006. An environment-based methodology to design reactive multi-agent systems for problem solving. Lecture Note in Artificial Intelligence, vol. 383. Springer, 32--49.
• 41: Steels, L. 1989. Cooperation between distributed agents through self-organization. Workshop on Multi-Agent Cooperation. North Holland, Cambridge, UK.
• 42: Sebastian Thrun , John C. Langford , Dieter Fox, Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Processes, Proceedings of the Sixteenth International Conference on Machine Learning, p.415-424, June 27-30, 1999
• 43: Welch, G. and Bishop, G. 2000. An introduction to the kalman filter. Dr. Rer.Nat. Thesis. Departement of Computer Science, Humbolt University Berlin, Berlin, Germany.
• 44: Weyns, D., Parunak, V., Michel, F., Holvoet, T., and Ferber, J. 2005. Environments for multiagent systems, state of the art and research challenges. In Post-proceedings of the 1st International Workshop on Environments for Multiagent Systems. Lecture Notes in Artificial Intelligence, vol. 3374. Springer.
• 45: Zeghal, K. and Ferber, J. 1994. A reactive approach for distributed air traffic control. In Proceedings of Avignon. 381--390.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Experimentation

Keywords:
Reactive multi-agent systems, localization, mobile robots, tracking