Planning

Planning (Chapters 10-11)

class PlanningProblem(initial, goals, actions, domain=None)[source]

Bases: object

Planning Domain Definition Language (PlanningProblem) used to define a search problem. It stores states in a knowledge base consisting of first order logic statements. The conjunction of these logical statements completely defines a state.

convert(clauses)[source]

Converts strings into exprs

expand_fluents(name=None)[source]

Generate all ground fluents obtainable by binding the problem’s objects to the predicates appearing in the initial state, goals and action effects. If a fluent name is given, only expansions of that single fluent are produced. When a domain is defined, candidate ground fluents are filtered through a FolKB so that only those consistent with the domain are kept.

expand_actions(name=None)[source]

Generate all possible actions with variable bindings for precondition selection heuristic

is_strips()[source]

Returns True if the problem does not contain negative literals in preconditions and goals

goal_test()[source]

Checks if the goals have been reached

act(action)[source]

Performs the action given as argument. Note that action is an Expr like expr(‘Remove(Glass, Table)’) or expr(‘Eat(Sandwich)’)

class Action(action, precond, effect, domain=None)[source]

Bases: object

Defines an action schema using preconditions and effects. Use this to describe actions in PlanningProblem. action is an Expr where variables are given as arguments(args). Precondition and effect are both lists with positive and negative literals. Negative preconditions and effects are defined by adding a ‘Not’ before the name of the clause Example: precond = [expr(“Human(person)”), expr(“Hungry(Person)”), expr(“NotEaten(food)”)] effect = [expr(“Eaten(food)”), expr(“Hungry(person)”)] eat = Action(expr(“Eat(person, food)”), precond, effect)

convert(clauses)[source]

Converts strings into Exprs

relaxed()[source]

Removes delete list from the action by removing all negative literals from action’s effect

substitute(e, args)[source]

Replaces variables in expression with their respective Propositional symbol

check_precond(kb, args)[source]

Checks if the precondition is satisfied in the current state

act(kb, args)[source]

Executes the action on the state’s knowledge base

goal_test(goals, state)[source]

Generic goal testing helper function

air_cargo()[source]

[Figure 10.1] AIR-CARGO-PROBLEM

An air-cargo shipment problem for delivering cargo to different locations, given the starting location and airplanes.

spare_tire()[source]

[Figure 10.2] SPARE-TIRE-PROBLEM

A problem involving changing the flat tire of a car with a spare tire from the trunk.

three_block_tower()[source]

[Figure 10.3] THREE-BLOCK-TOWER

A blocks-world problem of stacking three blocks in a certain configuration, also known as the Sussman Anomaly.

simple_blocks_world()[source]

SIMPLE-BLOCKS-WORLD

A simplified definition of the Sussman Anomaly problem.

have_cake_and_eat_cake_too()[source]

[Figure 10.7] CAKE-PROBLEM

A problem where we begin with a cake and want to reach the state of having a cake and having eaten a cake. The possible actions include baking a cake and eating a cake.

shopping_problem()[source]

SHOPPING-PROBLEM

A problem of acquiring some items given their availability at certain stores.

socks_and_shoes()[source]

SOCKS-AND-SHOES-PROBLEM

A task of wearing socks and shoes on both feet

logistics_problem(initial_state=None, goal_state=None)[source]

LOGISTICS-PROBLEM

A logistics problem where a robot moves between places, picking up and putting down containers in order to deliver them to their destinations.

blocks_world(initial, goals, blocks)[source]

GENERALIZED-BLOCKS-WORLD-PROBLEM

A flexible constructor for creating blocks-world planning problems. Any initial and goal configuration can be specified for a given set of blocks.

rush_hour()[source]

RUSH-HOUR-PROBLEM (non-numeric version)

A planning problem for the Rush Hour sliding block puzzle. The goal is to maneuver the RedCar to the exit. This version uses non-numeric symbols for grid positions (e.g. R1, C1) instead of integers.

