An important aspect of multi agent systems are agent reasoning techniques for problem solving, either at the level of a single agent or at the level of distributed collaboration amongst multiple agents.
Constraint Satisfaction Problems (CSP) prove to be a generic framework which can be applied for modeling and solving a wide range of combinatorial applications as planning, scheduling and resource sharing in many practical domains such as transportation, production, mass marketing, network management and human resources management. Constraint satisfaction techniques provide efficient algorithms to prune search spaces and it is a paradigm for combinatorial problem solving. As a problem solving technology, constraint satisfaction problems framework is a reasoning technique. In this work we study constraint satisfaction techniques for solving and solution adaptation that can be applied to agent reasoning.
Most work in constraint satisfaction has focused on computing a solution to a given problem. In practice, it often happens that an existing solution needs to be modified to satisfy additional criteria or accommodate changes in the problem. For example, a schedule or plan might have to be adjusted when a resource is missing.
The concept of interchangeability characterizes symmetries among the problem entities and thus facilitates making local changes to CSP solutions. The first part of this work studies how the concept of interchangeability can define (provide) methods for solution adaptation. In general, interchangeability is only partial and thus localizes changes to sets of variables, which we call dependent sets. This study presents concepts for characterizing, and algorithms for computing, partial interchangeability in CSPs using the dependent sets. We present novel algorithms for generating the minimal dependent sets for a desired interchangeability, and the minimum thereof. Furthermore we define a new interchangeability concept, tuple interchangeability, which characterizes equivalent partial solutions in a CSP. We present algorithms for computing this new interchangeability concept and study its dependence on the problem structure. Based on dependent sets and interchangeable tuples, we develop techniques for adapting solutions in applications such as replanning, rescheduling, reconfiguration, etc., which are important techniques for agent-based reasoning.
