Planning Flashcards
Planning is the task of coming up with a sequence of actions that will achieve a goal starting from the initial state.
True
What is NOT a key problem of planning?
- states are domain specific, i.e. heuristics have to be applied for each new problem
- planning problems can be seen as a sat. problem where some are unsatisfiable = TRUE
- number of solutions/plans grows exponentially
- there are many different solutions/plans to get to the goal state
What is the key problem in First Order Logic Planning?
- for every step, there is a chance of making the problem worse by removing/adding states to the intial state
- First Order Logic works with quantifiers which are superflous for planning
- for every step, one has to declare all remaining states again = TRUE
- First Order Logic is not complete and sound, so it is possible to prove something wrong
What is wrong about actions in STRIPS language?
- after a step the current initial true states have to remain the same = TRUE
- consist of preconditions, an add-list and a delete-list
- are represented by predicates or propositions
- the preconditions can be empty
Tick the true statements for progression algorithms
start is the goal state
always succeeds
start is the initial state = TRUE
one can only consider relevant actions for the next step
make actions where the preconditions are satisfied = TRUE
make steps until the current state satisfies the goal = TRUE
Considering the Action A in Inverse Action Application, is the following formula true? New Goal = Old Goal + Precond(A) - Add(A)
True
What is the main advantage of regression compared to progression?
- only relevant actions are considered = TRUE
- a solution is guaranteed
- is a convex function (minima/maxima can be determined analytically)
- the loss of regression of data can be easily calculated
What does A → p → B in Planning mean?
p is a method
p is a precondition of B = TRUE
p is added to A to get to B = TRUE
A and B are Actions = TRUE
In planning, Progression- and Regression-Planning are not ordered?
False
What is the difference between state-space and plan-space planning?
In plan-space you estimate the average of the steps for all plans
In state-space the goal is to search through all actions of a plan and try to derive new knowledge/actions which simplify the problem
In plan-space you search through all possible plans = TRUE
In state-space you filter the useful states needed for a valid plan
Which statements regarding ”state-space planning” and ”plan-space planning” are correct?
- Plan-Space Planning search goes through possible plans = TRUE
- State-Space Plannning generates possible states
- Heuristics for Plan-Space Planning are (nearly) the same like Heuristics for State-Space Planning
- Plan-Space Planning generates possible plans
- State-Space Plannning search goes through possible states = TRUE
- Heuristics for Plan-Space Planning are not as well understood as heuristics for state- space planning = TRUE
When considering the plan space of Partial order Planning, one ”Node/State” in the graph is
always an action and not a (mostly in-)complete plan.
False
The STRIPS Language is a classical planning system (Fikes & Nilsson, 1971) What does STRIPS stand for?
STanford Research Institute Problem Solver
The STRIPS is a classical planning
system. Which of the following Reprentations does not exist?
- Representation of States: Decompose the world in logical conditions and represent a state as a conjunction of positive literals.
- Representation of Possibilities: Shows those possibilities (taking into account the states) that have a high probability of achieving the goal TRUE
- Representation of Goals: A goal is satisfied if the state contains all literals in goal.
- Representation of Actions: Preconditions determine the applicability of an action. Effects are typically divided into:
ADD-list (facts that become true after executing the action) &
DELETE-list (facts that become false after executing the action)
The main advantage of Regression Planning is, that only relevant actions are considered (often
much lower branching factor than for forward search).
True
The Sussman anomaly clarifies, that subgoals are not independent. Shortest solution for subgoals
has often to be undone later in order to complete the goal.
True
Match the sentences to their headlines!
1. First successful knowledge-intensive system recognized importance of domain-specific knowledge. (DEN- DRAL pro ject (Buchanan et al. 1969))
2. Model such things as knowledge and planning in data structures that make sense to the programmers that build them.
3. Model intelligence at a level similar to the neuron; Let such things as know- ledge and planning emerge.
4. Growth from a few million dollars in 1980 to billions of dollars in 1988.
a. Subsymbolic AI = 3
b. Symbolic AI = 2
c. AI industry = c
d. Knowledge-Based System = 1
The STRIPS is a classical planning
system. Now it’s about STRIPS Representation of Actions. Match correct!
- facts that become true after executing the action
- facts that become false after executing the action
- describe the state change after executing an action and are typically divided into two subs
- determine the applicability of an action
a. Preconditions = 4
b. DELETE-list = 2
c. Effects =3
d. ADD-list = 1
In Problem Solving, actions, states, and goals are black boxes
each problem has its own representation
agent does not understand the representations of actions, states, and goals
→ cannot exploit relations between them
True
Planning works with explicit representations of actions, states, and goals
True
Planning
= Problem solving + Logic representation
Key problems of the First-Order Logic
How to represent change?
a) add and delete sentences from the Knowledge Base to reflect changes
b) all facts are indexed by a situation variable → situation calculus
Situation Calculus
literals receive additional arguments that specify in which state they are true
define action rules which specify aspects change when an action is performed
Preconditions
determine the applicability of an action
conjunction of function-free literals
the action is applicable if the preconditions match the current state (similar to goals)
