Classical Planning (1) PDF

Facoltà di Ingegneria - Università del Salento Classical Planning (1) www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Planning Planning is a key aspect of intelligent behavior. Planning is the del...

Facoltà di Ingegneria - Università del Salento Classical Planning (1) www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Planning Planning is a key aspect of intelligent behavior. Planning is the deliberate process to identify and select appropriate activities, in order to reach a given goal. – Sometimes an action directly achieves a goal – Sometimes a series of actions are required To be considered: physical, temporal and logical constraints, resource consumption, 2 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Do humans always plan when trying to achieve a goal? No, because planning can be effortful and time- consuming Driving to work vs space mission As a rule, humans plan when: – facing a new situation – plans are tipically complex – a large amount of money is at stake or a high risk is involved 3 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Automated Planning Goal-based agentsa Utility-based agents – Perfomance measure (or utility function) – Optimal plans 4 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Routing and scheduling of material handling in automated plants, fulfillment centers, port terminals, … 5 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Non-player characters in video-games 6 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Hubble telescope observations planning Astronomers input a series of observations they would like to perform without taking care of manoeuvering the telescope Taken into account: dynamics, energy consumption, time windows,... 7 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Rover mission planning Mission planners input a goal. The agent determines the best course of action. Communication delays 8 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Route planning 9 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Classical Planning Fully Observable: The planner has complete knowledge of the environment's current state at any given time. Deterministic: Actions have predictable and consistent outcomes - there is no uncertainty or randomness involved. Finite States: The environment is modeled as a finite set of discrete states. Static Environment: The environment does not change unless altered by the actions of the planner itself. External changes or unexpected events do not occur. Sequential Actions: Actions are executed one at a time, and the goal is to find a sequence of these actions that leads to the desired goal state. 10 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Classical Planning Approaching automated planning as a search in a graph Uninformed search algorithms ü Breadth-first ü Depth-first ü… Informed search ü Greedy algorithm (again !) ü A* 11 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Problem solving as search States Actions Given an initial state and a goal, find the sequence of actions leading through a sequence of states to the final goal state with the least “cost” (i.e., the minimum number of steps) www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Problem solving as search Terms: – State space: the set of all states reachable from the initial state – Successor function: given action and state, returns the successor(s) Next state = f(current state, action) – Path: a sequence of states connected by actions – Goal test: is a given state the goal state? – Path cost: function assigning a numeric cost to each path – Solution: a path from initial state to goal state (hp: the environment is observable; the environment is deterministic) www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Problem solving as a search An example: the 8-puzzle problem Least # of moves Initial state Goal state Try out: http://www.permadi.com/java/puzzle8 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Running example: the 8-tile puzzle States: integer locations of tiles (1 6 3 4 B 5 7 0 2) Action: left, right, up, down Goal test: is current state = (0 1 2 3 4 5 6 7 B)? Path cost: # of steps Successor function: given {up, (1 6 3 4 B 5 7 0 2)} -> (1,6,3, 4, 0, 5, 7, B, 2)? What would the state space be for this problem? (Up to) 9! states (each state is a permutation of B 0 1 … 7; is every state reachable ?) www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Uninformed vs informed search Uninformed: search through the space of possible solutions WITH NO knowledge about which path is likely to be best 16 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Search tree www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento The search strategy The search strategy decides what is the node to be expanded next: breadth-first strategy depth-first strategy... 18 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Breadth-first earch OPEN = {start node}; # States generated but not examined. A FIFO queue CLOSED = empty; # Already visited states while OPEN is not empty do Extract the leftmost state from OPEN, call it X If X = goal state, return success SUCCESSORS = Successor function (X) Put X on CLOSED Discard any successors contained in OPEN or CLOSED Put the remaining successors in OPEN endwile 19 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Breadth-first earch OPEN=[A] CLOSED=[] OPEN=[B, C] CLOSED=[A] OPEN=[C, D. E] CLOSED=[A] OPEN=[D, E, F, G] CLOSED=[A, B, C] www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Depth-first search OPEN = {start node}; CLOSED = empty; while OPEN is not empty do Extract the rightmost state from OPEN, call it X If X = goal state, return success SUCCESSORS = Successor function (X) Put X on CLOSED Discard any successors contained in OPEN or CLOSED Put the remaining successors in OPEN endwile 21 www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Depth-first search OPEN=[A] OPEN=[C, B] OPEN=[C, E, D] CLOSED=[] CLOSED=[A] CLOSED=[A, B] OPEN=[C, E, I, H] OPEN=[C, E, I] OPEN=[C, E] CLOSED=[A, B, D] CLOSED=[A, B,D, H] CLOSED=[A, B,D, H, I] www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Questions Completeness: is the algorithm guaranteed to find a solution when there is one? Optimality: Does the strategy find the optimal solution? Time: How long does it take to find a solution? Space: How much memory is needed to perform the search? www.ingegneria.unisalento.it  Facoltà di Ingegneria - Università del Salento Search features Time: number of nodes generated Space: maximum number of nodes stored in memory Branching factor: b Maximum number of successors of any node Depth: d Depth of shallowest goal node Path length: m Maximum length of any path in the state space 24 www.ingegneria.unisalento.it