A Multi-Agent Temporal Constraint Satisfaction System Based on Allen's Interval Algebra and Probabilities

View Sample PDF

Author(s): Elhadi Shakshuki (Acadia University, Canada), André Trudel (Acadia University, Canada)and Yiqing Xu (Acadia University, Canada)
Copyright: 2009
Pages: 21
Source title: Agent Technologies and Web Engineering: Applications and Systems
Source Author(s)/Editor(s): Ghazi I. Alkhatib (The Hashemite University, Jordan)and David C. Rine (George Mason University, USA)
DOI: 10.4018/978-1-60566-618-1.ch004

Keywords: Computer Science & IT / Information Science Reference / Web Technologies / Web Technologies & Engineering

Purchase

View A Multi-Agent Temporal Constraint Satisfaction System Based on Allen's Interval Algebra and Probabilities on the publisher's website for pricing and purchasing information.

Abstract

Many real-world problems can be viewed and represented as a constraint satisfaction problem (CSP). In addition, many of these problems are distributed in nature. To this end, we combine agents with a special type of CSP called an Interval Algebra network (IA network). An IA network is a graph where each node represents an interval. Directed edges in the network are labelled with temporal interval relations. A probabilistic IA network has probabilities associated with the relations on the edges that can be used to capture preferences. A probabilistic IA agent (PIA-Agent) is assigned a probabilistic IA network. PIA-Agent’s networks are connected via edges. The overall goal is to make each PIA-Agent’s network consistent and optimal. Each PIA-Agent is independent and has sole control over its network. But, it must communicate and coordinate with other PIA-Agents when modifying or updating edges that are shared between two PIA-Agents. We present an algorithm which allows the PIA-Agents to collaboratively solve and recommend a temporal schedule. At the agent level, this schedule is optimal under the given local constraints. Although the global solution may not be optimal, we try to generate near optimal ones. Note that our distributed system is not centrally controlled. Our algorithm decides which PIA-Agent should be given an opportunity to update the solution next. Also, when a conflict is detected, the algorithm modifies the PIA-Agent execution order in order to deal with the inconsistency.

The IRMA Community

Research IRM

A Multi-Agent Temporal Constraint Satisfaction System Based on Allen's Interval Algebra and Probabilities

Purchase

Abstract

Related Content

IRMA Sponsors