Contemporary cost-based goal-recognition assumes rationality: that observed behaviour is more or less optimal. Probabilistic goal recognition systems, however, explicitly depend on some degree of sub-optimality to generate probability distributions. We show that, even when an observed agent is only slightly irrational (sub-optimal), state-of-the-art systems produce counter-intuitive results (though these may only become noticeable when the agent is highly irrational). We provide a definition of rationality appropriate to situations where the ground truth is unknown, define a rationality measure (RM) that quantifies an agent’s expected degree of sub-optimality, and define an innovative self-modulating probability distribution formula for goal recognition. Our formula recognises sub-optimality and adjusts its level of confidence accordingly, thereby handling irrationality—and rationality—in an intuitive, principled manner. Building on that formula, moreover, we strengthen a previously published result, showing that “single-observation” recognition in the path-planning domain achieves identical results to more computationally expensive techniques, where previously we claimed only to achieve equivalent rankings though values differed.

We consider the problem of reaching a propositional goal condition in fully-observable non-deterministic (FOND) planning under a general class of fairness assumptions that are given explicitly. The fairness assumptions are of the form A/B and say that state trajectories that contain infinite occurrences of an action a from A in a state s and finite occurrence of actions from B, must also contain infinite occurrences of action a in s followed by each one of its possible outcomes. The infinite trajectories that violate this condition are deemed as unfair, and the solutions are policies for which all the fair trajectories reach a goal state. We show that strong and strong-cyclic FOND planning, as well as QNP planning, a planning model introduced recently for generalized planning, are all special cases of FOND planning with fairness assumptions of this form which can also be combined. FOND+ planning, as this form of planning is called, combines the syntax of FOND planning with some of the versatility of LTL for expressing fairness constraints. A new planner is implemented by reducing FOND+ planning to answer set programs, and the performance of the planner is evaluated in comparison with FOND and QNP planners, and LTL synthesis tools.

Goal recognition is the problem of determining an agent’s intent by observing her behaviour. Contemporary solutions for general task-planning relate the probability of a goal to the cost of reaching it. We adapt this approach to goal recognition in the strict context of path-planning. We show (1) that a simpler formula provides an identical result to current state-of-the-art in less than half the time under all but one set of conditions. Further, we prove (2) that the probability distribution based on this technique is independent of an agent’s past behaviour and present a revised formula that achieves goal recognition by reference to the agent’s starting point and current location only. Building on this, we demonstrate (3) that a Radius of Maximum Probability (i.e., the distance from a goal within which that goal is guaranteed to be the most probable) can be calculated from relative cost-distances between the candidate goals and a start location, without needing to calculate any actual probabilities. In this extended version of earlier work, we generalise our framework to the continuous domain and discuss our results, including the conditions under which our findings can be generalised back to goal recognition in general task-planning.

We 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.

This work proposes a novel high-level paradigm, agent planning programs, for modeling agents behavior, which suitably mixes automated planning with agent-oriented programming. Agent planning programs are finite-state programs, possibly containing loops, whose atomic instructions consist of a guard, a maintenance goal, and an achievement goal, which act as precondition-invariance-postcondition assertions in program specification. Such programs are to be executed in possibly nondeterministic planning domains and their execution requires generating plans that meet the goals specified in the atomic instructions, while respecting the program control flow. In this paper, we define the problem of automatically synthesizing the required plans to execute an agent planning program, propose a solution technique based on model checking of two-player game structures, and use it to characterize the worst-case computational complexity of the problem as EXPTIME-complete. Then, we consider the case of deterministic domains and propose a different technique to solve agent planning programs, which is based on iteratively solving classical planning problems and on exploiting goal preferences and plan adaptation methods. Finally, we study the effectiveness of this approach for deterministic domains through an experimental analysis on well-known planning domains.

The Belief Desire Intention (BDI) agent paradigm provides a powerful basis for developing complex systems based on autonomous intelligent agents. These agents have, at any point in time, a set of intentions encoding the various tasks the agent is working on. Despite its importance, the problem of selecting which intention to progress at any point in time has received almost no attention and has been mostly left to the programmer to resolve in an application-dependent manner. In this paper, we implement and evaluate two domain-independent intention selection mechanisms based on the ideas of enablement checking and low coverage prioritisation. Through a battery of automatically generated synthetic tests and one real program, we compare these with the commonly used intention selection mechanisms of First-In-First-Out (FIFO) and Round Robin (RR). We found that enablement checking, which is incorporated into low coverage prioritisation, is never detrimental and provides substantial benefits when running vulnerable programs in dynamic environments. This is a significant finding as such a check can be readily applied to FIFO and RR, giving an extremely simple and effective mechanism to be added to existing BDI frameworks. In turn, low coverage prioritisation provides a significant further benefit.

The 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.

The behavior composition problem involves automatically building a controller that is able to realize a desired, but unavailable, target system (e.g., a house surveillance) by suitably coordinating a set of available components (e.g., video cameras, blinds, lamps, a vacuum cleaner, phones, etc.) Previous work has almost exclusively aimed at bringing about the desired component in its totality, which is highly unsatisfactory for unsolvable problems. In this work, we develop an approach for approximate behavior composition without departing from the classical setting, thus making the problem applicable to a much wider range of cases. Based on the notion of simulation, we characterize what a maximal controller and the “closest” implementable target module (optimal approximation) are, and show how these can be computed using ATL model checking technology for a special case. We show the uniqueness of optimal approximations, and prove their soundness and completeness with respect to their imported controllers.

Agents are an important technology that have the potential to take over contemporary methods for analysing, designing, and implementing complex software. The Belief-Desire-Intention (BDI) agent paradigm has proven to be one of the major approaches to intelligent agent systems, both in academia and in industry. Typical BDI agent-oriented programming languages rely on user-provided “plan libraries” to achieve goals, and online context sensitive subgoal selection and expansion. These allow for the development of systems that are extremely flexible and responsive to the environment, and as a result, well suited for complex applications with (soft) real-time reasoning and control requirements. Nonetheless, complex decision making that goes beyond, but is compatible with, run-time context-dependent plan selection is one of the most natural and important next steps within this technology. In this paper we develop a typical BDI-style agent-oriented programming language that enhances usual BDI programming style with three distinguished features: declarative goals, look-ahead planning, and failure handling. First, an account that mixes both procedural and declarative aspects of goals is necessary in order to reason about important properties of goals and to decouple plans from what these plans are meant to achieve. Second, lookahead deliberation about the effects of one choice of expansion over another is clearly desirable or even mandatory in many circumstances so as to guarantee goal achievability and to avoid undesired situations. Finally, a failure handling mechanism, suitably integrated with both declarative goals and planning, is required in order to model an adequate level of commitment to goals, as well as to be consistent with most real BDI implemented systems.

IndiGolog isa 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 non-deterministic 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 a legal terminating execution. To support this, the programmer provides a declarative specication 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 non-determinism 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.

A recent trend in planning with incomplete information is to model the actions of a planning problem as nondeterministic transitions over the belief states of a planner, and to search for a plan that terminates in a desired goal state no matter how these transitions turn out. We show that this view of planning is fundamentally limited. Any plan that is successful by this criteria has an upper bound on the number of actions it can execute. Specifically, the account will not work when iterative plans are needed. We also show that by modifying the definition slightly, we obtain another account of planning that does work properly even for iterative plans. Although the argument is presented in an abstract form, we illustrate the issues using a simple concrete example.