Using additional information in DisCSPs search Academic Article uri icon


  • Abstract. A method of volunteering information during asynchronous search on DisCSPs is presented. The meeting scheduling problem (MSP) is formulated as a distributed search problem. In order to implement asynchronous backtracking (ABT) for the MSP, a multi- variable version of ABT is described. Agents participate in multiple meetings, where each meeting is represented by a variable that needs to be assigned a time-slot. Assignments are constrained by arrival-time constraints, since meetings take place in different locations. All constraints are local to their agents. Additional information is in the form of Nogoods. During search for a consistent schedule for all meetings, agents can generate and send additional Nogoods to those sent by the ABT algorithm. When additional Nogoods are sent, the efficiency of asynchronous backtracking is enhanced. This effect grows with the number …

publication date

  • September 1, 2004