This specific instance uses: - RedCar (2x1, horizontal) starting at (R3, C1) - GreenTruck (3x1, vertical) starting at (R1, C4) - BlueCar (2x1, vertical) starting at (R5, C2)

rush_hour_optimized()[source]

RUSH-HOUR-PROBLEM (optimized version)

This version optimizes the planning problem by creating vehicle-specific actions. Since each vehicle’s orientation is fixed, generic predicates like IsHorizontal can be removed and actions can be created that only apply to the correct vehicle on its fixed axis of movement. This drastically reduces the number of permutations the planner needs to generate and check.

double_tennis_problem()[source]

[Figure 11.10] DOUBLE-TENNIS-PROBLEM

A multiagent planning problem involving two partner tennis players trying to return an approaching ball and repositioning around in the court.

class ForwardPlan(planning_problem)[source]

Bases: Problem

[Section 10.2.1] Forward state-space search

actions(state)[source]

Return the expanded actions whose preconditions all hold in the given state.

result(state, action)[source]

Return the state resulting from applying the action to the given state.

goal_test(state)[source]

Return True if every goal of the planning problem holds in the given state.

h(state)[source]

Computes ignore delete lists heuristic by creating a relaxed version of the original problem (we can do that by removing the delete lists from all actions, i.e. removing all negative literals from effects) that will be easier to solve through GraphPlan and where the length of the solution will serve as a good heuristic.

class BackwardPlan(planning_problem)[source]

Bases: Problem

[Section 10.2.2] Backward relevant-states search

actions(subgoal)[source]

Returns True if the action is relevant to the subgoal, i.e.: - the action achieves an element of the effects - the action doesn’t delete something that needs to be achieved - the preconditions are consistent with other subgoals that need to be achieved

result(subgoal, action)[source]

Regress the subgoal through the action, i.e. g' = (g - effects(a)) + preconds(a).

goal_test(subgoal)[source]

Return True if the subgoal is entailed by the search goal (the problem’s initial state).

h(subgoal)[source]

Computes ignore delete lists heuristic by creating a relaxed version of the original problem (we can do that by removing the delete lists from all actions, i.e. removing all negative literals from effects) that will be easier to solve through GraphPlan and where the length of the solution will serve as a good heuristic.

CSPlan(planning_problem, solution_length, CSP_solver=<function ac_search_solver>, arc_heuristic=<function sat_up>)[source]

[Section 10.4.3] Planning as Constraint Satisfaction Problem

SATPlan(planning_problem, solution_length, SAT_solver=<function cdcl_satisfiable>)[source]

[Section 10.4.1] Planning as Boolean satisfiability

predicate_negate(e)[source]

Return the logical negation of an Expr predicate, avoiding a double ‘Not’ prefix.

class Level(kb)[source]

Bases: object

Contains the state of the planning problem and exhaustive list of actions which use the states as pre-condition.

separate(e)[source]

Separates an iterable of elements into positive and negative parts

find_mutex()[source]

Finds mutually exclusive actions

populate_prop_mutexes()[source]

Compute the next level’s proposition mutexes based on the current action mutexes

prune_invalid_actions()[source]

Remove actions whose own preconditions are mutex (unsupportable)

build(actions, objects)[source]

Populates the lists and dictionaries containing the state action dependencies

perform_actions()[source]

Performs the necessary actions and returns a new Level

class Graph(planning_problem)[source]

Bases: object

Contains levels of state and actions Used in graph planning algorithm to extract a solution

expand_graph()[source]

Expands the graph by a level

non_mutex_goals(goals, index)[source]

Checks whether the goals are mutually exclusive

class GraphPlan(planning_problem)[source]

Bases: object

Class for formulation GraphPlan algorithm Constructs a graph of state and action space Returns solution for the planning problem

check_leveloff()[source]

Checks if the graph has leveled off

get_preconditions_for(action_set, level)[source]

Collects all unique preconditions for a given set of actions in a level

