Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Introduction to AI (3/3) > Planning > Flashcards

Planning Flashcards

1
Q

What is planning in the context of AI?

A

The task of coming up with a sequence of actions that will achieve a goal starting from an initial state.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the key components involved in a planning problem?

A
  • initial state
  • set of actions
  • goal state (predicate)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does a plan consist of?

A

A sequence of actions that change the initial state to satisfy the goal-state description.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How are goals typically specified in planning?

A

As a conjunction of subgoals.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

In problem solving, how are actions, states, and goals typically represented?

A

As black boxes, with each problem having its own representation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How does Planning work in terms of representation?

A
  • Explicit representations of states, actions and goals
  • typically in some form of logical calculus

Problem solving + Logic representation = Planning

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the principal idea behind planning in First-Order Logic (FOL)?

A

Planning problems are formulated in FOL, where
* states and goals are conjunctions of literals
* and actions are logical rules.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are key problems in Planning?

A
  • Find relevant actions
  • Pick good heuristic
  • Decompose the problem
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the principal idea behind planning in First-Order Logic?

A
  1. Formulate planning problem in First-Order Logic (FOL)
  2. Use theorem prover to find a proof for the goal (e.g. PROLOG)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the key problem with planning in FOL?

A

The representation of change

  • add & delete sentences from the Knowledge Base (KB) to reflect changes
  • all facts are indexed by a situation variable → situation calculus
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the Situation Calculus and how does it represent states and actions in planning?

A

A logical framework for representing states and changes caused by actions in AI planning.

It allows for Logical reasoning by providing

  1. State representation (additional arguments for literals, to specify the state where they are true)
  2. Action rules (define how aspects of the world change with an action)

For example, “at(grocery, s1)” means “In state s1, we are at the grocery store.”

For example, “have(milk, result(buy(milk),S)) :- at(grocery,S)” means “The result of buying milk in a state S, in which we are in a grocery store, is that we then have milk.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the Frame Problem in planning?

A

The need for rules that describe what doesn’t change when an action is performed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Related to the Frame Problem, what is the issue with frame axioms?

A

Frame axioms track how all states s need to be updated after an action a.

They are necessary for all possible combinations of s and a, but…

  • we don’t want to represent each such possible combination (representational frame problem)
  • we don’t want to re-evaluate every proposition in the KB after each action (inferential frame problem)

  • most of the work will be spent in deriving that nothing changes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are criteria for a good Representation Language?

A
  • Expressive enough to describe a wide variety of problems
  • Restrictive enough to allow efficient algorithms

A Planning algorithm should be able to take advantage of the logical structure of the problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is STRIPS in the context of planning?

A

STanford Research Institute Problem Solver, a classical planning system.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the closed world assumption in STRIPS?

A

What is not known to be true is assumed to be false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How does State Representation work in STRIPS?

A

The world is decomposed into logical conditions and State is represented as conjunction of positive literals:

  • Propositional literals e.g., rich ∧ famous
  • First-Order literals e.g. at(plane1, melbourne) ∧ at(plane2, sydney)

fol: e.g., grounded i.e, no variables and function-free, no function symbols)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How does Action Representation work in STRIPS?

A

An action is applicable if the preconditions match the current state. The resulting state changes *) are described by the effects, divided into ADD- and DELETE-list

*) Facts that become true/false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

How does Goal Representation work in STRIPS?

A

Like any other state, a goal is a conjunction of positive ground literals. It is satisfied if the goal state contains all literals.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are partially instantiated first-order predicates and how do they help with goal achievement?

A

Logical statements with variables which allow flexible goal-setting and matching without specifying all details up front.

  • at(P,paris) ∧ plane(P)
  • at(spirit_of_st_louis,paris) ∧
    plane(spirit_of_st_louis)
  • satisfies the goal with the substitution θ = {P/spiritofstlouis}
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Explain the semantics of the STRIPS language

A
  • States are represented as conjunctions of positive literals, with closed-world assumption
  • Actions are defined by preconditions, add lists, and delete lists
  • Effects of actions modify the state by adding and removing literals
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are the ADD-list and DELETE-list in STRIPS?

A

They describe the state change (= effects) after executing an action:

  • ADD-list: facts that become True
  • DELETE-list: facts that become False
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

How does the STRIPS language avoid the representational frame problem?

A

By assuming that every literal not in the effect (ADD, DEL) remains unchanged.

How? The result of executing action a in state s is the state t.

C.p. t is same as s except:
* any literal P in the ADD-list is added
* any literal P in the DELETE-list is removed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the Blocks World in AI planning?

A

A famous AI toy domain consisting of a table, a set of blocks, and a robot hand.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What can the robot hand do in the Blocks World?

A
  • Grasp a single block
  • Move over the table
  • Release a block it is holding
  • Stack blocks if the top is clear
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is the initial state of the Blocks World?

A

Conditions describing which blocks are on the table and their clear status.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is the goal representation in the Blocks World?

A

A conjunction of literals that describes the desired arrangement of blocks.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is a progression algorithm in planning?

A

Formulates planning as a state-space search problem using initial states, actions, goal tests and step costs

  • any complete graph search algorithm will yield a complete planner
  • efficiency is a problem (irrelevant actions, good heuristic required)
29
Q

What is the purpose of heuristics in planning?

A

To improve the efficiency of the search process in planning.

30
Q

What is the regression algorithm in planning?

A

A backward search method that applies STRIPS operators backwards to find relevant actions.

31
Q

What is a relevant action in the context of regression planning?

A

One that achieves at least one of the subgoals.

32
Q

What is a consistent action in regression planning?

A

An action that does not undo subgoals that are already achieved.

33
Q

What are relevant actions in planning?

A

