A Collaborative Solving Algorithm for Dynamic Distributed Constraint Optimization Problem
GE Fang-Zhen1,2,WEI Zhen1,LU Yang1,QIU Shu-Wei1,LI Li-Xiang3
1.School of Computer and Information,Hefei University of Technology,Hefei 230009 2.School of Computer Science and Technology,Huaibei Normal University,Huaibei 235000 3.Information Security Center,Beijing University of Posts and Telecommunications,Beijing 100876
Abstract A large number of problems in the multiagent collaboration process can be modeled under the framework of distributed constraint optimization problem (DCOP). However,DCOP framework is limited to the issue of planning,and the agents in DCOP generally require a complete and accurate reward function. To resolve this issue,a dynamic distributed constraint optimization problem (DDCOP) is defined,and DDCOP′s crucial operations,exploration and exploitation,are analyzed. Furthermore,a chaotic ant based collaborative solving algorithm for dynamic distributed constraint optimization problem (CA-DDCOP) is proposed. The CA-DDCOP algorithm is established based on chaotic behavior of a single ant and self-organizing behavior of ant colony,thereby the exploration and exploitation are realized. The proposed algorithm achieves the collaboration of exploration and exploitation according to the Boltzmann distribution. Then a channel allocation in multi-radio multi-channel Ad Hoc networks is solved by the CA-DDCOP algorithm. The simulation results show that the CA-DDCOP algorithm performs effectively.
[1] Modi P J,Shen Weishen,Tambe M,et al. ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees. Artificial Intelligence,2006,161(1/2): 149-180 [2] Cox J S,Durfee E H,Bartold T. A Distributed Framework for Solving the Multiagent Plan Coordination Problem // Proc of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems. Utrecht,The Netherlands,2005: 821-827 [3] Enembreck F,Scalabrin E E,Avila B C,et al. Distributed Constraint Optimization for scheduling in CSCWD // Proc of the 13th International Conference on Computer Supported Cooperative Work in Design. Santiago,Chile,2009: 252-257 [4] Vlassis N,Elhorst R,Kok J R. Anytime Algorithms for Multiagent Decision Making Using Coordination Graphs // Proc of the IEEE International Conference on Systems,Man and Cybernetics. The Hague,The Netherlands,2004,I: 953-957 [5] Mailler R,Lesser V. Solving Distributed Constraint Optimization Problems Using Cooperative Mediation // Proc of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems. New York,USA,2004: 438-445 [6] Petcu A,Faltings B. A Scalable Method for Multiagent Constraint Optimization // Proc of the 19th International Joint Conference on Artificial Intelligence. Edinburgh,UK,2005: 266-271 [7] Chechetka A,Sycara K. No-Commitment Branch and Bound Search for Distributed Constraint Optimization // Proc of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems. Hakodate,Japan,2006: 1427-1429 [8] Gershman A,Meisels A,Zivan R. Asynchronous Forward Bounding for Distributed COPs. Journal of Artificial Intelligence Research,2009,34(1): 61-88 [9] Enembreck F,Barthès J P A. Distributed Constraint Optimization with MULBS: A Case Study on Collaborative Meeting Scheduling. Journal of Network and Computer Applications,2012,35(1): 164-175 [10] Fitzpatrick S,Meertens L. Distributed Coordination through Anarchic Optimization // Lesser V,Ortiz C L,Tambe M. eds. Distributed Sensor Networks: A Multiagent Perspective. Dordrecht,The Netherlands: Kluwer Academic Publisher,2003: 257-295 [11] Maheswaran R T,Pearce J P,Tambe M. Distributed Algorithms for DCOP: A Graphical-Game-Based Approach // Proc of the 17th International Conference on Parallel and Distributed Computing Systems. San Francisco,USA,2004: 432-439 [12] Zivan R. Anytime Local Search for Distributed Constraint Optimization // Proc of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems. Estoril,Portugal,2008,Ⅲ: 1449-1452 [13] Zhang Y,Bellingham J G,Davis R E,et al. Optimizing Autonomous Underwater Vehicles′ Survey for Reconstruction of an Ocean Field that Varies in Space and Time // Proc of the Fall Meeting of American Geophysical Union. New Orleans,USA,2005: 445-451 [14] Beard R W,McLain T W,Nelson D B,et al. Decentralized Cooperative Aerial Surveillance Using Fixed-Wing Miniature UAVs. Proc of the IEEE,2006,94(7): 1306-1324 [15] Ge Fangzhen,Wei Zhen,Lu Yang,et al. Decentralized Coordination of Autonomous Swarms Inspired by Chaotic Behavior of Ants. Nonlinear Dynamics,2012,70(1): 571-584 [16] Hamann H,Schmickl T,Crailsheim K. Thermodynamics of Emergence: Langton′s Ant Meets Boltzmann // Proc of the IEEE Symposium on Artificial Life. Paris,France,2011: 62-69 [17] Ferreira P R,Boffo F S, Bazzan A L C. Using Swarm-GAP for Distributed Task Allocation in Complex Scenarios // Jamali N,Scerri P,Sugawara T,eds. Massively Multi-Agent Technology. Berlin,Germany: Springer-Verlag,2008: 107-121 [18] Santos F D,Bazzan A L C. Ant-Based Task Allocation among Teams // Proc of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems. Budapest,Hungary,2009: 1183-1184 [19] Cole B J. Short-Term Activity Cycles in Ants: Generation of Periodicity by Worker Interaction. American Naturalist,1991,137(2): 244-259 [20] Cole B J. Is Animal Behaviour Chaotic? Evidence from the Activity of Ants. Biological Sciences,1991. DOI: 10.1098/rspb.1991.0079 [21] Solé R V,Miramontes O,Goodwin B C. Oscillations and Chaos in Ant Societies. Journal of Theoretical Biology,1993,161(3): 343-357 [22] Peng Haipeng,Li Lixiang,Yang Yixian,et al. Parameter Estimation of Dynamical Systems via a Chaotic Ant Swarm. Physical Review E,2010. DOI: 10.1103/PhysRevE.81.016207 [23] Miramontes O. Order-Disorder Transitions in the Behavior of Ant Societies. Complexity,1995,1(3): 56-60 [24] Couzin I D. Collective Cognition in Animal Groups. Trends in Cognitive Sciences,2009,13(1): 36-43 [25] Gupta R,Musacchio J,Walrand J. Sufficient Rate Constraints for QoS Flows in Ad-Hoc Networks. Ad Hoc Networks,2007,5(4): 429-443 [26] Wooseong K,Kassler A J,Di Felice M,et al. Urban-X: Towards Distributed Channel Assignment in Cognitive Multi-Radio Mesh Networks // Proc of the IFIP Wireless Days. Venice,Italy,2010: 1-5 [27] Nezhad M A,Cerda-Alabern L. Adaptive Channel Assignment for Wireless Mesh Networks Using Game Theory // Proc of the 8th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (MASS). Valencia,Spain,2011: 746-751
2013, Vol. 26 
