Learning and executing generalized robot plans

doi:10.1016/0004-3702(72)90051-3

Artificial Intelligence

Volume 3, 1972, Pages 251-288

https://doi.org/10.1016/0004-3702(72)90051-3 Get rights and content

Abstract

In this paper we describe some major new additions to the STRIPS robot problem-solving system. The first addition is a process for generalizing a plan produced by STRIPS so that problem-specific constants appearing in the plan are replaced by problem-independent parameters.

The generalized plan, stored in a convenient format called a triangle table, has two important functions. The more obvious function is as a single macro action that can be used by STRIPS— either in whole or in part—during the solution of a subsequent problem. Perhaps less obviously, the generalized plan also plays a central part in the process that monitors the real-world execution of a plan, and allows the robot to react “intelligently” to unexpected consequences of actions.

We conclude with a discussion of experiments with the system on several example problems.

References (6)

R.E Fikes et al.
STRIPS: A new approach to the application of theorem proving to problem solving
Artificial Intelligence
(1971)
R.E Fikes
Monitored execution of robot plans produced by STRIPS
T.D Garvey et al.
User's Guide to QA3.5 Question-Answering System

There are more references available in the full text version of this article.

Cited by (568)

MARLIN: A cloud integrated robotic solution to support intralogistics in retail
2024, Robotics and Autonomous Systems
In this paper, we present the service robot MARLIN and its integration with the K4R platform¹, a cloud system for complex AI applications in retail. At its core, this platform contains so-called semantic digital twins, a semantically annotated representation of the retail store. MARLIN continuously exchanges data with the K4R platform, improving the robot’s capabilities in perception, autonomous navigation, and task planning. We exploit these capabilities in a retail intralogistics scenario, specifically by assisting store employees in stocking shelves. We demonstrate that MARLIN is able to update the digital representation of the retail store, autonomously plan and execute replenishment missions, adapt to unforeseen changes in the environment, and interact with store employees. Experiments are conducted in simulation, in a laboratory environment, and in a real store. We also describe MARLIN’s capabilities in terms of obstacle detection and navigation in confined spaces.
Plan commitment: Replanning versus plan repair
2023, Engineering Applications of Artificial Intelligence
While executing its plan in a dynamic environment where multiple agents are operating, an autonomous agent may suffer a failure due to discrepancies between the expected and actual context and thus must replace its obsolete plan. In its endeavour to fix the failure and reach its original goals, the agent may unknowingly disrupt other agents executing their plans in the same environment. We present a property for plan repair called plan commitment to ensure a responsible repair policy among agents that aims to minimise the negative impact on others. We present arguments to support the claim that plan commitment is a valuable property when an agent may have made bookings and commitments to others. We then propose C-TFLAP, an implementation of a plan repair heuristic that allows adapting a failed plan to the new context while committing as much as possible to the original plan. We demonstrate empirically that: (1) our plan repair achieves more committed plans than plan-stability repair when an agent has made bookings and commitments to others, and (2) compared to typical replanning and plan-stability repair, it can reduce the revisions among agents when failures are avoidable and can decrease the time-loss otherwise. In addition, to demonstrate extensibility, we integrate context-aware knowledge extension with committed repairing to increase the agent’s chances of repairing.
Analyzing generalized planning under nondeterminism
2022, Artificial Intelligence
In automated planning, there has been a recent interest in solving a class of problems, where a single solution applies for multiple, possibly infinitely many, instances. This necessitates a generalized notion of plans, such as plans with loops. However, the correctness of such plans is non-trivial to define, making it difficult to provide a clear specification of what we should be looking for. In an influential paper, Levesque proposed a formal specification for analyzing the correctness of such plans. He motivated a logical characterization within the situation calculus that included binary sensing actions. This characterization argued that from each state considered possible initially, the plan should terminate while satisfying the goal. Increasingly, classical plan structures are being applied to stochastic environments such as robotics applications. This raises the question as to what the specification for correctness should look like, since Levesque's account makes the assumption that actions are deterministic.
In this work, we aim to generalize Levesque's account to handle actions with nondeterministic outcomes, which may also be accorded probabilities. By appealing to an extension of the situation calculus to handle probabilistic nondeterminism, we will show that Levesque's definition, as well as a notion of goal achievability proposed by Lin and Levesque, have limited appeal under stochastic nondeterminism. In essence, they correspond to one correct execution, which is unlikely to be adequate. Rather, we propose to delineate between goal satisfaction and termination leading to a range of correctness criteria. To better study these criteria, and to position the results in a broader context while still allowing for the generality of the situation calculus, we consider an abstract framework to study the correctness of plans with loops, in domains that are possibly unbounded, and/or stochastic, and/or continuous. Within that framework, we then prove numerous relationships between the criteria, including some impossibility results for categorically satisfying goals. Finally, we show that these notions provide a more granular view than those discussed in the literature, such as strong planning and strong cyclic planning.
Knowledge-based programs as building blocks for planning
2022, Artificial Intelligence
Citation Excerpt :
Their approach focuses on programs that do not contain sensing actions and captures a subset of the class of loop-containing programs, since the problem in general is undecidable. Planning with programs represented as operators is akin to planning with a complex form of macro-action [e.g. 17–19,10,20]. Planning with macro-actions can dramatically improve the efficiency of plan generation by reducing the depth of the search space.
Knowledge-based programs contain both world-altering actions, which upon execution change the state of the world, and sensing actions, which upon execution change the knowledge state of the agent. Knowledge-based programming has been proposed as an alternative to planning, since programs allow solving families of planning problems. Notwithstanding, agents equipped with a variety of knowledge-based procedures can compose these procedures to achieve goals, exhibiting greater degrees of flexibility. Optimized state-of-the-art planners, unfortunately, cannot be used directly to compose programs since they require operators (not programs), defined by preconditions and effects. In this article we study how to compute preconditions and effects of knowledge-based programs in order to allow state-of-the-art planners to construct plans with knowledge-based programs as building blocks. We study the problem in the language of the situation calculus, appealing to Golog to represent our programs. To this end, we propose an offline execution semantics for Golog programs with sensing. We then propose a compilation method that transforms our action theory with programs into a new theory where programs are replaced by primitive actions. This enables us to use state-of-the-art, operator-based planning techniques to plan with programs that sense for a restricted but compelling class of problems. Finally, we discuss the applicability of these results to existing operator-based planners that support sensing and illustrate the computational advantage of planning with programs that sense via an experiment.
Learning Uncertainty-Aware Temporally-Extended Actions
2024, Proceedings of the AAAI Conference on Artificial Intelligence
Generalized Planning in PDDL Domains with Pretrained Large Language Models
2024, Proceedings of the AAAI Conference on Artificial Intelligence

View all citing articles on Scopus

^☆: The research reported herein was supported at SRI by the Advance Research Projects Agency of the Department of Defense, monitored by the U.S.Army Research Office-Durham under Contract DAHC04 72 C 0008.

View full text

Learning and executing generalized robot plans☆

Abstract

Artificial Intelligence

Monitored execution of robot plans produced by STRIPS

User's Guide to QA3.5 Question-Answering System