Algorithms for distributed constraint satisfaction
When the agents interact, they need to satisfy several constraints to be able to execute actions.
This constraints are not easy to satisfy becausegenerally they turn into a trial and error exploration of the possibilities.
There are various algorithms to try to solve the Constraint satisfaction problems. Backtracking, Interactive Improvementand Consistency Algorithms. The general goal of this algorithms and Distributed Constraint satisfaction problems is to achieve a coherence or consistency among all the agents in the environment.Asynchronous backtracking algorithm uses priority status on agents and ensures that always finds a solution if exists, or terminates if no solution exists. By using mathematical induction we can be surethat any agent will not enter to an infinite loop. The agents communicate between them with messages.
Asynchronous weak/commitment search introduce an heuristic to reduce the risk of makingerroneous decisions. The priority of the agents now can be changed to be more flexible. This algorithm is also complete.
Distributed breakout algorithm a weight is defined for each constraint. in thisalgorithm 2 types of message are defined , the improve message is used to improve the evaluation value.
Extending on the definition of MAS, we found several methods to handle the multiple localvariables, satisfy several partial constraints, finding the optimal solution for the partial constraints and assign a level of importance to the constraints.
Adopt: Asynchronous Distributed ConstraintOptimization with quality guarantees
Distributed Constraint Optimization Problem provides a solution on how agents manages its decisions on the domain. This optimization provides methods and techniques tosolve real world application, and must have three important requirements to be meet, Local communication (adjacent agents) , Asynchronous operation agents and a method that provides quality/time...
Regístrate para leer el documento completo.