Conference proceeding
On Modeling Multiagent Task Scheduling as a Distributed Constraint Optimization Problem
20TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, pp.1531-1536
01 Jan 2007
Abstract
This paper investigates how to represent and solve multiagent task scheduling as a Distributed Constraint Optimization Problem (DCOP). Recently multiagent researchers have adopted the C_TAEMS language as a standard for multiagent task scheduling. We contribute an automated mapping that transforms C_TAEMS into a DCOP. Further, we propose a set of representational compromises for C_TAEMS that allow existing distributed algorithms for DCOP to be immediately brought to bear on C_TAEMS problems. Next, we demonstrate a key advantage of a constraint based representation is the ability to leverage the representation to do efficient solving. We contribute a set of pre-processing algorithms that leverage existing constraint propagation techniques to do variable domain pruning on the DCOP. We show that these algorithms can result in 96% reduction in state space size for a given set of C_TAEMS problems. Finally, we demonstrate up to a 60% increase in the ability to optimally solve C_TAEMS problems in a reasonable amount of time and in a distributed manner as a result of applying our mapping and domain pruning algorithms.
Metrics
1 Record Views
Details
- Title
- On Modeling Multiagent Task Scheduling as a Distributed Constraint Optimization Problem
- Creators
- Evan A. Sultanik - Drexel UniversityPragnesh Jay Modi - Drexel Univ, Dept Comp Sci, Philadelphia, PA 19104 USAWilliam C. Regli - Drexel University
- Contributors
- M M Veloso (Editor)
- Publication Details
- 20TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, pp.1531-1536
- Conference
- 20TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 20th
- Publisher
- Ijcai-Int Joint Conf Artif Intell
- Number of pages
- 6
- Resource Type
- Conference proceeding
- Language
- English
- Identifiers
- 991019357775504721
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Web of Science research areas
- Computer Science, Artificial Intelligence
- Computer Science, Theory & Methods