Week 6a and 6b.docx

Week 6a and 6b Action Planning as AI problem Planning in AI is the problem of finding a sequence of primitive actions to achieve some goal. The sequence of actions is the system's plan which then can be executed. Action planning is needed in many AI systems Autonomous agents which demonstrate intell...

Week 6a and 6b Action Planning as AI problem Planning in AI is the problem of finding a sequence of primitive actions to achieve some goal. The sequence of actions is the system's plan which then can be executed. Action planning is needed in many AI systems Autonomous agents which demonstrate intelligent behaviour (robots, drones, driverless vehicles, etc.) AI programs which automate rational thinking (theorem provers, expert systems, schedulers, NLP systems, etc.) Hybrid systems which extend the human ability to operate in hostile environment (surgical devices, underwater video cameras, etc.) Planning research has been central to AI from the beginning, partly because of practical interest but also because of the “intelligence” features of human planners. Large logistics problems, operational planning, robotics, scheduling etc. A number of international Conferences on Planning Bi-annual Planning competition Planning Domain Definition Language (PDDL) PDDL is a human-readable format for problems in automated planning that gives a description of the possible states of the world, a description of the set of possible actions, a specific initial state of the world, and a specific set of desired goals. The Planning Domain Definition Language (PDDL) is a subset of First-Order Predicate Logic (FOL) which is more expressive than propositional logic. It allows for more detailed representation of the states. The solution of the planning problem (the plan) is a sequence of actions leading to the goal state from an initial state PDDL is derived from the planning language of Stanford Research Institute Problem Solver (STRIPS). Initial and goal states s, described using predicates over state variables. A set of Actions(s) described in terms of their preconditions and effects on the states. Closed world assumption principle (CWA): Unmentioned state variables are assumed false. Action: Fly(from, to) Precondition: At(p, from), Plane(p), Airport(from), Airport(to) Effect: ¬At(p, from), At(p, to) Components of a PDDL planning task: Objects: Things in the world that interest us. Predicates: Properties of objects that we are interested in; can be true or false. Initial state: The state of the world that we start in. Goal specification: Things that we want to be true. Actions/Operators: Ways of changing the state of the world. PDDL / STRIPS operators or OPERATOR / Action Representation In the context of PDDL (Planning Domain Definition Language), "operators" generally refer to actions and their associated preconditions and effects. These operators describe the possible actions that can be taken within a planning problem. "Action" refers to a basic unit of change or transformation that can occur in a planning problem. Actions represent the ways in which the state of the world can be altered during the execution of a plan. Actions in PDDL are fundamental to defining the structure of planning problems and specifying how they can be solved through automated planning techniques. They provide a formal way to describe the actions available to an agent and the conditions under which they can be executed to achieve a desired goal. Operators contain three components: Action description Precondition - conjunction of positive literals Effect - conjunction of positive or negative literals which describe how situation changes when operator is applied Restricted language for describing the states using unary and binary predicates A restricted language for describing states using unary and binary predicates typically involves defining a set of predicates along with their arguments to represent properties of objects or relationships between them. Unary predicates have one argument, while binary predicates have two arguments. Example: Unary Predicates: Unary predicates represent properties or attributes of individual objects in the domain.Examples: At(x): Object x is located at a specific position. Robot(x): Object x is a robot. BatteryLow(x): Object x has a low battery. Binary Predicates: Binary predicates represent relationships or connections between pairs of objects in the domain.Examples: Adjacent(x, y): Object x is adjacent to object y. Carries(x, y): Object x carries object y. Connected(x, y): Object x is connected to object y. Restricted language ⇒ efficient algorithm When working with a restricted language for describing states using unary and binary predicates, an efficient algorithm for planning or reasoning about these states can use the simplicity and structure of the language. To design such Algorithm, keep in mind this consideration: Exploit Predicate Structure, Symbolic Reasoning, Constraint Propagation technique, Incremental Updates and Heuristic Search Static planning Forward search in state space (progression) Starts the search for actions from the current state and plans subsequent actions towards the goal state Considers all actions that are applicable in a given state (too much unnecessary searches) not efficient! Forward chaining follows a down-up strategy, going from bottom to top. It uses known facts to start from the initial state (facts) and works toward the goal state, or conclusion. The forward chaining method is also known as data-driven because we achieve our objective by employing available data. The forward chaining method is widely used in expert systems such as CLIPS, business rule systems and manufacturing rule systems. It uses a breadth-first search as it has to go through all the facts first. It can be used to draw multiple conclusions. Heuristics for forward state-space search For forward state-space search there are a number of domain-independent heuristics: 1. Relaxing actions: Ignore-preconditions heuristic Ignore-delete-consequence heuristic 2. Using state abstractions: Reduce the state space by considering only more general states (taxonomic inheritance) rather than all specific states (purely relational) Programs that have won the bi-annual Planning competition has often used fast forward search with heuristics (FF), or planning graphs (GraphPlan), or constraint-satisfaction planners (SAT). Backward search in state space (regression) Starts the search for actions from the goal state and plans the previous actions from the initial state Considers only actions that are relevant the actions and the states can be indexed to lower the complexity of the search for action in each state by filtering the alternative continuations Backward chaining uses an up-down strategy going from top to bottom. The modus ponens inference rule is used as the basis for the backward chaining process. This rule states that if both the conditional statement (p->q) and the antecedent (p) are true, then we can infer the subsequent (q). In backward chaining, the goal is broken into sub-goals to prove the facts are true. It is called a goal-driven approach, as a list of goals decides which rules are selected and used. The backward chaining algorithm is used in game theory, automated theorem-proving tools, inference engines, proof assistants and various AI applications. The backward-chaining method mostly used a depth-first search strategy for proof. Heuristics for backward state-space search In backward state-space search, the goal is to find a sequence of actions or transitions that lead from a goal state back to an initial state. Heuristic search algorithms aim to efficiently explore the state space by guiding the search towards promising regions based on heuristic estimates of the remaining cost to reach the initial state. Heuristics commonly used in backward state-space search: Inverse Actions, Goal Distance Heuristic, Relaxed Planning Graph Heuristic, Abstraction Heuristic, Pattern Database Heuristic, Symbolic Heuristic. Planning graphs and incremental progression The main disadvantage of state-space search is the size of the search tree (exponential). Also, the heuristics are not admissible in general (difficult to find suitable). The planning graph is organized in alternating levels of possible states Si and applicable actions Ai. Links between levels represent preconditions and effects whereas links within the levels express conflicts (mutex-links). Problems of static planning Linear planning and Sussman anomaly Planners in the early 1970s considered the plan to include totally ordered action sequences problems were decomposed in subgoals the resulting subplans were combined together in some order But linear planning is incomplete! there are some very simple problems it cannot handle due to interaction between goals (i.e., Sussman anomaly) a complete planner must be able to interleave subplans and thus, to modify the subgoals when they are combined The Sussman anomaly is a problem in artificial intelligence, first described by Gerald Sussman, that illustrates a weakness of noninterleaved planning algorithms, which were prominent in the early 1970s. Most modern planning systems are not restricted to noninterleaved planning and thus can handle this anomaly. While the significance/value of the problem is now a historical one, it is still useful for explaining why planning is non-trivial. In the problem, three blocks (labeled A, B, and C) rest on a table. The agent must stack the blocks such that A is atop B, which in turn is atop C. However, it may only move one block at a time. The problem starts with B on the table, C atop A, and A on the table: However, noninterleaved planners typically separate the goal (stack A atop B atop C) into subgoals, such as: get A atop B get B atop C Suppose the planner starts by pursuing Goal 1. The straightforward solution is to move C out of the way, then move A atop B. But while this sequence accomplishes Goal 1, the agent cannot now pursue Goal 2 without undoing Goal 1, since both A and B must be moved atop C: If instead the planner starts with Goal 2, the most efficient solution is to move B. But again, the planner cannot pursue Goal 1 without undoing Goal 2: Non-linear methods and partial planning Hierarchical planning the planning is divided into phases based on the taxonomic classification of actions First the more abstract actions are planned The specific implementation of the abstract actions are planned subsequently Partial-order planning, state-of-the-art during the 1980s and 90s used for specific tasks, such as operations scheduling also used when it is important for humans to understand the plans - e.g., operational plans for spacecraft and Mars rovers are checked by human operators before uploaded to the vehicles Planning and Action in Dynamic World The real world is changing (planning in real-time) Contingent Planning: Contingent planning involves generating a plan in advance by accounting for all possible contingencies or future states of the world. This approach requires considering a wide range of possible scenarios and generating a plan that can handle each of them effectively. While contingent planning can be comprehensive, it may lead to overly complex plans and may not be suitable for highly dynamic environments where the future states are uncertain. Conditional Planning: Conditional planning allows the planner to check the actual state of the world in real-time and then generate a plan based on that current state. This approach enables more flexibility as plans can be tailored to the specific circumstances of the current environment. However, conditional planning still requires some level of preplanning and may not handle all possible contingencies as comprehensively as contingent planning. Algorithms: backward chaining with additional rule which guarantees that every premise is satisfied AND–OR tree search where all perceptions form AND branches (very similar to backward chaining algorithm) Continuous Planning: Continuous planning involves a cycle of execution monitoring and replanning in real-time. The system continuously monitors the execution of the current plan and the state of the world. If unexpected changes occur or if the current plan becomes invalid, the system dynamically replans to generate a new plan that addresses the current situation. This approach is well-suited for highly dynamic environments where changes occur frequently and unpredictably. Continuous planning requires efficient algorithms for real-time replanning and may involve trade-offs between plan optimality and computational complexity. What Can go Wrong Incomplete Information: Unknown preconditions, Disjunctive effects. Incorrect information : Current state incorrect, Missing/incorrect postconditions in operators. Qualification problem: can never finish listing all the required preconditions and possible conditional outcomes of actions Solutions: Contingent or sensorless planning: Devise a plan that works regardless of state or outcome, considering all eventualities Conditional planning: Plan to obtain information (observation actions), Devise subplan for each contingency, combine the sublplans - e.g., Continuous planning/Replanning: Assume normal states and outcomes, Check the progress during execution, replan if necessary Execution Monitoring and Replanning: Current plan failure when preconditions of remaining plan not met Preconditions of remaining plan = all preconditions of remaining steps not achieved by remaining steps = all causal links crossing current time point makes it impossible to continue the plan On failure, replan to achieve open conditions from current state IPEM (Integrated Planning, Execution, and Monitoring): keep updating Start to match current state links from actions replaced by links from Start when done Example: Evacuation from a tall building in the case of fire Plan immediate action along the escape route After each change of floor check if the escape route is still clear to continue In the case of obstacle, replan for finding alternative escape route In the case similar to 11th September jump through the window…