DCOPolis: a framework for simulating and deploying distributed constraint reasoning algorithms

Abstract

The proliferation of mobile computers---such as laptops, personal digital assistants, and smart phones---has propelled distributed computing into mainstream society. Over the past decade these technologies have spurred interest in both decentralized multiagent systems and wireless mobile ad-hoc networks. Such networks, however, present many challenges to information sharing and coordination. Interference, obstacles, and other environmental effects conspire with power-and processing-limited hardware to impose a number of challenging networking characteristics. Messages are routinely lost or delayed, connections may be only sporadically available, and network transfer capacity is nowhere near that available on modern wired networks. It is therefore imperative to emphasize local decision making and autonomy over a centralized analogue, insofar as it is possible. The majority of such decentralized decision making can be seen as a fundamental problem of propagating and then solving systems of constraints, otherwise known as Distributed Constraint Reasoning (DCR).