Constraint satisfaction as a tool for modeling and checking feasibility of multiagent commitments

摘要

Commitments are being used to specify interactions among autonomous agents in multiagent systems. Various formalizations of commitments have shown their strength in representing and reasoning on multiagent interactions. These formalizations mostly study commitment lifecycles, emphasizing fulfillment of a single commitment. However, when multiple commitments coexist, fulfillment of one commitment may have an effect on the lifecycle of other commitments. Since agents generally participate in more than one commitment at a time, it is important for an agent to determine whether it can honor its commitments. These commitments may be the existing commitments of the agent as well as any prospective commitments that the agent plans to participate in. To address this, we develop the concept of commitment feasibility, i.e., whether it is possible for an agent to fulfill a set of commitments all together. To achieve this we generalize the fulfillment of a single commitment to the feasibility of a set of commitments. We then develop a solid method to determine commitment feasibility. Our method is based on the transformation of feasibility into a constraint satisfaction problem and use of constraint satisfaction techniques to come up with a conclusion. We show soundness and completeness of our method and illustrate its applicability over realistic cases.