How does one deal with the unexpected? Our world is full of surprises and we humans are often able to correctly identify a problem and respond appropriately. Consider a new driver encountering their first traffic circle; a student experiencing a hard drive failure in the middle of an assignment; an unexpected question being asked during a job interview. In situations where we have a goal (i.e., reach a destination or submit a completed assignment), we may need to alter our original plan when the unexpected occurs. Could we enable autonomous artificial intelligent agents to do the same?
A long standing area of artificial intelligence is the field of automated planning. The traditional planning problem is to generate a sequence of actions given a concrete, specific goal (e.g., I will be home at dinnertime) and a set of specific actions (e.g., drive-car, fill-gas-tank, walk, etc). Generating plans that are hopefully efficient and optimal from start to finish under different circumstances (e.g., delayed effects) is an active area of research. After a plan has been generated, and during the execution of the plan, the environment may change. For example, a robot retrieving packages in a warehouse may discover it has dropped its package. Or perhaps another robot has broken down due to a hardware failure and is blocking the path of this robot. How can a robot (or any A.I. agent) know something unexpected has happened without knowing all possible future failures?
Fundamental research on autonomy aims to find general approaches to solve this problem. One approach is to generate expectations: facts that should be true during different stages of a plan's execution. When an expectation is violated, a discrepancy occurs between the expected and perceived facts. A new trend in autonomy is to include goal reasoning capabilities. In the event of a failure, the original goal may no longer be warranted. Perhaps robust autonomous agents need to generate and change their goals in response to a changing environment.
Autonomous systems still have a long way to go and open research questions on autonomous systems remain. Funding agencies consistently seek new research on autonomy for diverse operations ranging from cybersecurity to military and vehicular autonomy. What will autonomous systems be like in the future? Will we achieve autonomous agents that can handle any situation they encounter?
- Dustin Dannenhauer
In this article we review the 2011 International Planning Competition. We give an overview of the history of the competition, discussing how it has developed since its first edition in 1998. The 2011 competition was run in three main separate tracks: the deterministic (classical) track; the learning track; and the uncertainty track. Each track proposed its own distinct set of new challenges and the participants rose to these admirably, the results of each track showing promising progress in each area. The competition attracted a record number of participants this year, showing its continued and strong position as a major central pillar of the international planning research community.
Complex, real-world domains require rethinking traditional approaches to AI planning. Planning and executing the resulting plans in a dynamic environment implies a continual approach in which planning and execution are interleaved, uncertainty in the current and projected world state is recognized and handled appropriately, and replanning can be performed when the situation changes or planned actions fail. Furthermore, complex planning and execution problems may require multiple computational agents and human planners to collaborate on a solution. In this article, we describe a new paradigm for planning in complex, dynamic environments, which we term distributed, continual planning (DCP). We argue that developing DCP systems will be necessary for planning applications to be successful in these environments.
In previous work we have shown that grounding, while used by most (if not all) modern state-of-the-art planners, is not necessary and is sometimes even undesirable. In this paper we extend this work and present a novel forward-chaining planner that does not require grounding and can solve problem instances that are too large for current planners to handle. We achieve this by exploiting equivalence relationships between objects whist constructing a lifted version of the relaxed planning graph (RPG) and extracting a relaxed plan. We compare our planner to FF and show that our approach consumes far less memory whist still being competitive. In addition we show that by not having to ground the domain we can solve much larger problem instances.
The paper addresses the problem of plan repair for tasks involving mandatory constraints on consumable and continuous resources, modeled as numeric fluents. The approach starts by proposing a new notion of numeric macro actions allowing to handle - as an extension to the classical macro action formulation - conditions and operations not only on the propositional fragment, but also on the numeric one. By reasoning directly on the current plan, the paper shows two techniques for selecting useful macro actions. Such macro actions, toghether with the original actions model, are then used by an off-the-shelf numeric planner for a faster plan repair task. To evaluate the techniques and the contribution of numeric macro actions, we experimented the approach on several numeric planning domains using Metric-FF as off-the-shelf planner.Results show that both strategies enhance the performance of the same planning system without macro actions. Even, one of the strategies turns out to be very competitive also with the specialized plan repair system LPG-ADAPT, both in terms of cpu-time, and stability of the repaired plan.
Recent advances in fully observable non-deterministic (FOND) planning have enabled new techniques for various applications, such as behaviour composition, among others. One key limitation of modern FOND planners is their lack of native support for conditional effects. In this paper we describe an extension to PRP, the current state of the art in FOND planning, that supports the generation of policies for domains with conditional effects and non-determinism. We present core modifications to the PRP planner for this enhanced functionality without sacrificing soundness and completeness. Additionally, we demonstrate the planner's capabilities on a variety of benchmarks that include actions with both conditional effects and non-deterministic outcomes. The resulting planner opens the door to models of greater expressivity, and does so without affecting PRP's efficiency.
In robotics and video games, one often discretizes continuous terrain into a grid with blocked and unblocked grid cells and then uses path-planning algorithms to find a shortest path on the resulting grid graph. This path, however, is typically not a shortest path in the continuous terrain. In this overview article, we discuss a path-planning methodology for quickly finding paths in continuous terrain that are typically shorter than shortest grid paths. Any-angle path-planning algorithms are variants of the heuristic path-planning algorithm A* that find short paths by propagating information along grid edges (like A*, to be fast) without constraining the resulting paths to grid edges (unlike A*, to find short paths).
Domain-independent optimal planning has seen important breakthroughs in recent years with the development of tractable and informative admissible heuristics, suitable for planners based on forward state-space search. These heuristics allow planners to optimally solve an important number of benchmark problems, including problems that are quite involved and difficult for the layman. In this paper we present a new admissible heuristic that is obtained from the state equation associated to the Petri-net representation of the planning problem. The new heuristic, that does not fall into one of the four standard classes, can be computed in polynomial time and is competitive with the current state of the art for optimal planning, as empirically demonstrated over a large number of problems, mainly because it often shows an improved quality-to-cost ratio. The new heuristic applies to SAS+ planning tasks with arbitrary non-negative action costs.
We provide a systematic analysis of levels of integration between discrete high-level reasoning and continuous low-level reasoning to address hybrid planning problems in robotics. We identify four distinct strategies for such an integration: (i) low-level checks are done for all possible cases in advance and then this information is used during plan generation, (ii) low-level checks are done exactly when they are needed during the search for a plan, (iii) first all plans are computed and then infeasible ones are filtered, and (iv) by means of replanning, after finding a plan, low-level checks identify whether it is infeasible or not; if it is infeasible, a new plan is computed considering the results of previous low- level checks. We perform experiments on hybrid planning problems in robotic manipulation and legged locomotion domains considering these four methods of integration, as well as some of their combinations. We analyze the usefulness of levels of integration in these domains, both from the point of view of computational efficiency (in time and space) and from the point of view of plan quality relative to its feasibility. We discuss advantages and disadvantages of each strategy in the light of experimental results and provide some guidelines on choosing proper strategies for a given domain.