1,720,992 research outputs found
An Adaptive Process Management System Implementation Based on Situatio Calculus, Indigolog and Classical Planning
No full textIn this paper, we introduce an adaptive Process Management System implementation that combines business process execution monitoring, unanticipated exception detection and automated resolution strategies leveraging on well-established formalisms developed for reasoning about actions in Artificial Intelligence, including the situation calculus, IndiGolog and classical planning. Such formalisms provide a natural framework for the formal specification of explicit mechanisms to model world changes and responding to anomalous situations, exceptions, exogenous events in an automated way during process execution
Two-player game structures for generalized planning and agent composition
No full textIn this paper, we review a series of agent behavior synthesis problems under full observability and nondeter-minism (partial controllability), ranging from conditional planning, to recently introduced agent planning programs, and to sophisticated forms of agent behavior compositions, and show that all of them can be solved by model checking two-player game structures. These structures are akin to transition systems/Kripke structures, usually adopted in model checking, except that they distinguish (and hence allow to separately quantify) between the actions/moves of two antagonistic players. We show that using them we can implement solvers for several agent behavior synthesis problems. Copyright © 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved
Path planning with Inventory-driven Jump-Point-Search
Get PDFIn many navigational domains the traversability of cells is conditioned on the path taken. This is often the case in video-games, in which a character may need to acquire a certain object (i.e., a key or a flying suit) to be able to traverse specific locations (e.g., doors or high walls). In order for non-player characters to handle such scenarios we present invJPS, an "inventory-driven" pathfinding approach based on the highly successful grid-based Jump-Point-Search (JPS) algorithm. We show, formally and experimentally, that the invJPS preserves JPS's optimality guarantees and its symmetry breaking advantages in inventory-based variants of game maps
Verifying congolog programs on bounded situation calculus theories
Get PDFWe address verification of high-level programs over situation calculus action theories that have an infinite object domain, but bounded fluent extensions in each situation. We show that verification of μ-calculus temporal properties against ConGolog programs over such bounded theories is decidable in general. To do this, we reformulate the transition seman- tics of ConGolog to keep the bindings of “pick variables” into a separate variable environment whose size is naturally bounded by the number of variables. We also show that for situation-determined ConGolog programs, we can compile away the program into the action theory itself without loss of generality. This can also be done for arbitrary programs, but only to check certain properties, such as if a situation is the result of a program execution, not for μ-calculus verification
Pruning and Preprocessing Methods for Inventory-Aware Pathfinding
No full textInventory-Aware Pathfinding is concerned with finding paths while taking into account that picking up items, e.g., keys, allow the character to unlock blocked pathways, e.g., locked doors. In this work we present a pruning method and a prepro-cessing method that can improve significantly the scalability of such approaches. We apply our methods to the recent approach of Inventory-Driven Jump-Point Search (InvJPS). First, we introduce InvJPS+ that allows to prune large parts of the search space by favoring short detours to pick up items, offering a trade-off between efficiency and optimality. Second, we propose a preprocessing step that allows to decide on runtime which items, e.g., keys, are worth using thus pruning potentially unnecessary items before the search starts. We show results for combinations of the pruning and preprocessing methods illustrating the best choices over various scenarios
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
Automatic behavior composition synthesis
No full textThe behavior composition problem amounts to realizing a virtual desired module (e.g., a surveillance agent system) by suitably coordinating (and re-purposing) the execution of a set of available modules (e.g., a video camera, vacuum cleaner, a robot, etc.). In particular, we investigate techniques to synthesize a controller implementing a fully controllable target behavior by suitably coordinating available partially controllable behaviors that are to execute within a shared, fully observable, but partially predictable (i.e., non-deterministic), environment. Both behaviors and environment are represented as arbitrary finite state transition systems. The technique we propose is directly based on the idea that the controller job is to coordinate the concurrent execution of the available behaviors so as to "mimic" the target behavior. To this end, we exploit a variant of the formal notion of simulation to formally capture the notion of "mimicking", and we show that the technique proposed is sound and complete, optimal with respect to computational complexity, and robust for different kind of system failures. In addition, we demonstrate that the technique is well suited for highly efficient implementation based on synthesis by model checking technologies, by relating the problem to that of finding a winning strategy in a special safety game and explaining how to actually solve it using an existing verification tool. © 2013 Elsevier B.V. All rights reserved
Making YAWL and SmartPM Interoperate: Managing Highly Dynamic Processes by Exploiting Automatic Adaptation Features
No full textIn the last years, the trade-off between flexibility and support has become a leading issue in workow technology. In this paper we show how an imperative modeling approach used to define stable and well-understood processes can be complemented by a modeling approach that enables automatic process adaptation and exploits planning techniques to deal with environmental changes and exceptions that may occur during process execution. To this end, we designed and implemented a Custom Service that allows the Yawl execution environment to delegate the execution of subprocesses and activities to the SmartPM execution environment, which is able to automatically adapt a process to deal with emerging changes and exceptions. We demonstrate the feasibility and validity of the approach by showing the design and execution of an emergency management process defined for train derailments
Fully Observable Non-deterministic Planning as Assumption-Based Reactive Synthesis
Get PDFWe contribute to recent efforts in relating two approaches to automatic synthesis, namely, automated planning and discrete reactive synthesis. First, we develop a declarative characterization of the standard “fairness” assumption on environments in non-deterministic planning, and show that strong-cyclic plans are correct solution concepts for fair environments. This complements, and arguably completes, the existing foundational work on non-deterministic planning, which focuses on characterizing (and computing) plans enjoying special “structural” properties, namely loopy but closed policy structures. Second, we provide an encoding suitable for reactive synthesis that avoids the naive exponential state space blowup. To do so, special care has to be taken to specify the fairness assumption on the environment in a succinct manner.Fil: D'ippolito, Nicolás Roque. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; ArgentinaFil: Rodriguez, Natalia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; ArgentinaFil: Sardina, Sebastian. RMIT University; Australi
- …
