4. Classical Planning

Searching versus Planning

• Local Search:

  We are not interested in the sequence of actions (rather (sub)optimal goal state)

• Classical Search:

  We are not interested in the internal representation of states.

  States are represented as a single entity (could be a complex element, but its internal structure is not used by the search algorithm)

• Planning:

  We are interested in both the sequence of actions and the internal representation of states.

  States have structured representations (collections of properties) that are used by the planning algorithm.

  Algorithm takes advantage of structure.

AI and Planning

AI Planning deals with the …

• formalization,

• implementation, and

• evaluation

of algorithms for constructing plans.

Planning Formalized

Plan (Classical View):

—> find sequence of actions that transforms given state into goal state (in a …

• fully observable (agent has knowledge of full environment, nothing is hidden)

• deterministic (no uncertainty in the actions)

• static (environment keeps unchanged)

environment)

Plan (Alternative View):

—> assign an action to every possible state (resembles RL, exhaustive when having exponentially large number of states)

Planning Approaches:

• deductive planning: Situation Calculus

• state-based planning: STRIPS

• probabilistic planning: Markov Decision Processes

Components of Planning Systems:

1. Planning Language (sort of input for algorithm)

   • often subsets of FOL

   • states & goals can often be represented as ‘conjunctions’ of ground literals (constants represent elements and by conjunction we can describe states)

   • operators can be described as rules

   • operator semantics: change state by applying an action

     
     

2. Algorithms

   • for constructing a plan

   • Output: Sequence of actions

Potential Challenges in Planning

Frame Problem

Actions change the world, but many things remain unchanged

—> Challenge of representing the effects of actions without having to represent a large number of non-effects

—> Planning system must transfer this information from previous- to future state in an efficient way

[when moving one PSU, all others remain unchanged]

Qualification Problem

Actions may have an endless list of pre-conditions

—> What qualifies the agent to do certain actions (what preconditions)?

[unable to move robot because it ran out of power / malfunction / blocked path / …]

Ramification Problem

Actions may have unintended side-effects

[when robot moves a PSU with particular item, other items in PSU are also moved]

Blocksworld

• Constants: A, B, C (blocks)

  —> ground literals

  
  

• Predicate Symbols:

  —> describe states (configuration) = conjunctions, checks something (representation method)

  • on(block, block)

  • ontable(block)

  • clear(block)

    
    

• Function Symbols:

  —> actions

  • put(block, block)

  • put_on_table(block)

Ground literals are mixed up to describe a more complex situation