Browsing by Author "Dix, Juergen"

Now showing 1 - 8 of 8
  • No Thumbnail Available
    Item
    Explaining Updates by minimal sums
    (1999-09-11) Dix, Juergen; Schlechta, Karl
    Human reasoning about developments of the world involves always an assumption of \emph{inertia}. We discuss two approaches for formalizing such an assumption, based on the concept of an \emph{explanation}: \emph{(1)} there is a general preference relation given on the set of all explanations, \emph{(2)} there is a notion of a \emph{distance} between models and explanations are \emph{preferred} if their sum of distances is minimal. We show exactly under which conditions the converse is true as well and therefore both approaches are equivalent modulo these conditions. Our main result is a general representation theorem in the spirit of Kraus, Lehmann and Magidor. Also cross-referenced as UMIACS-TR-99-47
  • No Thumbnail Available
    Item
    A General Theory of Confluent rewriting Systems for Logic Programming and its Applications
    (1999-09-11) Dix, Juergen; Osorio, Mauricio
    Recently, Brass and Dix showed (\emph{Journal of Automated Reasoning} \textbf{20(1)}, 1998) that the wellfounded semantics WFS can be defined as a confluent calculus of transformation rules. This lead not only to a simple extension to disjunctive programs (\emph{Journal of Logic Programming} \textbf{38(3)}, 1999), but also to a new computation of the wellfounded semantics which is \emph{linear} for a broad class of programs. We take this approach as a starting point and generalize it considerably by developing a general theory of \emph{Confluent LP-Systems} $\cfs$. Such a system $\cfs$ is a rewriting system on the set of all logic programs over a fixed signature $\Lang$ and it induces in a natural way a canonical semantics. Moreover, we show four important applications of this theory: \emph{(1) most of the well-known semantics are induced by confluent LP-systems}, \emph{(2) there are many more transformation rules that lead to confluent LP-systems}, \emph{(3) semantics induced by such systems can be used to model aggregation}, \emph{(4) the new systems can be used to construct interesting counterexamples to some conjectures about the space of well-behaved semantics}. Also cross-referenced as UMIACS-TR-99-46
  • Thumbnail Image
    Item
    IMPACTing SHOP: Foundations for integrating HTN Planning and Multi-Agency
    (2000-02-08) Munoz-Avila, Hector; Dix, Juergen; Nau, Dana S.; Cao, Yue
    In this paper we describe a formalism for integrating the SHOP HTN planning system with the IMPACT multi-agent environment. Our formalism provides an agentized adaptation of the SHOP planning algorithm that takes advantage of IMPACT's capabilities for interacting with external agents, performing mixed symbolic/numeric computations, and making queries to distributed, heterogeneous information sources (such as arbitrary legacy and/or specialized data structures or external databases). We show that this agentized version of SHOP will preserve soundness and completeness if certain conditions are met. (This technical report is the updated version of CS-TR-4085) (Also cross-referenced as UMIACS-TR-2000-02)
  • No Thumbnail Available
    Item
    Meta Agent Programs
    (1999-09-11) Dix, Juergen; Subrahmanian, V.S.; Pick, George
    There are numerous applications where an agent \aga needs to reason about the beliefs of another agent, as well as about the actions that other agents may take. In Eiter/Subrahmanian/Pick the concept of an agent program is introduced, and a language within which the operating principles of an agent can be declaratively encoded on top of imperative data structures is defined. In this paper we first introduce certain belief data structures that an agent needs to maintain. Then we introduce the concept of a \emph{Meta Agent Program} (\map), that extends the framework of Eiter/Subrahmanian/Pick, so as to allow agents to perform metareasoning. We build a formal semantics for \map{s}, and show how this semantics supports not just beliefs agent a may have about agent b's state, but also beliefs about agents b's beliefs about agent c's actions, beliefs about b's beliefs about agent c's state, and so on. Finally, we provide a translation that takes any \map as input and converts it into an agent program such that there is a one-one correspondence between the semantics of the \map and the semantics of the resulting agent program. This correspondence allows an implementation of \map{s} to be built on top of an implementation of agent programs. Also cross-referenced as UMIACS-TR-99-49
  • Thumbnail Image
    Item
    Meta Agent Programs
    (1998-10-15) Dix, Juergen; Subrahmanian, V. S.; Pick, George
    There are numerous applications where one agent a needs to reason about the beliefs of another agent, as well as about the actions that other agents may take. Eiter et. al. introduced the concept of an agent program, and provided a language within which the operating principles of an agent could be declaratively encoded on top of imperative data structures. We first introduce certain belief data structures that an agent needs to maintain. Then we introduce the concept of a "Meta Agent Program" (MAP), that extends the Eiter et. al. framework, so as to allow agents to peform metareasoning. We build a formal semantics for MAPs, and show how this semantics supports not just beliefs agent a may have about agent b's state, but also beliefs about agents b's beliefs about agent c's actions, beliefs about b's beliefs about agent c's state, and so on. Finally, we provide a translation that takes any MAP as input and converts it into an agent program such that there is a one-one correspondence between the semantics of the MAP and the semantics of the resulting agent program. This correspondence allows an implementation of MAPs to be built on top of an implementation of agent programs. (Also cross-referenced as UMIACS-TR-98-43)
  • No Thumbnail Available
    Item
    Nonmonotonic Reasoning: Towards efficient calculi and implementations
    (1999-09-11) Dix, Juergen; Furbach, Ulrich; Niemelae, Ilkka
    In this paper we do not want to give a detailed overview of the various formalizations of nonmonotonic reasoning that have evolved (those can be found in various textbooks), but we want to give an overview of the main computational techniques and methods leading to implementions of nonmonotonic reasoning. We first introduce the main nonmonotonic logics: \emph{Default Logic}, \emph{Circumscription} and \emph{Autoepistemic Logic}. We also consider the abstract approach of Kraus, Lehmann and Magidor to associate with any reasoning system an \emph{abstract consequence relation}. Then we investigate universal methods for computing in general nonmonotonic logics. We do this with a special eye on the underlying complexity and show how this lead to automated theorem proving in such logics. Finding efficient computation mechanisms for the logics introduced in the former section is the aim of the next Section. There we consider techniques that originated from automated reasoning in first-order predicate calculus. We depict how these techniques can be applied for disjunctive logic programming with programs with variables but only limited use of negation. In particular, we handle \ie{GCWA} as a basis for nonmonotonic negation therein. We then give a declarative overview on nonmonotonicity in logic programming. We introduce (nonmonotonic) semantics of logic programs with negation and disjunction, notably the well-founded and the stable semantics and their extensions to programs containing disjunction--- they constitute the most important semantics and are in close relation to the logics introduced in the next Section. While in we considered in a former section techniques that can be successfully applied for programs with variables and only limited use of negation, we also treat propositional programs with full negation and disjunction. In particular, we provide implementations of \mbox{D-WFS}\Index{D-WFS} and \ie{D-ST ABLE} in polynomial space. We end with a section where we consider the problem of finding good benchmarks to test and compare nonmonotonic systems against. Also cross-referenced as UMIACS-TR-99-48
  • Thumbnail Image
    Item
    Planning in a Multi-Agent Environment: Theory and Practice
    (2002-02-19) Dix, Juergen; Munoz-Avila, Hector; Nau, Dana S.; Zhang, Lingling
    We give the theoretical foundations and empirical evaluation of a planning agent, SHOP, performing \htn planning in a multi-agent environment. SHOP is based on \ashop, an agentized version of the original SHOP \htn planning algorithm, and is integrated in the IMPACT multi-agent environment. We ran several experiments involving accessing various distributed, heterogeneous information sources, based on simplified versions of noncombatant evacuation operations, NEO's. As a result, we noticed that in such realistic settings the time spent on communication (including network time) is orders of magnitude higher than the actual inference process. This has important consequences for optimizations of such planners. Our main results are: (1) using NEO's as new, more realistic benchmarks for planners acting in an agent environment, and (2) a memoization mechanism implemented on top of SHOP, which improves the overall performance a lot. (Also UMIACS-TR-2002-13)
  • Thumbnail Image
    Item
    Probabilistic Agent Programs
    (1999-10-22) Dix, Juergen; Nanni, Mirco; Subrahmanian, VS
    Agents are small programs that autonomously take actions based on changes in their environment or ``state.'' Over the last few years, there have been an increasing number of efforts to build agents that can interact and/or collaborate with other agents. In one of these efforts, Eiter, Subrahmanian amd Pick (AIJ, 108(1-2), pages 179-255) have shown how agents may be built on top of legacy code. However, their framework assumes that agent states are completely determined, and there is no uncertainty in an agent's state. Thus, their framework allows an agent developer to specify how his agents will react when the agent is 100\% sure about what is true/false in the world state. In this paper, we propose the concept of a \emph{probabilistic agent program} and show how, given an arbitrary program written in any imperative language, we may build a declarative ``probabilistic'' agent program on top of it which supports decision making in the presence of uncertainty. We provide two alternative semantics for probabilistic agent programs. We show that the second semantics, though more epistemically appealing, is more complex to compute. We provide sound and complete algorithms to compute the semantics of \emph{positive} agent programs. (Also cross-referenced as UMIACS-TR-99-50)