find_valid_action_sets(goals, level)[source]

Finds sets of actions in the given level that are not mutually exclusive and that collectively satisfy all the goals.

extract_solution(goals)[source]

Starts the solution extraction process by calling the recursive helper and returning the final plan.

extract_solution_recursive(goals, level_index)[source]

Recursively searches for a plan backwards from a given proposition level.

goals is the set of goal propositions to satisfy and level_index is the index of the proposition level currently being solved.

goal_test(kb)[source]

Return True if all of the problem’s goals can be proven from the knowledge base.

execute()[source]

Executes the GraphPlan algorithm for the given problem

class Linearize(planning_problem)[source]

Bases: object

Coordinator that linearizes partially ordered solutions generated by a GraphPlan object.

filter(solution)[source]

Filter out persistence actions from a solution

orderlevel(level, planning_problem)[source]

Return valid linear order of actions for a given level

execute()[source]

Finds a total-order solution for a planning graph (not necessarily unique)

linearize(solution)[source]

Converts a level-ordered solution into a linear solution

class PartialOrderPlanner(planning_problem)[source]

Bases: object

[Section 10.13] PARTIAL-ORDER-PLANNER

Partially ordered plans are created by a search through the space of plans rather than a search through the state space. It views planning as a refinement of partially ordered plans. A partially ordered plan is defined by a set of actions and a set of constraints of the form A < B, which denotes that action A has to be performed before action B. To summarize the working of a partial order planner,

1. An open precondition is selected (a sub-goal that we want to achieve).

2. An action that fulfils the open precondition is chosen.

3. Temporal constraints are updated.

4. Existing causal links are protected. Protection is a method that checks if the causal links conflict and if they do, temporal constraints are added to fix the threats.

5. The set of open preconditions is updated.

6. Temporal constraints of the selected action and the next action are established.

7. A new causal link is added between the selected action and the owner of the open precondition.

8. The set of new causal links is checked for threats and if found, the threat is removed by either promotion or demotion. If promotion or demotion is unable to solve the problem, the planning problem cannot be solved with the current sequence of actions or it may not be solvable at all.

9. These steps are repeated until the set of open preconditions is empty.

find_open_precondition()[source]

Find the open precondition with the least number of achieving actions (a most-constrained-variable heuristic). Returns the triple (precondition, action_that_needs_it, [achieving_actions]). Iteration is ordered deterministically so the search does not depend on set/hash ordering. Returns (None, None, None) when some open precondition has no achiever at all, which is a dead end for the current partial plan.

find_action_for_precondition(oprec)[source]

Find action for a given precondition

generate_expr(clause, bindings)[source]

Generate atomic expression from generic expression given variable bindings

generate_action_object(action, bindings)[source]

Generate action object given a generic action and variable bindings

cyclic(graph)[source]

Check cyclicity of a directed graph

add_const(constraint, constraints)[source]

Add the constraint to constraints if the resulting graph is acyclic

is_a_threat(precondition, effect)[source]

Check if effect is a threat to precondition

protect(causal_link, action, constraints)[source]

Check and resolve threats by promotion or demotion

convert(constraints)[source]

Convert constraints into a dict of Action to set orderings

toposort(graph)[source]

Generate topological ordering of constraints

display_plan()[source]

Display causal links, constraints and the plan

execute(display=True)[source]

Execute the algorithm with backtracking, using iterative deepening on the number of actions in the plan. The original greedy version committed to the first achiever it happened to iterate over and could not recover when that action’s own preconditions turned out to be unsatisfiable, so it depended on hash ordering and often printed ‘Probably Wrong’ / “Couldn’t find a solution”. Backtracking over both action choices and threat resolution (promotion vs demotion), together with the deterministic selection in find_open_precondition and a smallest-plan-first deepening bound, makes the planner solve the standard problems reproducibly and return a short, valid plan.

spare_tire_graph_plan()[source]

Solves the spare tire problem using GraphPlan

