Arrow Research search

Author name cluster

Keith Decker

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers
2 author rows

Possible papers

15

JAAMAS Journal 2026 Journal Article

Coordinating Mutually Exclusive Resources using GPGP

  • Keith Decker
  • Jinjiang Li

Abstract Hospital Patient Scheduling is an inherently distributed problem because of the way real hospitals are organized. As medical procedures have become more complex, and their associated tests and treatments have become interrelated, the current ad hoc patient scheduling solutions have been observed to break down. We propose a multi-agent solution using the Generalized Partial Global Planning (GPGP) approach that preserves the existing human organization and authority structures, while providing better system-level performance (increased hospital unit throughput and decreased patient stay time). To do this, we extend GPGP with a new coordination mechanism to handle mutually exclusive resource relationships. Like the other GPGP mechanisms, the new mechanism can be applied to any problem with the appropriate resource relationship. We evaluate this new mechanism in the context of the hospital patient scheduling problem, and examine the effect of increasing interrelations between tasks performed by different hospital units.

Details DOI

AAMAS Conference 2010 Conference Paper

Coordination for Uncertain Outcomes using Distributed Neighbor Exchange

  • James Atlas
  • Keith Decker

Coordination of agent activites in non-deterministic, distributed environments is computationally difficult. Distributed Constraint Optimization (DCOP) provides a rich framework for modeling such multi-agent coordination problems, but existing representations, problem domains, and techniques for DCOP focus on small ($<$100 variables), deterministic solutions. We present a novel approach to DCOP for large-scale applications that contain uncertain outcomes. These types of real-time domains require distributed, scalable algorithms to meet difficult bounds on computation and communication time. To achieve this goal, we develop a new distributed neighbor exchange algorithm for DCOPs that scales to problems involving hundreds of variables and constraints and offers faster convergence to high quality solutions than existing DCOP algorithms. In addition, our complete solution includes new techniques for dynamic distributed constraint optimization and uncertainty in constraint processing. We validate our approach using test scenarios from the DARPA Coordinators program and show that our solution is very competitive with existing approaches.

PDF

AAMAS Conference 2007 Conference Paper

A Complete Distributed Constraint Optimization Method For Non-Traditional Pseudotree Arrangements

  • James Atlas
  • Keith Decker

Distributed Constraint Optimization (DCOP) is a general framework that can model complex problems in multi-agent systems. Several current algorithms that solve general DCOP instances, including ADOPT and DPOP, arrange agents into a traditional pseudotree structure. We introduce an extension to the DPOP algorithm that handles an extended set of pseudotree arrangements. Our algorithm correctly solves DCOP instances for pseudotrees that include edges between nodes in separate branches. The algorithm also solves instances with traditional pseudotree arrangements using the same procedure as DPOP.

PDF

ICAPS Conference 2003 Conference Paper

A Multi-Agent System-driven AI Planning Approach to Biological Pathway Discovery

  • Salim Khan
  • William Gillis
  • Carl J. Schmidt
  • Keith Decker

As genomic and proteomic data is collected from highthroughput methods on a daily basis, subcellular components are identified and their in vitro behavior is characterized. However, much less is known of their in vivo activity because of the complex subcellular milieu they operate within. A component’s milieu is determined by the biological pathways it participates in, and hence, the mechanisms by which it is regulated. We believe AI planning technology provides a modeling formalism for the task of biological pathway discovery, such that hypothetical pathways can be generated, queried and qualitatively simulated. The task of signal transduction pathway discovery is re-cast as a planning problem, one in which the initial and final states are known and cellular processes captured as abstract operators that modify the cellular environment. Thus, a valid plan that transforms the initial state into a goal state is a hypothetical pathway that prescribes the order of signaling events that must occur to effect the goal state. The planner is driven by data that is stored within a knowledge base and retrieved from heterogeneous sources (including gene expression, protein-protein interaction and literature mining) by a multi-agent information gathering system. We demonstrate the combined technology by translating the well-known EGF pathway into the planning formalism and deploying the Fast-Forward planner to reconstruct the pathway directly from the knowledge base.

Details

AAAI Conference 1993 Conference Paper

A One-Shot Dynamic Coordination Algorithm for Distributed Sensor Networks

  • Keith Decker

This paper presents a simple, fast coordination algorithm for the dynamic reorganization of agents in a distributed sensor network. Dynamic reorganization is a technique for adapting to the current local problemsolving situation that can both increase expected system performance and decrease the variance in performance. We compare our dynamic organization algorithm to a static algorithm with lower overhead. ‘ Oneshot’ refers to the fact that the algorithm only uses one meta-level communication action. The other theme of this paper is our methodology for analyzing complex control and coordination issues without resorting to a handful of single-instance examples. Using a general model that we have developed of distributed sensor network environments [Decker and Lesser, 1993a], we present probabilistic performance bounds for our algorithm given any number of agents in any environment that fits our assumptions. This model also allows us to predict exactly in what situations and environments the performance benefits of dynamic reorganization outweigh the overhead.

PDF Details

IJCAI Conference 1993 Conference Paper

An Approach to Analyzing the Need for Meta-Level Communication

  • Keith Decker
  • Victor Lesser

This paper presents an analysis of static and dynamic organizational structures for naturally distributed, homogeneous, cooperative problem solving environments, exemplified by distributed sensor networks. We first show how the performance of any static organization can be statistically described, and then show under what conditions dynamic organizations do better and worse than static ones. Finally, we show how the variance in the agents' performance leads to uncertainty about whether a dynamic organization will perform better than a static one given only agent a priori expectations. In these cases, we show when meta-level communication about the actual state of problem solving will be useful to agents in constructing a dynamic organizational structure that outperforms a static one. Viewed in its entirety, this paper also presents a methodology for answering questions about the design of distributed problem solving systems by analysis and simulation of the characteristics of a complex environment rather than by relying on single-instance examples.

PDF

UAI Conference 1985 Conference Paper

Selecting Uncertainty Calculi and Granularity: An Experiment in Trading-off Precision and Complexity

  • Piero P. Bonissone
  • Keith Decker

The management of uncertainty in expert systems has usually been left to ad hoc representations and rules of combinations lacking either a sound theory or clear semantics. The objective of this paper is to establish a theoretical basis for defining the syntax and semantics of a small subset of calculi of uncertainty operating on a given term set of linguistic statements of likelihood. Each calculus is defined by specifying a negation, a conjunction and a disjunction operator. Families of Triangular norms and conorms constitute the most general representations of conjunction and disjunction operators. These families provide us with a formalism for defining an infinite number of different calculi of uncertainty. The term set will define the uncertainty granularity, i.e. the finest level of distinction among different quantifications of uncertainty. This granularity will limit the ability to differentiate between two similar operators. Therefore, only a small finite subset of the infinite number of calculi will produce notably different results. This result is illustrated by two experiments where nine and eleven different calculi of uncertainty are used with three term sets containing five, nine, and thirteen elements, respectively. Finally, the use of context dependent rule set is proposed to select the most appropriate calculus for any given situation. Such a rule set will be relatively small since it must only describe the selection policies for a small number of calculi (resulting from the analyzed trade-off between complexity and precision).

Details