A decentralized approach to cooperative situation assessment in multi-robot systems

ABSTRACT

To act effectively under uncertainty, multi-robot teams need to accurately estimate the state of the environment. Although individual robots, with uncertain sensors, may not be able to accurately determine the current situation, the team as a whole should have the capability to perform situation assessment. However, sharing all information with all other team mates is not scalable nor is centralization of all information possible. This paper presents a decentralized approach to cooperative situation assessment that balances use of communication bandwidth with the need for good situation assessment. When a robot believes locally that a particular plan should be executed, it sends a proposal for that plan, to one of its team mates. The robot receiving the plan proposal, can either agree with the plan and forward it on, or it can provide sensor information to suggest that an alternative plan might have higher expected utility. Once sufficient robots agree with the proposal, the plan is initiated. The algorithm successfully balances the value of cooperative sensing against the cost of sharing large volumes of information. Experiments verify the utility of the approach, showing that the algorithm dramatically out-performs individual decision-making and obtains performance similar to a centralized approach.

REFERENCES

• 1: M. Dietl, J.-S. Gutmann, and B. Nebel. Cooperative sensing in dynamic environments. In Proc. of Int. Conf. on Intelligent Robots and Systems (IROS'01), Maui, Hawaii, 2001.
• 2: H. Durrant-Whyte, D. Rye, and E. Nebot. Localisation of automatic guided vehicles. In Robotics Research: The 7th International Symposium (ISRR'95), pages 613--625. Springer Verlag, 1996.
• 3: D. Fox, W. Burgard, and S. Thrun. Markov localization for mobile robots in dynamic environments. Journal of Artificial Intelligence Research, 11:391--427, 1999.
• 4: D. Goldberg, V. Cicirello, M. B. Dias, et al. A distributed layered architecture for mobile robot coordination: Application to space exploration. In Proc. of 3rd Int. NASA Workshop on Planning and Scheduling for Space, 2002.
• 5: D. Hall and J. Llinas, editors. Handbook of Multisensor Data Fusion. CRC Press, 2001.
• 6: N. R. Jennings, Controlling cooperative problem solving in industrial multi-agent systems using joint intentions, Artificial Intelligence, v.75 n.2, p.195-240, June 1995 [doi>10.1016/0004-3702(94)00020-2]
• 7: K. Konolige, D. Fox, C. Ortiz, et al. Centibots: Very large scale distributed robotic teams. In Proc. of the Int. Symp. on Experimental Robotics (ISER04), Singapore, 2004.
• 8: Sarit Kraus , Katia Sycara , Amir Evenchik, Reaching agreements through argumentation: a logical model and implementation, Artificial Intelligence, v.104 n.1-2, p.1-69, Sept. 1998 [doi>10.1016/S0004-3702(98)00078-2]
• 9: A. Makarenko and H. Durrant-Whyte. Decentralized data fusion and control algorithms in active sensor networks. In In The 7th Int. Conf. on Information Fusion (Fusion '04), pages 479--486, 2004.
• 10: C. J. Matheus, M. M. Kokar, and K. Baclawski. A core ontology for situation awareness. In Proceedings of the Sixth International Conference on Information Fusion, 2003.
• 11: L. E. Parker. ALLIANCE: An architecture for fault tolerant multirobot cooperation. IEEE Transactions on Robotics and Automation, 14(2):220--240, April 1998.
• 12: D. V. Pynadath and M. Tambe. The communicative multiagent team decision problem: Analyzing teamwork theories and models. Journal of Artificial Intelligence Research, 16:389--423, 2002.
• 13: M. Rosencrantz, G. Gordon, and S. Thrun. Decentralized sensor fusion with distributed particle filters. In Proc. Conf. Uncertainty in Artificial Intelligence (UAI-03), Acapulco, Mexico, 2003.
• 14: Maayan Roth , Reid Simmons , Manuela Veloso, Reasoning about joint beliefs for execution-time communication decisions, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082593]
• 15: R. Saha and K. Chang. An efficient algorithm for multisensor track fusion. Aerospace and Electronic Systems, IEEE Transactions on Volume: 34 Issue: I, pages 200 -- 210, 1998.
• 16: Paul Scerri , Yang Xu , Elizabeth Liao , Justin Lai , Katia Sycara, Scaling Teamwork to Very Large Teams, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.888-895, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.239]
• 17: A. Stroupe, M. Martin, and T. Balch. Distributed sensor fusion for object position estimation by multi-robot systems. In Proc. of Int. Conf. on Robotics and Automation (ICRA2001), volume 2, pages 1092--1098, 2001.
• 18: M. Tambe. Towards flexible teamwork. Journal of Artificial Intelligence Research (JAIR), 7:83--124, 1997.
• 19: G. Theocharous, K. Rohanimanesh, and S. Mahadevan. Learning hierarchical partially observable markov decision processes for robot navigation. In IEEE Conf. on Robotics and Automation, (ICRA), Seoul, South Korea, 2001.
• 20: B. B. Werger and M. J. Mataric. Broadcast of local eligibility for multi-target observation. In Proc. of 5th Int. Symposium on Distributed Autonomous Robotic Systems, (DARS-2000), pages 347--356, Knoxville (TN), USA, October 2000.
• 21: R. Zlot, A. Stenz, M. B. Dias, and S. Thayer. Multi robot exploration controlled by a market economy. In Proc. of the Int. Conf. on Robotics and Automation (ICRA'02), pages 3016--3023, 2002.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

General Terms:
Algorithms, Experimentation

Keywords:
cooperative perception, robotics, situation assessment