Solving Distributed CSPs Probabilistically

• Autorzy: Bistarelli S. , Gosti G.
• Języki publikacji: EN

Abstrakty

EN

Constraint solving problems (CSPs) are the formalization of a large range of problems that emerge fromcomputer science. The solving methodology described here is based on the naming game. The two main features that distinguish this methodology from most distributed constraint solving problem (DCSPs) methods are: the system can react to small instance changes, and it does not require pre-agreed agent/variable ordering. The naming game was introduced to represent N agents that have to bootstrap an agreement on a name to give to an object. The agents do not have a hierarchy, and use a minimal protocol. Still they converge to a consistent state by using a distributed strategy. For this reason, the naming game can be used to untangle DCSPs. It was shown that a distributed system of uniform finite state machines does not solve the ring ordering problem in all the algorithm executions. Our algorithm is a distributed uniform system of agents able to perform random decisions when presented with equivalent alternatives. We show that this algorithm solves the ring ordering problem with a probability one.

Słowa kluczowe

EN

Distributed Constraint Satisfaction Problem; naming game

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 105, nr 1/2
• Strony: 57--78
• Opis fizyczny: Bibliogr. 21 poz., wykr.

Twórcy

autor

Bistarelli S.

autor

Gosti G.

• IMBS, Social Science Plaza A, School of Social Sciences, Irvine, CA 92697-5100, USA,

Bibliografia

• [1] Baronchelli, A., Felici, M., Caglioti, E., Loreto, V., Steels, L.: Sharp Transition Toward Shared Vocabularies in Multi-Agent Systems. Journal of Statistical Mechanics, Exp P06014, 2006.
• [2] Baronchelli, A., Dall'Asta, L., Barrat, A. and Loreto., V.: Topology Induced Coarsening in Language Games Language. Phys. Rev., E 73, 015102(R), 2006.
• [3] Bistarelli, S.:Semirings for Soft Constraint Solving and Programming, LNCS 2962, Springer, Heidelberg, Germany, 2004, 1-28.
• [4] Bistarelli, S., Gosti, G.: Solving CSPs with Naming Games. Recent Advances in Constraints, CSCLP 2008, (Angelo Oddi, Franc¸ois Fages, Francesca Rossi Eds.). LNCS 5655, Springer, Heidelberg, Germany, 2009, 16-32
• [5] Bistarelli, S., Gosti, G.: Solving CSPs with naming games. In: CILC09: 24-esimo Convegno Italiano di Logica Computazionale, (Gavanelli, M., Riguzzi, F. Eds.), Ferrara, Italy, 2009.
• [6] Collin, Z., Dechter, R., and Katz, S.: On the Feasibility of Distributed Constraint Satisfaction. Proceedings of the Twelfth International Joint Conference of Artificial Intelligence, IJCAI-91, Sidney, Australia, 1991, 318-324.
• [7] Dijkstra E.W.: Self-Stabilizing Systems in Spite of Distributed Control. Communications of the ACM, 17(11), 1974, 643-644.
• [8] Fitzpatrick, S., Meertens, L., "Experiments on dense graphs with a stochastic, peer-to-peer colorer", Proc. AAAI-02 Workshop on Probabilistic Approaches in Search, 2002, 24-28.
• [9] Gosti, G.: Resolving CSP with Naming Games. 24th International Conference on Logic Programming, (M. Garcia de la Banda, E. Pontelli, Eds.) LNCS, vol. 5366, Springer, Heidelberg, Germany, 2008, 807-808.
• [10] Grinstead, C. M., Snell, J. L.: Introduction to Probability, AmericanMathematics Society, Providence, USA, 2003.
• [11] Komarova, N. L., Jameson, K. A., Narens, L.: Evolutionary Models of Color Categorization Based on Discrimination. Journal of Mathematical Psychology, 51, 2007, 359-382.
• [12] Mackworth, A. K.: Constraint satisfaction. Encyclopedia of AI,(Shapiro, S. C. ed.) 2nd ed., vol. 1, Wiley, New York, 1992, 285-293.
• [13] Montanari, U.: Networks of constraints: Fundamental properties and application to picture processing. Information Sciences, Vol. 7, 1974, 95-132.
• [14] Nowak, M. A., Plotkin, J. B., Krakauer, J. D.: The Evolutionary Language Game. Journal of Theoretical Biology, Sep. 21;200(2), 1999, 147-162
• [15] Nowak, M.A., Komarova, N. L., Niyogi, P.: Computational and Evolutionary Aspects of Language. Nature, 417, 2002, 611-617.
• [16] Ross, S. M.: Introduction to Probability Models. 9th ed. Accademic Press, Providence, USA, 2007.
• [17] Steels, L.: Self-Organizing Vocabularies. Artificial Life V: Proceeding of the Fifth International Workshop on the Synthesis and Simulation of Living Systems (Langton, C. and Shimohara, T., eds.), The MIT Press, Cambridge,MA, 1997, 179-184.
• [18] Sipper, M.: Co-evolving Non-Uniform Cellular Automata to Perform Computations. Physica D, 92, 1996, 193-208.
• [19] Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge, UK, 2005.
• [20] Yokoo, M., Katsutoshi H.: Algorithms For Distributed Constraint Satisfaction: A Review. Autonomous Agents and Multi-Agent Systems, Vol.3, No.2, 2000, 198-212.
• [21] Zhang, W., Wang, G., Xing, Z.: Distributed Stochastic Search and Distributed Breakout: Properties, Comparison and Applications to Constraint Optimization Problems in Sensor Networks. Artificial Intelligence, Special issue: Distributed constraint satisfaction, Volume 161, Issue 1-2, 2005, 55-87.