ANTS Publications

Experiments on Dense Graphs with a Stochastic, Peer-to-Peer Colorer

Stephen Fitzpatrick & Lambert Meertens

Workshop on Probabilistic Approaches in Search at AAAI'02, Eighteenth National Conference on Artificial Intelligence, 28 July - 1 August 2002, Edmonton, Alberta, Canada; Carla Gomes & Toby Walsh (Ed.), AAAI Press, Technical Report WS-02-14, ISBN 1-57735-167-3, pp. 24-28

Paper: PDF or Postscript

This paper reports on a simple, stochastic, scalable, peer-to-peer algorithm for approximately solving distributed constraint problems in soft real time. The performance of the algorithm is assessed using soft k-coloring of random graphs having known chromatic number and edge probability ranging from moderate to high.

Asynchronous Execution and Communication Latency in Distributed Constraint Optimization

Lambert Meertens & Stephen Fitzpatrick

Third International Workshop on Distributed Constraint Reasoning at AAMAS 2002, 16 July 2002, Bologna, Italy; Makoto Yokoo (Ed.), pp. 80-85

Paper: PDF or Postscript

Previous papers have reported on a simple, distributed, synchronous algorithm for approximately k-colouring large graphs in soft real time. In this paper, the effects of asynchronous execution and communication latency are investigated. The main conclusions are that strict synchrony is not required and that considerable communication latency can be tolerated. These results are important for practical applications of the algorithm involving large networks of low-performance hardware equipped with wireless communication.

Scalable, Anytime Constraint Optimization through Iterated, Peer-to-Peer Interaction in Sparsely-Connected Networks

Stephen Fitzpatrick & Lambert Meertens

The Sixth Biennial World Conference on Integrated Design & Process Technology (IDPT 2002), 23-28 June 2002, Pasadena, California, U.S.A.; H. Ehrig, B.J. Kramer & A. Ertas (Ed.), Society for Design and Process Science, ISSN No. 1090-9389

Paper: PDF or Postscript

This paper reports on an algorithm for anytime, stochastic, distributed constraint optimization that uses iterated, peer-to-peer interaction to try to achieve rapid, approximate solutions to large constraint problems in which the constraint variables are naturally distributed. Two examples are given - graph coloring and coordination of distributed sensors - together with experimental results on performance.

Peer-to-Peer Coordination of Autonomous Sensors in High-Latency Networks using Distributed Scheduling and Data Fusion

Technical Report KES.U.01.09, December 2001

Lambert Meertens & Stephen Fitzpatrick

Report: PDF or Postscript

This report details an approach to the real-time coordination of large networks of short-range sensors that communicate over short-range, low-bandwidth, high-latency radio channels.

Each sensor is limited in the distance over which it can scan and in the type of data that it can acquire, so nearby sensors must collaborate to acquire complementary data for accomplishing such tasks as multiple-target detection and tracking.

Operational limitations on sensors and real-time requirements on tasks restrict the number of tasks in which a given sensor can collaborate. The quality with which a given task is accomplished and the cost incurred are affected by which particular sensors collaborate in achieving the task. Consequently, a coordination mechanism is required to optimize collaboration.

The coordination mechanism reported is fully distributed - each sensor decides for itself which measurements it should take to achieve optimal collaboration with nearby sensors, based what it knows about their intended measurements, and informs those sensors of its own intentions so that they can likewise optimize their own measurements.

In order to determine which measurements are optimal, a sensor must have knowledge about the targets that are the intended subjects of the measurements. To this end, each sensor exchanges measurement data with nearby sensors, and operates a data fusion process to maintain local target estimates.

The reported coordination mechanism is claimed to be scalable, low-cost, adaptive and robust.

An Experimental Assessment of a Stochastic, Anytime, Decentralized, Soft Colourer for Sparse Graphs

Stephen Fitzpatrick & Lambert Meertens

Proceedings of SAGA 2001, 1^st Symposium on Stochastic Algorithms, Foundations and Applications, Berlin, 13-14 December 2001, Springer-Verlag.

Paper: PDF or Postscript

This paper reports on a simple, decentralized, anytime, stochastic, soft graph-colouring algorithm. The algorithm is designed to quickly reduce the number of colour conflicts in large, sparse graphs in a scalable, robust, low-cost manner. The algorithm is experimentally evaluated in a framework motivated by its application to resource coordination in large, distributed networks.

Soft, Real-Time, Distributed Graph Coloring using Decentralized, Synchronous, Stochastic, Iterative-Repair, Anytime Algorithms - A Framework

Technical Report KES.U.01.05, May 2001

Stephen Fitzpatrick & Lambert Meertens

Report: PDF or Postscript

Soft, real-time distributed graph coloring is presented as a simplification of the problem of distributed resource management in an environment where communication is expensive and subject to relatively high latency. The resources are subject to dynamic task sets that may produce critical or super-critical loading - the objective is to quickly compute reasonable schedules for the resources that accomplish a satisfactory fraction of the task set. A class of simple, decentralized, anytime, approximate colorers is presented, together with a framework for assessing performance, and representative results from performance experiments using a simulator.