Decentralised coordination of continuously valued control parameters using the max-sum algorithm

ABSTRACT

In this paper we address the problem of decentralised coordination for agents that must make coordinated decisions over continuously valued control parameters (as is required in many real world applications). In particular, we tackle the social welfare maximisation problem, and derive a novel continuous version of the max-sum algorithm. In order to do so, we represent the utility function of the agents by multivariate piecewise linear functions, which in turn are encoded as simplexes. We then derive analytical solutions for the fundamental operations required to implement the max-sum algorithm (specifically, addition and marginal maximisation of general n-ary piecewise linear functions). We empirically evaluate our approach on a simulated network of wireless, energy constrained sensors that must coordinate their sense/sleep cycles in order to maximise the system-wide probability of event detection. We compare the conventional discrete max-sum algorithm with our novel continuous version, and show that the continuous approach obtains more accurate solutions (up to a 10% increase) with a lower communication overhead (up to half of the total message size).

REFERENCES

• 1: S. M. Aji and R. J. McEliece. The generalized distributive law. Information Theory, IEEE Transactions on, 46(2):325--343, 2000.
• 2: A. Farinelli , A. Rogers , A. Petcu , N. R. Jennings, Decentralised coordination of low-power embedded devices using the max-sum algorithm, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 3: S. Fitzpatrick and L. Meertens. Distributed Sensor Networks A multiagent perspective, chapter Distributed Coordination through Anarchic Optimization, pages 257--293. Kluwer Academic, 2003.
• 4: B. J. Frey and D. Dueck. Clustering by passing messages between data points. Science, 315(5814):972--976, 2007.
• 5: B. Grocholsky, J. Keller, V. Kumar, and G. Pappas. Cooperative air and ground surveillance. IEEE Robotics&Automation Magazine, 13(3):16--25, 2006.
• 6: J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1]
• 7: Chih-fan Hsin , Mingyan Liu, Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984685]
• 8: Aman Kansal , Jason Hsu , Sadaf Zahedi , Mani B. Srivastava, Power management in energy harvesting sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.4, p.32-es, September 2007 [doi>10.1145/1274858.1274870]
• 9: F. R. Kschischang, B. J. Frey, and H. A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 42(2):498--519, 2001.
• 10: David J. C. MacKay, Information Theory, Inference & Learning Algorithms, Cambridge University Press, New York, NY, 2002
• 11: R. J. Maheswaran, J. Pearce, and M. Tambe. A family of graphical-game-based algorithms for distributed constraint optimization problems. In Coordination of Large-Scale Multiagent Systems, pages 127--146. Springer-Verlag, 2005.
• 12: Roger Mailler , Victor Lesser, Solving Distributed Constraint Optimization Problems Using Cooperative Mediation, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.438-445, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.249]
• 13: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, Adopt: asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence, v.161 n.1-2, p.149-180, January 2005 [doi>10.1016/j.artint.2004.09.003]
• 14: Mark Paskin , Carlos Guestrin , Jim McFadden, A robust architecture for distributed inference in sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 15: A. Petcu and B. Faltings. DPOP: A scalable method for multiagent constraint optimization. In Proc. of the 19th Int. Joint Conf. on Artificial Intelligence, pages 266--271, 2005.
• 16: Y. Weiss and W. T. Freeman. On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory, 47(2):723--735, 2001.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
DCOP, computational geometry, coordination