Heterogeneous active agents, III: Polynomially implementable agents

Thomas Eiter, V. S. Subrahmanian, T. J. Rogers

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


In `Heterogeneous active agents, I', two of the authors have introduced techniques to build agents on top of arbitrary data structures, and to `agentize' new/existing programs. They provided a series of successively more sophisticated semantics for such agent systems, and showed that as these semantics become epistemically more desirable, a computational price may need to be paid. In this paper, we identify a class of agents that are called weakly regular - this is done by first identifying a fragment of agent programs called weakly regular agent programs (WRAPs for short). It is shown that WRAPs are definable via three parameters - checking for a property called `safety', checking for a property called `conflict-freedom' and checking for a `deontic stratifiability' property. Algorithms for each of these are developed. A weakly regular agent is then defined in terms of these concepts, and a regular agent is one that satisfies an additional boundedness property. We then describe a polynomial algorithm that computes (under suitable assumptions) the reasonable status set semantics of regular agents - this semantics was identified by Eiter et al. (1999) as being epistemically most desirable. Though this semantics is coNP-complete for arbitrary agent programs, it is polynomially computable via our algorithm for regular agents. Finally, we describe our implementation architecture and provide details of how we have implemented RAPs, together with experimental results.

Original languageEnglish (US)
Pages (from-to)107-167
Number of pages61
JournalArtificial Intelligence
Issue number1
StatePublished - 2000
Externally publishedYes

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Heterogeneous active agents, III: Polynomially implementable agents'. Together they form a unique fingerprint.

Cite this