three_block_tower_graph_plan()[source]

Solves the Sussman Anomaly problem using GraphPlan

air_cargo_graph_plan()[source]

Solves the air cargo problem using GraphPlan

have_cake_and_eat_cake_too_graph_plan()[source]

Solves the cake problem using GraphPlan

shopping_graph_plan()[source]

Solves the shopping problem using GraphPlan

socks_and_shoes_graph_plan()[source]

Solves the socks and shoes problem using GraphPlan

simple_blocks_world_graph_plan()[source]

Solves the simple blocks world problem

class HLA(action, precond=None, effect=None, duration=0, consume=None, use=None)[source]

Bases: Action

Define Actions for the real-world (that may be refined further), and satisfy resource constraints.

unique_group = 1

do_action(job_order, available_resources, kb, args)[source]

An HLA based version of act - along with knowledge base updation, it handles resource checks, and ensures the actions are executed in the correct order.

has_consumable_resource(available_resources)[source]

Ensure there are enough consumable resources for this action to execute.

has_usable_resource(available_resources)[source]

Ensure there are enough usable resources for this action to execute.

inorder(job_order)[source]

Ensure that all the jobs that had to be executed before the current one have been successfully executed.

class RealWorldPlanningProblem(initial, goals, actions, jobs=None, resources=None)[source]

Bases: PlanningProblem

Define real-world problems by aggregating resources as numerical quantities instead of named entities.

This class is identical to PDDL, except that it overloads the act function to handle resource and ordering conditions imposed by HLA as opposed to Action.

act(action)[source]

Performs the HLA given as argument.

Note that this is different from the superclass action - where the parameter was an Expression. For real world problems, an Expr object isn’t enough to capture all the detail required for executing the action - resources, preconditions, etc need to be checked for too.

refinements(library)[source]

State is a Problem, containing the current state kb library is a dictionary containing details for every possible refinement. e.g.:

{
'HLA': [
    'Go(Home, SFO)',
    'Go(Home, SFO)',
    'Drive(Home, SFOLongTermParking)',
    'Shuttle(SFOLongTermParking, SFO)',
    'Taxi(Home, SFO)'
    ],
'steps': [
    ['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'],
    ['Taxi(Home, SFO)'],
    [],
    [],
    []
    ],
# empty refinements indicate a primitive action
'precond': [
    ['At(Home) & Have(Car)'],
    ['At(Home)'],
    ['At(Home) & Have(Car)'],
    ['At(SFOLongTermParking)'],
    ['At(Home)']
    ],
'effect': [
    ['At(SFO) & ~At(Home)'],
    ['At(SFO) & ~At(Home)'],
    ['At(SFOLongTermParking) & ~At(Home)'],
    ['At(SFO) & ~At(SFOLongTermParking)'],
    ['At(SFO) & ~At(Home)']
    ]}

hierarchical_search(hierarchy, max_depth=None)[source]

[Figure 11.5] ‘Hierarchical Search, a Breadth First Search implementation of Hierarchical Forward Planning Search’ The problem is a real-world problem defined by the problem class, and the hierarchy is a dictionary of HLA - refinements (see refinements generator for details). With the default max_depth=None the search follows Figure 11.5 exactly and, like the textbook algorithm, may not terminate on a recursive (cyclic) hierarchy whose goal is unreachable. Passing max_depth prunes any plan longer than that many actions, which guarantees termination (returning None when no solution is found within the bound).

result(actions)[source]

The outcome of applying an action to the current problem

angelic_search(hierarchy, initial_plan)[source]

[Figure 11.8] A hierarchical planning algorithm that uses angelic semantics to identify and commit to high-level plans that work while avoiding high-level plans that don’t. The predicate MAKING-PROGRESS checks to make sure that we aren’t stuck in an infinite regression of refinements. At top level, call ANGELIC-SEARCH with [Act] as the initial_plan.

InitialPlan contains a sequence of HLA’s with angelic semantics

