RESEARCH ARTICLE
A colored Petri net model for DisCSP algorithms
Carlos Pascal,
Doru Panescu,
Corresponding Author
Carlos Pascal
Automatic Control and Applied Informatics, Gheorghe Asachi Technical University of Iasi, Iasi, Romania
Correspondence
Carlos Pascal, Automatic Control and Applied Informatics, Gheorghe Asachi Technical University of Iasi, Iasi, Romania.
Email: [email protected]
Search for more papers by this authorDoru Panescu
Automatic Control and Applied Informatics, Gheorghe Asachi Technical University of Iasi, Iasi, Romania
Search for more papers by this authorCarlos Pascal,
Doru Panescu,
Corresponding Author
Carlos Pascal
Automatic Control and Applied Informatics, Gheorghe Asachi Technical University of Iasi, Iasi, Romania
Correspondence
Carlos Pascal, Automatic Control and Applied Informatics, Gheorghe Asachi Technical University of Iasi, Iasi, Romania.
Email: [email protected]
Search for more papers by this authorDoru Panescu
Automatic Control and Applied Informatics, Gheorghe Asachi Technical University of Iasi, Iasi, Romania
Search for more papers by this authorSummary
The aim of this paper is to present a colored Petri net that models a system applying a DisCSP method. Our study considered 3 representative DisCSP algorithms: synchronous backtracking, asynchronous backtracking, and weak-commitment search. To obtain the model, it was necessary to transpose the operation of a DisCSP-based system into a discrete event system. The constructed colored Petri net is presented, with details on the information stored in places, procedures associated with transitions, and communication between agents. Through the performed trials (with the n-queens problem), it was proved that the model is correct, easy to use, and adaptable to different operation conditions. The conducted simulations revealed new results about the way the 3 analyzed algorithms compare one with the other. It was showed that the performance of weak-commitment search is degrading in cases close to real conditions, namely, when agents use un-updated information about the state of system. We could also study 3 strategies for improving the performance of DisCSP algorithms, making them more practicable. The proposed model is available for open use, it is independent of the software that carries out a DisCSP method, and it can be enhanced for other DisCSP algorithms and diverse communication schemes.
REFERENCES
- 1Bessiere C, Bouyakhf EH, Mechqrane Y, Wahbi M. Agile asynchronous backtracking for distributed constraint satisfaction problems. 23rd IEEE International Conference on Tools with Artificial Intelligence, 2011; 777-784. https://doi.org/10.1109/ICTAI.2011.122
- 2Faltings B, Yokoo M. Introduction: special issue on distributed constraint satisfaction. Artific Intel. 2005; 161: 1-5. https://doi.org/10.1016/j.artint.2004.10.001
- 3Mailler R, Lesser V. Asynchronous partial overlay: a new algorithm for solving distributed constraint satisfaction problems. J Artific Intel Res. 2006; 25: 529-576. https://doi.org/10.1613/jair.1786
- 4Meisels A. Distributed Search by Constrained Agents: Algorithms, Performance, Communication. Springer Science & Business Media; 2008.
- 5Shoham Y, Leyton-Brown K. Multiagent Systems: Algorithmic, Game-theoretic, and Logical Foundations. Cambridge University Press; 2008.
10.1017/CBO9780511811654 Google Scholar
- 6Wahbi M, Brown K. The Impact of Wireless Communication on Distributed Constraint Satisfaction. In: B O'Sullivan ed. Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, Springer. 2014;8656: 738-754. https://doi.org/10.1007/978-3-319-10428-7
10.1007/978-3-319-10428-7_53 Google Scholar
- 7Yeoh W, Yokoo M. Distributed problem solving. AI Magazine. 2012; 33(3): 53-65. https://doi.org/10.1609/aimag.v33i3.2429
- 8Yokoo M. Distributed constraint satisfaction: foundations of cooperation in multi-agent systems. Springer Sci Bus Med. 2012. https://doi.org/10.1007/978-3-642-59546-2
- 9Zanker M, Jannach D. Modeling and solving distributed configuration problems: a CSP-based approach. IEEE Transact Knowl Data Eng. 2013; 25(3): 603-618. https://doi.org/10.1109/TKDE.2011.236
- 10Freuder E, Mackworth A. Constraint Satisfaction: An Emerging Paradigm. In: F Rossi, P Van Beek, T Walsh, eds. Handbook of Constraint Programming. New York: Elsevier; 2006: 11-25.
10.1016/S1574-6526(06)80006-4 Google Scholar
- 11Yokoo M, Hirayama K. Algorithms for distributed constraint satisfaction: a review. Autonom Agents Multi-Agent Syst. 2000; 3: 85-207. https://doi.org/10.1023/A:1010078712316
- 12Yokoo M, Ishida T. Search algorithms for agents. In: G Weiss, ed. Multiagent Systems. A Modern Approach to Distributed Artificial Intelligence. Cambridge: The MIT Press; 2001: 165-199.
- 13Yokoo M, Durfee E, Ishida T, Kuwabara K. The distributed constraint satisfaction problem: formalization and algorithms. IEEE Transact Knowl Data Eng. 1998; 10(5): 673-685. https://doi.org/10.1109/69.729707
- 14Conry SE, Kuwabara K, Lesser VR, Meyer RA. Multistage negotiation for distributed constraint satisfaction. IEEE Transact Syst Man Cybernet. 1991; 21(6): 1462-1477. https://doi.org/10.1109/21.135689
- 15Modi PJ, Jung H, Tambe M, Shen W, Kulkarni S. A dynamic distributed constraint satisfaction approach to resource allocation. Proc. of International Conference on Principles and Practices of Constraint Programming (CP-2001). 2001; 685-700. https://doi.org/10.1007/3-540-45578-7_56
- 16Petcu A, Faltings B. A value ordering heuristic for distributed resource allocation. Proc. of Joint Annual Workshop of ERCIM/CoLogNet on CSCLP'04. 2004; 86-97. https://doi.org/10.1007/11402763_7
- 17Bartak R, Salido M, Rossi F. Constraint satisfaction techniques in planning and scheduling. J Intell Manuf. 2010; 21(1): 5-15. https://doi.org/10.1007/s10845-008-0203-4
- 18Hassine AB, Ho TB, Ito T. Meeting scheduling solver enhancement with local consistency reinforcement. Appl Intel. 2006; 24(2): 143-154. https://doi.org/10.1007/s10489-006-6935-y
- 19Mandiau R, Vion J, Piechowiak S, Monier P. Multi-variable distributed backtracking with sessions. Appl Intel. 2014; 41(3): 736-758. https://doi.org/10.1007/s10489-014-0532-2
- 20Meisels A, Kaplansky E. Scheduling agents–distributed timetabling problems, Practice and Theory of Automated Timetabling IV, Springer 2003; 2740: 166-177. https://doi.org/10.1007/978-3-540-45157-0_11
- 21Meisels A, Lavee O. Using additional information in DisCSP search. Proc. of 5th Workshop on Distributed Constraints Reasoning. 2004; 4.
- 22Nissim R, Brafman R, Domshlak C. A general, fully distributed multi-agent planning algorithm. Proc. of AAMAS 2010. 2010; 1: 1323-1330.
- 23Wahbi M, Ezzahir R, Bessiere C, Bouyakhf EH. Nogood-based asynchronous forward checking algorithms. Constr. 2013; 18(3): 404-433. https://doi.org/10.1007/s10601-013-9144-4
- 24Wallace R, Freuder E. Constraint-based multi-agent meeting scheduling: effects of agent heterogeneity on performance and privacy loss, Proc. of DCR'02. 2002; 176-182.
- 25Xiang Y, Zhang W. Distributed university timetabling with multiply sectioned constraint networks. FLAIRS Conference. 2008; 567-571.
- 26Pascal C, Panescu D. On applying DisCSP for scheduling in holonic systems. 20th International Conference on System Theory, Control and Computing (ICSTCC). 2016; 423-428. https://doi.org/10.1109/ICSTCC.2016.7790702
- 27Muscalagiu I, Popa HE, Panoiu M, Negru V. Multi-agent Systems Applied in the Modelling and Simulation of the Protein Folding Problem Using Distributed Constraints. In: M Klusch, M Thimm, M Paprzycki eds. Multiagent System Technologies, Proceedings of MATES 2013, Lecture Notes in Computer Science, Springer. 2013; 8076: 346-360. https://doi.org/10.1007/978-3-642-40776-5_29
10.1007/978-3-642-40776-5_29 Google Scholar
- 28Monier P, Doniec A, Piechowiak S, Mandiau R. Metrics for the evaluation of DisCSP: some experiments on multi-robot exploration. IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT). 2010; 2: 370-373. https://doi.org/10.1109/WI-IAT.2010.71
- 29Monier P, Doniec A, Piechowiak S, Mandiau R. Comparison of DCSP algorithms: a case study for multi-agent exploration. In: Y Demazeau, M Pechoucek, JM Corchado, JB Perez eds. Proc. of the 9th international conference on practical applications of agents and multiagent systems (PAAMS), Springer, Advances in Intelligent and Soft Computing. 2011; 88: 231-236. https://doi.org/10.1007/978-3-642-19875-5_30
10.1007/978-3-642-19875-5_30 Google Scholar
- 30Pal A, Ritu RT, Shukla A. Communication constraints multi-agent territory exploration task. Appl Intel. 2013; 38(3): 357-383. https://doi.org/10.1007/s10489-012-0376-6
- 31Panescu D, Pascal C. A constraint satisfaction approach for planning of multi-robot systems, Proc. of 18th International Conference on System Theory, Control, and Computing (ICSTCC), Sinaia, Romania; 2014: 157-162. https://doi.org/10.1109/ICSTCC.2014.6982408
- 32Pascal C, Panescu D. A Petri net model for constraint satisfaction application in holonic systems. IEEE International Conference on Automation, Quality and Testing, Robotics (AQTR), Cluj-Napoca, Romania. 2014. https://doi.org/10.1109/AQTR.2014.6857900
- 33Felfernig A, Friedrich G, Jannach D, Zanker M. Towards distributed configuration. Advances in Artificial Intelligence. In: F Baader, G Brewka, T Eiter, eds. Lecture Notes in Computer Science. Vol. 2174. Berlin: Springer; 2001: 198-212. https://doi.org/10.1007/3-540-45422-5_15
- 34Jannach D, Zanker M. Modeling and solving distributed configuration problems: a CSP-based approach. IEEE Transact Knowl Data Eng. 2013; 25(3): 603-618. https://doi.org/10.1109/TKDE.2011.236
- 35Sodagari S, 2014. Application of asynchronous weak commitment search in autonomous quality of service provision in cognitive radio networks, arXiv preprint, arXiv:1403.2077
- 36Bejar R, Domshlak C, Fernández C, et al. Sensor networks and distributed CSP: communication, computation and complexity. Artific Intel. 2005; 161(1-2): 117-147. https://doi.org/10.1016/j.artint.2004.09.002
- 37Fernandez C, Bejar R, Krishnamachari B, Gomes C. Communication and computation in distributed CSP algorithms. Principles and Practice of Constraint Programming, Springer, Berlin 2002; 664-679. https://doi.org/10.1007/3-540-46135-3_44
- 38Fouchal H, Habbas Z. Distributed backtracking algorithm based on tree decomposition over wireless sensor networks. Concurr Comput: Pract Exp. 2013; 25(5): 728-742. https://doi.org/10.1002/cpe.1804
- 39Zhang W, Xing Z, Wang G, Wittenburg L. An analysis and application of distributed constraint satisfaction and optimization algorithms in sensor networks. Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, New York. 2003; 185-192.
- 40Bessiere C. Constraint Propagation. In: F Rossi, P Van Beek, T Walsh, eds. Handbook of Constraint Programming. New York: Elsevier; 2006: 27-82.
10.1016/S1574-6526(06)80007-6 Google Scholar
- 41Brito I, Herrero F, Meseguer P. On the evaluation of DisCSP algorithms. Fifth International Workshop on Distributed Constraint Reasoning at the Tenth International Conference on Principles and Practice of Constraint Programming (CP-2004), Toronto, Canada, 2004.
- 42Brito I, Meseguer P. Synchronous, asynchronous and hybrid algorithms for DisCSP. Principles and Practice of Constraint Programming (CP-2004). In: M Wallace, ed. Lecture Note in Computer Science. Vol. 3258. Springer; 2004: 791-805.
- 43Grinshpoun T, Meisels A. Completeness and performance of the APO algorithm. J Artific Intel Res. 2008; 33: 223-258. https://doi.org/10.1613/jair.2611
- 44Zivan R, Meisels A. Synchronous vs asynchronous search on DisCSPs. Proceedings of the First European Workshop on Multi-Agent Systems (EUMA) 2003.
- 45Zivan R, Meisels A. Message delay and DisCSP search algorithms. Ann Math Artific Intel. 2006; 46(4): 415-439. https://doi.org/10.1007/s10472-006-9033-2
- 46Portinale L. Modeling and solving constraint satisfaction problems through Petri nets. International Conference on Application and Theory of Petri Nets. 1997; 1248: 348-366. https://doi.org/10.1007/3-540-63139-9_45
- 47Hirayama K, Yokoo M. The distributed breakout algorithms. Artific Intel. 2005; 161: 89-115. https://doi.org/10.1016/j.artint.2004.08.004
- 48Mailler R, Zheng H. A new analysis method for dynamic, distributed constraint satisfaction. In: A Lomuscio, P Scerri, A Bazzan, M Huhns eds. Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AMAS 2014); 2014.
- 49Hamadi Y, Ringwelski G. Boosting distributed constraint satisfaction. J Heurist. 2011; 17(3): 251-279. https://doi.org/10.1007/11564751_41
- 50Meisels A, Zivan R. Asynchronous forward-checking for DisCSPs. Constr. 2007; 12(1): 131-150. https://doi.org/10.1007/s10601-006-9013-5
- 51Muscalagiu I. The effect of flag introduction on the explosion of nogood values in the case of ABT family techniques. In: Multi-Agent Systems and Applications IV. Berlin: Springer; 2005: 286-295. https://doi.org/10.1007/11559221_29
10.1007/11559221_29 Google Scholar
- 52Wahbi M, Brown K. Global Constraints in Distributed CSP: Concurrent GAC and Explanations in ABT. In: Principles and Practice of Constraint Programming. Springer International Publishing; 2014: 721-737. https://doi.org/10.1007/978-3-319-10428-7_52
10.1007/978-3-319-10428-7_52 Google Scholar
- 53Wahbi M, Ezzahir R, Bessiere C, Bouyakhf EH. Nogood-based asynchronous forward checking algorithms. Constr. 2013; 18(3): 404-433. https://doi.org/10.1007/s10601-013-9144-4
- 54Meisels A, Kaplansky E, Razgon I, Zivan R. Comparing performance of distributed constraints processing algorithms. Workshop on Distributed Constraint Reasoning (AAMAS-2002). 2002.
- 55Grubshtein A, Herschorn N, Netzer A, Rapaport G, Yaffe G, Meisels A. The distributed constraints (DisCo) simulation tool. Proceedings of the IJCAI workshop on Distributed Constraint Reasoning. 2011; 30-42.
- 56Leaute T, Ottens B, Szymanek R. FRODO 2.0: An open-source framework for distributed constraint optimization, Proceedings of the IJCAI 2009 Workshop on Distributed Constraint Reasoning, 2009; 160-164.
- 57Mailler R, Graves J. Solving distributed CSPs using dynamic, partial centralization without explicit constraint passing. In: Principles and Practice of Multi-Agent Systems. Berlin, Heidelberg: Springer; 2012: 27-41.
10.1007/978-3-642-25920-3_3 Google Scholar
- 58Sultanik EA, Lass RN, Regli WC. Dcopolis: a framework for simulating and deploying distributed constraint reasoning algorithms. Proc AAMAS. 2008; 2008: 1667-1668.
- 59Wahbi M, Ezzahir R, Bessiere C, Bouyakhf EH. DisChoco 2: a platform for distributed constraint reasoning. Proceedings of the IJCAI workshop on Distributed Constraint Reasoning 2011; 112-121.
- 60Jensen K, Kristensen LM. Coloured Petri nets: Modeling and Validation of Concurrent Systems. New York: Springer-Verlag; 2009.
10.1007/b95112 Google Scholar
- 61Kristensen LM, Jensen K. Specification and validation of an edge router discovery protocol for mobile ad-hoc networks, Proceedings of Integration of Software Specification Techniques for Applications in Engineering, Lecture Notes in Computer Science, Springer, Berlin 2004; 3147: 248-269.
- 62Smith B. Modelling. In: F Rossi, P Van Beek, T Walsh, eds. Handbook of Constraint Programming. Elsevier: New York; 2006: 375-404.
10.1016/S1574-6526(06)80015-5 Google Scholar
- 63Jensen K, Kristensen LM. Colored Petri nets: a graphical language for formal modeling and validation of concurrent systems. Comm ACM. 2015; 58(6): 61-70. https://doi.org/10.1145/2663340
- 64Barták R, Salido M. Constraint satisfaction for planning and scheduling problems. Constr. 2011; 16(3): 223-227. https://doi.org/10.1007/s10601-011-9109-4
- 65Panescu D, Pascal C. An extended contract net protocol with direct negotiation of managers. In: Service Orientation in Holonic and Multi-Agent Manufacturing and Robotics. Springer International Publishing; 2014: 81-95.
10.1007/978-3-319-04735-5_6 Google Scholar
- 66Panescu D, Pascal C. Holonic coordination obtained by joining the contract net protocol with constraint satisfaction. Comp Ind. 2016; 81: 36-46. https://doi.org/10.1016/j.compind.2015.08.010
- 67Pascal C, Panescu D. A Petri net model for constraint satisfaction application in holonic systems. IEEE International Conference on Automation, Quality and Testing, Robotics (AQTR), Cluj-Napoca, Romania; 2014. https://doi.org/10.1109/AQTR.2014.6857900
- 68Wahbi M. Algorithms and ordering heuristics for distributed constraint satisfaction problems. Doctoral dissertation, Université Mohammed V-Agdal; 2012.
- 69Leitão P. Agent-based distributed manufacturing control: a state-of-the-art survey. Eng Appl Artif Intel. 2009; 22(7): 979-991.
- 70Hsieh FS. Developing cooperation mechanism for multi-agent systems with Petri nets. Eng Appl Artif Intel. 2009; 22(4): 616-627.
- 71Borangiu T, Gilbert P, Ivanescu NA, Rosu A. An implementing framework for holonic manufacturing control with multiple robot-vision stations. Eng Appl Artif Intel. 2009; 22(4): 505-521.
- 72Pascal C, Panescu D. On applying DisCSP for scheduling in holonic systems, Proc. of 20th International Conference on System Theory, Control, and Computing (ICSTCC), Sinaia, Romania. 2016; 423-428.
- 73Hirayama K, Yokoo M. The effect of nogood learning in distributed constraint satisfaction. Proceedings of the 20th International Conference on Distributed Computing Systems. 2000; 169-177. https://doi.org/10.1109/ICDCS.2000.840919
- 74Lee J, Shi Y. Removing redundant conflict value assignments in resolvent based nogood learning. Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems, International Foundation for Autonomous Agents and Multiagent Systems. 2014; 1133-1140.
- 75 DisCSP Models. Available: http://github.com/carlospascal/DisCSP-CPN-Models, 2016.
