Optimize my schedule but keep it flexible: Distributed multi-criteria coordination for personal assistants
Emma Bowring, Milind Tambe, Makoto Yokoo · 2005
Research projects have begun focusing on deploying personal assistant agents to coordinate users in such diverse environ-ments as offices, distributed manufacturing or design centers, and in support of first responders for emergencies. In such en-vironments, distributed constraint optimization (DCOP) has emerged as a key technology for multiple collaborative as-sistants to coordinate with each other. Unfortunately, while previous work in DCOP only focuses on coordination in ser-vice of optimizing a single global team objective, personal assistants often require satisfying additional individual user-specified criteria. This paper provides a novel DCOP algo-rithm that enables personal assistants to engage in such multi-criteria coordination while maintaining the privacy of their additional criteria. It uses n-ary NOGOODS implemented as private variables to achieve this. In addition, we’ve developed an algorithm that reveals only the individual criteria of a link and can speed up performance for certain problem structures. The key idea in this algorithm is that interleaving the crite-ria searches — rather than sequentially attempting to satisfy the criteria — improves efficiency by mutually constraining the distributed search for solutions. These ideas are realized in the form of private-g and public-g Multi-criteria ADOPT, built on top of ADOPT, one of the most efficient DCOP al-gorithms. We present our detailed algorithm, as well as some experimental results in personal assistant domains.