The possible effects of an angelic HLA in initial_plan are: ~ : effect remove $+: effect possibly add $-: effect possibly remove $$: possibly add or remove

intersects_goal(reachable_set)[source]

Find the intersection of the reachable states and the goal

is_primitive(library)[source]

checks if the hla is primitive action

reach_opt(plan)[source]

Finds the optimistic reachable set of the sequence of actions in plan

reach_pes(plan)[source]

Finds the pessimistic reachable set of the sequence of actions in plan

find_reachable_set(action_description)[source]

Finds the reachable states of the action_description when applied in each state of reachable set.

find_hla(hierarchy)[source]

Finds the the first HLA action in plan.action, which is not primitive and its corresponding index in plan.action

making_progress(initial_plan)[source]

Prevents from infinite regression of refinements

(infinite regression of refinements happens when the algorithm finds a plan that its pessimistic reachable set intersects the goal inside a call to decompose on the same plan, in the same circumstances)

decompose(plan, s_f, reachable_set)[source]

Recursively refine the high-level actions of an abstract plan into a concrete sequence of primitive actions. Working backwards from the final state s_f, it picks an intermediate state for each pessimistic action from reachable_set and uses angelic search to expand it, returning the assembled primitive solution (or None if some action cannot be refined).

find_previous_state(reachable_set, i, action)[source]

Given a final state s_f and an action finds a state s_i in reachable_set such that when action is applied to state s_i returns s_f.

job_shop_problem()[source]

[Figure 11.1] JOB-SHOP-PROBLEM

A job-shop scheduling problem for assembling two cars, with resource and ordering constraints.

go_to_sfo()[source]

Go to SFO Problem

class AngelicHLA(action, precond, effect, duration=0, consume=None, use=None)[source]

Bases: HLA

Define Actions for the real-world (that may be refined further), under angelic semantics

convert(clauses)[source]

Converts strings into Exprs An HLA with angelic semantics can achieve the effects of simple HLA’s (add / remove a variable) and furthermore can have following effects on the variables:

Possibly add variable    ( $+ )
Possibly remove variable ( $- )
Possibly add or remove a variable ( $$ )

Overrides HLA.convert function

angelic_action()[source]

Converts a high level action (HLA) with angelic semantics into all of its corresponding high level actions (HLA). An HLA with angelic semantics can achieve the effects of simple HLA’s (add / remove a variable) and furthermore can have following effects for each variable:

Possibly add variable ( $+: ‘PosYes’ ) –> corresponds to two HLAs:

HLA_1: add variable HLA_2: leave variable unchanged

Possibly remove variable ( $-: ‘PosNot’ ) –> corresponds to two HLAs:

HLA_1: remove variable HLA_2: leave variable unchanged

Possibly add / remove a variable ( $$: ‘PosYesNot’ ) –> corresponds to three HLAs:

HLA_1: add variable HLA_2: remove variable HLA_3: leave variable unchanged

example: the angelic action with effects possibly add A and possibly add or remove B corresponds to the following 6 effects of HLAs:

‘$+A & $$B’: HLA_1: ‘A & B’ (add A and add B)

HLA_2: ‘A & ~B’ (add A and remove B) HLA_3: ‘A’ (add A) HLA_4: ‘B’ (add B) HLA_5: ‘~B’ (remove B) HLA_6: ‘ ‘ (no effect)

compute_parameters()[source]

computes n,w

n = number of HLA effects that the angelic HLA corresponds to w = length of representation of angelic HLA effect

n = 1, if effect is add n = 1, if effect is remove n = 2, if effect is possibly add n = 2, if effect is possibly remove n = 3, if effect is possibly add or remove

class AngelicNode(state, parent=None, action_opt=None, action_pes=None, path_cost=0)[source]

Bases: Node

Extends the class Node. self.action: contains the optimistic description of an angelic HLA self.action_pes: contains the pessimistic description of an angelic HLA