1,721,064 research outputs found
How to progress a database III
No full textIn a seminal paper, Lin and Reiter introduced a model-theoretic definition for the progression of a basic action theory in the situation calculus, and proved that it implies the intended properties. They also showed that this definition comes with a strong negative result, namely that for certain cases first-order logic is not expressive enough to correctly characterize the progressed theory and second-order axioms are necessary. However, they also considered an alternative simpler definition according to which the progressed theory is always first-order definable. They conjectured that this alternative definition is incorrect in the sense that the progressed theory is too weak and may sometimes lose information. This conjecture and the status of the definability of progression in first-order logic has remained open since. In this paper we present two significant results about this alternative definition of progression. First, we prove the Lin and Reiter conjecture by presenting a case where the progressed theory indeed does lose information, thus closing a question that has remained open for more than ten years. Second, we prove that the alternative definition is nonetheless correct for reasoning about a large class of sentences, including some that quantify over situations. (C) 2012 Elsevier B.V. All rights reserved
Incremental Execution of Guarded Theories
No full text
When it comes to building controllers for robots or agents, high level programming languages like
Golog
and
ConGolog
offer a useful compromise between planning-based approaches and low-level robot programming. However, two serious problems typically emerge in practical implementations of these languages: how to evaluate test in a program efficiently enough in an open-world setting, and how to make appropiate nondeterministic choices while avoiding full lookahead. Recent proposals in the literature suggest that one could tackle the first problem by exploiting sensing information, and tackle the second by specifying the amount of lookahead allowed explicitly in the program. In this paper, we combine these two ideas and demonstrate their power by presenting an interpreter, written in Prolog, for a variant of
Golog
that is suitable for efficiently operating in open-world setting by exploiting sensing and bounded lookahead.
</jats:p
Reasoning About Concurrent Execution, Prioritized Interrupts, and Exogenous Actions in the Situation Calculus
No full textAs an alternative to planning, an approach to high-level agent control based on concurrent program execution is considered. A formal definition in the situation calculus of such a programming language is presented and illustrated with a detailed example. The language includes facilities for prioritizing the concurrent execution, interrupting the execution when certain conditions become true, and dealing with exogenous actions. The language differs from other procedural formalisms for concurrency in that the initial state can be incompletely specified and the primitive actions can be userdefined by axioms in the situation calculus. When it comes to providing high-level control for robots or other agents in dynamic and incompletely known worlds, approaches based on plan synthesis may end up being too demanding computationally in all but simple settings. An alternative approach that is showing promise is that of high-level program execution [8]. The idea, roughly, is that instead of searc..
An Incremental Interpreter for High-Level Programs with Sensing
No full textLike classical planning, the execution of high-level agent programs requires a reasoner to look all the way to a final goal state before even a single action can be taken in the world. This deferral is a serious problem in practice for large programs. Furthermore, the problem is compounded in the presence of sensing actions which provide necessary information, but only after they are executed in the world. To deal with this, we propose (characterize formally in the situation calculus, and implement in Prolog) a new incremental way of interpreting such high-level programs and a new high-level language construct, which together allow much more control to be exercised over when actions can be executed. We argue that such a scheme leads to a practical way to deal with large agent programs containing both nondeterminism and sensing
ConGolog, a concurrent programming language based on the situation calculus: foundations
No full textAs an alternative to planning, an approach to high-level agent control based on concurrent program execution is considered. The language includes facilities for prioritizing the concurrent execution, interrupting the execution when certain conditions become true, and dealing with exogenous actions. The language differs from other procedural formalisms for concurrency in that the initial state can be incompletely specified and the primitive actions can be user-defined by axioms in the situation calculus. In a companion paper, a formal definition in the situation calculus of such a programming language is presented and illustrated with detailed examples. In this paper, the mathematical properties of the programming language are explored. 1 Introduction When it comes to providing high-level control for robots or other agents in dynamic and incompletely known worlds, approaches based on plan synthesis may end up being too demanding computationally in all but simple settings. An alternativ..
IndiGolog: A High-Level Programming Language for Embedded Reasoning Agents
No full textIndiGolog is a programming language for autonomous agents that sense their environment and do planning as they operate. Instead of classical planning, it supports high-level program execution. The programmer provides a high-level nondeterministic program involving domain-specific actions and tests to perform the agent’s tasks. The IndiGolog interpreter then reasons about the preconditions and effects of the actions in the program to find a legal terminating execution. To support this, the programmer provides a declarative specification of the domain (i.e., primitive actions, preconditions and effects, what is known about the initial state) in the situation calculus. The programmer can control the amount of nondeterminism in the program and how much of it is searched over. The language is rich and supports concurrent programming. Programs are executed online together with sensing the environment and monitoring for events, thus supporting the development of reactive agents. We discuss the language, its implementation, and applications that have been realized with it
Cognitive Robotics
Get PDFThis chapter is dedicated to the memory of Ray Reiter. It is also an overview of cognitive robotics, as we understand it to have been envisaged by him.1 Of course, nobody can control the use of a term or the direction of research. We apologize in advance to those who feel that other approaches to cognitive robotics and related problems are inadequately
represented here
- …