Actions that achieve one of the subgoals, i.e., the subgoal is on the actions’ ADD-list.

34
Q

What is an example of a relevant action?

A

Actions that achieve one of the subgoals (subgoal is on the actions’ ADD-list)

35
Q

What are consistent actions in planning?

A

Actions that must not undo subgoals that are already achieved.

36
Q

A task will appear in a plan even if it deletes the subgoal which has been achieved with the first action.

A

False.

37
Q

What is the difference between progression planners and regression planners?

A
  • Progression: search forward from initial to goal state
  • Regression: search backward from goal to initial state
38
Q

What is the general process for predecessor construction?

A

Inverse Action Application

  • Given a goal description G
  • let A be an action that is relevant and consistent

New Goal = Old Goal – ADD(A) + PRECOND(A)

39
Q

Fill in the blank: New Goal = Old Goal - ______ + PRECOND(A).

A

ADD(A)

40
Q

What are decomposable problems?

A

Problems where goals are given as a conjunction of subgoals that can be solved independently.

41
Q

What is the Sussman Anomaly?

A

An example showing that subgoals are not independent, where achieving one subgoal may require undoing another.

42
Q

What is Partial-Order Planning (POP)?

A

A planning method that allows actions to be executed in any order if they don’t interfere with each other.

Least commitment strategy: Delay choice during search -> re-order steps later on (when subplans are combined)

43
Q

What is the role of the Start action in a plan?

A

Defines the start state and must be ordered before every other action in the plan.

44
Q

What does the Finish action signify in a plan?

A

It has an empty ADD-list and defines when goal is achieved.

45
Q

What is the difference between state-space planning and plan-space planning?

A
  • State-space planning searches through possible states
  • Plan-space planning searches through possible plans
46
Q

What components does each plan in POP consist of?

A
  • set of actions {A, B}
  • set of ordering constraints: A < B
  • set of causal links: A -> p -> B
  • set of open preconditions (not achieved by action in the plan)
47
Q

What is a causal link in the context of planning?

A

A link that shows that action A adds condition p which is needed for action B.

48
Q

What is the goal test in the context of plan-space search?

A

A consistent plan with no open preconditions is a solution.

49
Q

Fill in the blank: An action C conflicts with causal link A → p → B if the effect of C is ______.

A

¬ p and if C could come after A and before B

50
Q

What is the main advantage of regression planning?

A

Only relevant actions are considered, leading to a lower branching factor than for forward planning (search).

51
Q

What does the search through plan-space gradually move towards?

A

From incomplete (vague) to complete (correct) plans.

52
Q

What happens if an open condition is unachievable during plan-space search?

A

The plan-space search backtracks to the next condition at one of the previous choice points

53
Q

What is the Spare Tire Problem?

A

A Plan-Space Planning problem.

It demonstrates basic concepts in planning, such as state representation, action preconditions and effects, and goal-directed reasoning.

54
Q

When is the Spare Tire Problem solved?

A

When no open preconditions remain.

55
Q

What is an example for constraints in the Spare Tire Problem?

A

Remove(Flat, Axle) < PutOn(Spare,Axle)

This indicates the order of actions.

56
Q

What is the outcome after resolving all open preconditions in the Spare Tire Problem?

A

No more open preconditions -> Plan is completed

57
Q

What are general heuristics that can be used in Plan-Space Planning?

A
  1. Number of distinct open preconditions
  2. Select open condition that can be satisfied in the fewest number of ways (most-constrained variable)

1) underestimates cost when several actions to achieve condition OR overestimate costs when multiple goals with single action

58
Q

What is a strong factor in selecting a precondition to refine?

A

Select open condition that can be satisfied in the fewest number of ways

This is analogous to the most-constrained variable heuristic.

59
Q

What happens when a condition cannot be achieved at all in planning?

A

Early failure

This indicates a significant issue in planning.

60
Q

In executing partially ordered plans, what is possible?

A

Any particular order consistent with ordering constraints

This flexibility is beneficial in non-cooperative environments.

61
Q

Name major approaches to planning.

A
  • Situation calculus
  • State-Space Planning
  • Plan-Space Planning
  • Partial-Order Planning
62
Q

What does GraphPlan do in relation to planning problems?

A

Maps planning problem to a graph search problem

This helps visualize and solve planning issues.

63
Q

What is one of the key differences between state-space planning and plan-space planning?

A

State-space planning searches through possible world states, while plan-space planning searches through possible partial plans.

This difference allows plan-space planning to take advantage of problem decomposition and delay committing to specific action orderings until necessary

64
Q

What are causal links and ordering constraints?

A
  • Causal links connect actions to their effects
  • Ordering constraints specify the sequence of actions

Conflicts can arise between these two.

65
Q

What is the Sussman Anomaly?

A

Famous example that shows that subgoals are not independent.

This anomaly highlights issues in achieving certain goals.

66
Q

Why is Regression planning often better than Progression planning?

A

Due to its ability to work backward from goals.

67
Q

How is the predecessor state determined?

A

The predecessor state is determined as follows:

  1. positive effects of A that appear in G are deleted (assumed to have been added by A, otherwise A not needed)
  2. each precondition literal of A is added (unless it already appears; we must find actions that enable the preconditions)
68
Q

How can a conflict between causal links and ordering constraints be recognized and resolved?

A

A conflict arises when an action C threatens a causal link A→p→B.

This occurs when:
* C has an effect that negates p (¬p)
* C could potentially be ordered between A and B

To resolve such a conflict, planners typically use two strategies:
1. Promotion: Order C before A (C < A)
2. Demotion: Order C after B (B < C)

69
Q

What are properties of Nearly Decomposable Problems?

A
  • Planning for subgoals is possible
  • Additional work may be required to bring the partial results together

Introduction to AI (3/3) (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions