Welcome to the InfoSci Platform
A Multi-Agent Temporal Constraint Satisfaction System Based on Allen's Interval Algebra and Probabilities

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

Elhadi Shakshuki, André Trudel, Yiqing Xu
Copyright: © 2009 |Pages: 21
ISBN13: 9781605666181|ISBN10: 1605666181|ISBN13 Softcover: 9781616925079|EISBN13: 9781605666198
DOI: 10.4018/978-1-60566-618-1.ch004
Cite Chapter Cite Chapter

MLA

Shakshuki, Elhadi, et al. "A Multi-Agent Temporal Constraint Satisfaction System Based on Allen's Interval Algebra and Probabilities." Agent Technologies and Web Engineering: Applications and Systems, edited by Ghazi I. Alkhatib and David C. Rine, IGI Global, 2009, pp. 56-76. https://doi.org/10.4018/978-1-60566-618-1.ch004

APA

Shakshuki, E., Trudel, A., & Xu, Y. (2009). A Multi-Agent Temporal Constraint Satisfaction System Based on Allen's Interval Algebra and Probabilities. In G. Alkhatib & D. Rine (Eds.), Agent Technologies and Web Engineering: Applications and Systems (pp. 56-76). IGI Global. https://doi.org/10.4018/978-1-60566-618-1.ch004

Chicago

Shakshuki, Elhadi, André Trudel, and Yiqing Xu. "A Multi-Agent Temporal Constraint Satisfaction System Based on Allen's Interval Algebra and Probabilities." In Agent Technologies and Web Engineering: Applications and Systems, edited by Ghazi I. Alkhatib and David C. Rine, 56-76. Hershey, PA: IGI Global, 2009. https://doi.org/10.4018/978-1-60566-618-1.ch004

Export Reference

Mendeley
Favorite

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.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.