The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

Research Paper #798

Title:Spring-Based Negotiation for Conflict Resolution in Agv Scheduling
Authors:Huang,X; Hallam,JC
Date:Mar 1996
Presented:Presented at the IEEE International Conference on Systems, Man and Cybernetics, 1995
Abstract:Scheduling Problems can be solved by approaches from Distributed Artificial Intelligence (DAI). Negotiation is often taken as a powerful way of resolving conflicts between agents. In this paper, based on discussion of Kwa's negotiation model for solving AGV movement scheduling problems, we propose what we call a spring-based negotiation model to overcome the deficiencies in Kwa's model. We view a scheduling problem as a constraint satisfaction problem (CSP) and constraints are categorized into soft constraints and hard constraints. Hard constraints must be strictly satisfied and soft constraints can be relaxed but are expected to be satisfied as well as possible. We use springs to represent soft constraints. The scheduling problem is solved in a multiple negotiating agent system in which each agent is responsible for solving a local scheduling problem. Any local schedule is represented by a spring model. When one agent detects a situation in which its local schedule is in conflict with that of another agent, then it initiates a negotiation process during which conflicting agents exchange their information, commencing with proposals. A proposal consists of an intention and an explanation.

[Search These Pages] [DAI Home Page] [Comment]