Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Previous work in multiagent coordination has addressed the challenge of planning in domains where agents must optimize a global goal, while satisfying local resource constraints. However, the imposition of resource constraints naturally raises the question of whether the agents could significantly improve their team performance if a few more resources were made available. Sensitivity analysis aims to answer that question. This paper focuses on sensitivity analysis in the context of the distributed coordination framework, Multiply-Constrained DCOP (MC-DCOP). There are three main challenges in performing sensitivity analysis: (i) to perform it in a distributed fashion, (ii) to avoid re-solving an NP-hard MC-DCOP optimization from scratch, and (iii) to avoid considering unproductive uses for extra resources. To meet these challenges, this paper presents three types of locally optimal algorithms: link analysis, local reoptimization and local constraint propagation. These algorithms are distributed and avoid redundant computation by ascertaining just the effects of local perturbations on the original problem. Deploying our algorithms on a large number of MC-DCOP problems revealed several results. While our cheapest algorithm successfully identified quality improvements for a few problems, our more complex techniques were necessary to identify the best uses for additional resources. Furthermore, we identified two heuristics that can help identify a priori which agents might benefit most from additional resources: density rank, which works well when nodes received identical resources and remaining resource rank, which works well when nodes received resources based on the number of neighbors they had.

REFERENCES

• 1: R. Bakker, F. Dikker, F. Tempelman, and P. Wognum. Diagnosing and solving over-determined constraint satisfaction problems. In IJCAI, 1993.
• 2: Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
• 3: Emma Bowring , Jonathan P Pearce , Christopher Portway , Manish Jain , Milind Tambe, On k-optimal distributed constraint optimization algorithms: new bounds and algorithms, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 4: E. Bowring, M. Tambe, and M. Yokoo. Multiply-constrained dcop for distributed planning and scheduling. In AAMAS, 2006.
• 5: M. W. Dawande , J. N. Hooker, Inference-Based Sensitivity Analysis for Mixed Integer/Linear Programming, Operations Research, v.48 n.4, p.623-634, July 2000 [doi>10.1287/opre.48.4.623.12420]
• 6: Carla P. Gomes, Artificial intelligence and operations research: challenges and opportunities in planning and scheduling, The Knowledge Engineering Review, v.15 n.1, p.1-10, March 2000 [doi>10.1017/S0269888900001090]
• 7: Nicholas G. Hall , Marc E. Posner, Sensitivity Analysis for Scheduling Problems, Journal of Scheduling, v.7 n.1, p.49-83, January-February 2004 [doi>10.1023/B:JOSH.0000013055.31639.f6]
• 8: G. Kharmanda, N. Olhoff, A. Mohamed, and M. Lemaire. Reliability-based topology optimization. Journal of Structural and Multidisciplinary Optimization, 26:295--307, 2004.
• 9: Haksun Li , H. Durfee , Kang G. Shin, Multiagent planning for agents with internal execution resource constraints, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860665]
• 10: Rajiv T. Maheswaran , Milind Tambe , Emma Bowring , Jonathan P. Pearce , Pradeep Varakantham, Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.310-317, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.257]
• 11: 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]
• 12: T. Matsui, H. Matsuo, M. Silaghi, K. Hirayama, and M. Yokoo. Resource constrained distributed constraint optimization with virtual variables. In AAAI, pages 120--125, 2008.
• 13: Praveen Paruchuri , Milind Tambe , Fernando Ordonez , Sarit Kraus, Towards a Formalization of Teamwork with Resource Constraints, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.596-603, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.277]
• 14: F. Pecora, P. Modi, and P. Scerri. Reasoning About and Dynamically Posting n-ary Constraints in ADOPT. In Proceedings of 7th Int. Workshop on Distributed Constraint Reasoning, at AAMAS, 2006.
• 15: A. Petcu, B. Faltings, and R. Mailler. PC-DPOP: A new partial centralization algorithm for distributed optimization. Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI, 7:167--172, 2007.
• 16: L. Schrage and L. Wolsey. Sensitivity analysis for branch and bound integer programming. Operations Research, 33:1008--1023, 1984.
• 17: Kostas Stergiou , Toby Walsh, Encodings of non-binary constraint satisfaction problems, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.163-168, July 18-22, 1999, Orlando, Florida, United States
• 18: L. Wolsey. Integer programming duality: Price functions and sensitivity analysis. Mathematical Programming, 20:173--195, 1981.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Design

Keywords:
DCOP, distributed constraint reasoning, multiagent systems