LE3 .A278 2007

2007

Shakshuki, Elhadi
Trudel, Andre

Acadia University

Master of Science

Masters

Computer Science

Computer Science

Many real-world problems can be represented as a constraint satisfaction problem (CSP). In addition, many of these problems are distributed in nature. To this end, CSP techniques and multi-agent technology can be combined to solve these real-world problems. This thesis presents a multi-agent system based on a special type of CSP called Probabilistic Interval Algebra (PIA) networks to solve inherently distributed scheduling problems. A PIA network is a directed graph where each node represents a temporal interval, and the edges are labelled with constraints and probabilities between intervals. The proposed multi-agent system consists of probabilistic IA agents (PIA-Agents) that are assigned a PIA network. The main objective of each PIA-Agent is to make its network consistent and optimal. Each PIA-Agent has complete control and knowledge of its internal network. An algorithm is presented in this paper, which allows the PIA-Agents to collaboratively solve and recommend a temporal schedule which is optimal at the agent level under the given local constraints. The optimality of the global solution is not guaranteed. A natural application of our proposed system is a distributed scheduling system. The particular one chosen is a university example which involves a professor, student and secretary. Each has their own schedule and preferences. The goal of the example is to recommend a globally consistent solution which attempts to maximize the desires of the individual PIA-Agents.

The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.

https://scholar.acadiau.ca/islandora/object/theses:2860