This CAREER project will develop representations and reasoning algorithms for Distributed Constraint Reasoning (DCR) to support the coordination of autonomous agents operating in real-time, open and large-scale real-world environments. The extension to existing DCR algorithms is the use of intelligent clustering of autonomous agents to reduce the time to find a solution. The research plan will result in a publicly available toolkit of DCR algorithm implementations, a common DCR algorithm evaluation environment, and a library of benchmark DCR models and datasets of real-world applications that will greatly facilitate the design and use of DCR algorithms.
The critical need addressed in this research project is for representations, domain modeling techniques, and efficient algorithms for allowing loosely-coupled agents to coordinate effectively through distributed reasoning about interactions between individual agent decisions. The specific issues addressed are: time limitations, and privacy and security. This project investigates how to design algorithms that allow agents to tradeoff solution quality for computation time in domains where time is limited. This project investigates bottom-up clustering as a key technique for approximation for large problems. The key outstanding challenge is how to do the clustering so that the small communities can do problem solving independently without large or unknown effects on overall quality. Privacy and security concerns are ubiquitous when agents are used to represent the interests of humans. This project addresses the issue of privacy and security by developing a language and models for DCOP that will allow users to express policies for information they would like agents to keep private while solving the DCOP. The language will be formal so that algorithm designers can develop DCOP algorithms that can be proven to adhere to these policies, perhaps at the cost of efficiency or solution quality.
The project will validate and implement the developed technology in three real-world domains which require coordination at varying time-scales: a) Cognitive radio, which requires coordination on the order of seconds or minutes, b) mission scheduling, which requires coordination on the order of hours or days, and c) digital assistants, which requires coordination on the order of weeks, months or years. Performance measurement and comparison of distributed algorithms is more complicated than for traditional centralized algorithms. To more accurately measure the performance of DCOP algorithm, the project uses a constraint-based metric by counting concurrent constraint checks and the time required in a cycle to deliver all messages sent in the previous cycle.
