Document Open Access Logo

Completeness Matters: Towards Efficient Caching in Tree-Based Synchronous Backtracking Search for DCOPs

Authors Jie Wang, Dingding Chen, Ziyu Chen, Xiangshuang Liu, Junsong Gao

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.39.pdf
  • Filesize: 1.22 MB
  • 17 pages

Document Identifiers

Author Details

Jie Wang
  • College of Computer Science, Chongqing University, China
Dingding Chen
  • College of Computer Science, Chongqing University, China
Ziyu Chen
  • College of Computer Science, Chongqing University, China
Xiangshuang Liu
  • College of Computer Science, Chongqing University, China
Junsong Gao
  • College of Computer Science, Chongqing University, China

Cite As Get BibTex

Jie Wang, Dingding Chen, Ziyu Chen, Xiangshuang Liu, and Junsong Gao. Completeness Matters: Towards Efficient Caching in Tree-Based Synchronous Backtracking Search for DCOPs. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CP.2022.39

Abstract

Tree-based backtracking search is an important technique to solve Distributed Constraint optimization Problems (DCOPs), where agents cooperatively exhaust the search space by branching on each variable to divide subproblems and reporting the results to their parent after solving each subproblem. Therefore, effectively reusing the historical search results can avoid unnecessary resolutions and substantially reduce the overall overhead. However, the existing caching schemes for asynchronous algorithms cannot be applied directly to synchronous ones, in the sense that child agent reports the lower and upper bound rather than the precise cost of exploration. In addition, the existing caching scheme for synchronous algorithms has the shortcomings of incompleteness and low cache utilization. Therefore, we propose a new caching scheme for tree-based synchronous backtracking search, named Retention Scheme (RS). It utilizes the upper bounds of subproblems which avoid the reuse of suboptimal solutions to ensure the completeness, and deploys a fine-grained cache information unit targeted at each child agent to improve the cache-hit rate. Furthermore, we introduce two new cache replacement schemes to further improve performance when the memory is limited. Finally, we theoretically prove the completeness of our method and empirically show its superiority.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Cooperation and coordination
Keywords
  • DCOP
  • Cache
  • Any-space Algorithms
  • Complete Search Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. James Atlas, Matt Warner, and Keith Decker. A memory bounded hybrid approach to distributed constraint optimization. In Proc. 10th International Workshop on Distributed Constraint Reasoning, pages 37-51, 2008. Google Scholar
  2. Ismel Brito and Pedro Meseguer. Improving DPOP with function filtering. In AAMAS, volume 1435, pages 141-148, 2010. Google Scholar
  3. Anton Chechetka and Katia Sycara. No-commitment branch and bound search for distributed constraint optimization. In Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pages 1427-1429, 2006. Google Scholar
  4. Anton Chechetka and Katia P Sycara. An Any-space Algorithm for Distributed Constraint Optimization. In AAAI Spring Symposium: Distributed Plan and Schedule Management, pages 33-40, 2006. Google Scholar
  5. Dingding Chen, Yanchen Deng, Ziyu Chen, Wenxing Zhang, and Zhongshi He. HS-CAI: A hybrid DCOP algorithm via combining search with context-based inference. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7087-7094, 2020. Google Scholar
  6. Ziyu Chen, Wenxin Zhang, Yanchen Deng, Dingding Chen, and Qiang Li. RMB-DPOP: Refining MB-DPOP by Reducing Redundant Inference. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 249-257, 2020. Google Scholar
  7. Rina Dechter, David Cohen, et al. Constraint processing. Morgan Kaufmann, 2003. Google Scholar
  8. Yanchen Deng, Ziyu Chen, Dingding Chen, Xingqiong Jiang, and Qiang Li. PT-ISABB: A Hybrid Tree-based Complete Algorithm to Solve Asymmetric Distributed Constraint Optimization Problems. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 1506-1514, 2019. Google Scholar
  9. Alessandro Farinelli, Alex Rogers, and Nick R Jennings. Agent-based decentralised coordination for sensor networks using the max-sum algorithm. Autonomous agents and multi-agent systems, 28(3):337-380, 2014. Google Scholar
  10. Alessandro Farinelli, Alex Rogers, Adrian Petcu, and Nicholas R Jennings. Decentralised coordination of low-power embedded devices using the max-sum algorithm. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 2, pages 639-646, 2008. Google Scholar
  11. Ferdinando Fioretto, Enrico Pontelli, and William Yeoh. Distributed constraint optimization problems and applications: A survey. Journal of Artificial Intelligence Research, 61:623-698, 2018. Google Scholar
  12. Ferdinando Fioretto, William Yeoh, Enrico Pontelli, Ye Ma, and Satishkumar J Ranade. A distributed constraint optimization (DCOP) approach to the economic dispatch with demand response. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 999-1007, 2017. Google Scholar
  13. Eugene C Freuder and Michael J Quinn. Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems. In IJCAI, volume 85, pages 1076-1078. Citeseer, 1985. Google Scholar
  14. Patricia Gutierrez and Pedro Meseguer. BnB-ADOPT+ with Several Soft Arc Consistency Levels. In ECAI, pages 67-72, 2010. Google Scholar
  15. Katsutoshi Hirayama and Makoto Yokoo. Distributed partial constraint satisfaction problem. In International conference on principles and practice of constraint programming, pages 222-236. Springer, 1997. Google Scholar
  16. Omer Litov and Amnon Meisels. Forward bounding on pseudo-trees for DCOPs and ADCOPs. Artificial Intelligence, 252:83-99, 2017. Google Scholar
  17. Rajiv T Maheswaran, Jonathan P Pearce, and Milind Tambe. A family of graphical-game-based algorithms for distributed constraint optimization problems. In Coordination of large-scale multiagent systems, pages 127-146. Springer, 2006. Google Scholar
  18. Rajiv T Maheswaran, Milind Tambe, Emma Bowring, Jonathan P Pearce, and Pradeep Varakantham. Taking dcop to the real world: Efficient complete solutions for distributed multi-event scheduling. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 1, pages 310-317, 2004. Google Scholar
  19. Toshihiro Matsui, Hiroshi Matsuo, and Akira Iwata. Efficient Methods for Asynchronous Distributed Constraint Optimization Algorithm. In Artificial Intelligence and Applications, pages 727-732, 2005. Google Scholar
  20. Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo. ADOPT: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence, 161(1-2):149-180, 2005. Google Scholar
  21. Arnon Netzer, Alon Grubshtein, and Amnon Meisels. Concurrent forward bounding for distributed constraint optimization problems. Artificial Intelligence, 193:186-216, 2012. Google Scholar
  22. Duc Thien Nguyen, William Yeoh, Hoong Chuin Lau, and Roie Zivan. Distributed gibbs: A linear-space sampling-based DCOP algorithm. Journal of Artificial Intelligence Research, 64:705-748, 2019. Google Scholar
  23. Brammert Ottens, Christos Dimitrakakis, and Boi Faltings. DUCT: An upper confidence bound approach to distributed constraint optimization problems. ACM Transactions on Intelligent Systems and Technology (TIST), 8(5):1-27, 2017. Google Scholar
  24. Adrian Petcu and Boi Faltings. DPOP: A scalable method for multiagent constraint optimization. In IJCAI 05, pages 266-271, 2005. Google Scholar
  25. Adrian Petcu and Boi Faltings. ODPOP: An algorithm for open/distributed constraint optimization. In AAAI, volume 6, pages 703-708, 2006. Google Scholar
  26. Adrian Petcu and Boi Faltings. MB-DPOP: A New Memory-Bounded Algorithm for Distributed Optimization. In IJCAI, pages 1452-1457, 2007. Google Scholar
  27. Evan Sultanik, Pragnesh Jay Modi, and William C Regli. On Modeling Multiagent Task Scheduling as a Distributed Constraint Optimization Problem. In IJCAI, pages 1531-1536, 2007. Google Scholar
  28. Meritxell Vinyals, Juan A Rodriguez-Aguilar, Jesús Cerquides, et al. Generalizing DPOP: Action-GDL, a new complete algorithm for DCOPs. In AAMAS (2), pages 1239-1240, 2009. Google Scholar
  29. William Yeoh, Ariel Felner, and Sven Koenig. BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm. Journal of Artificial Intelligence Research, 38:85-133, 2010. Google Scholar
  30. William Yeoh, Pradeep Varakantham, and Sven Koenig. Caching schemes for DCOP search algorithms. In AAMAS (1), pages 609-616, 2009. Google Scholar
  31. Weixiong Zhang, Guandong Wang, Zhao Xing, and Lars Wittenburg. Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks. Artificial Intelligence, 161(1-2):55-87, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact