Week 2

Question 1

State model

Answer 1

S: finite, discrete state space
s0 ϵ S: initial state
SG ⊆ S: goal state(s)
A(s) ⊆ A: actions applicable in each s ϵ S
s’ = f(a, s): deterministic transition function for a ϵ A(s)
c(a, s): positive action costs

Question 2

Solution

Answer 2

Sequence of actions mapping s0 to SG

Question 3

Solution

Answer 3

Sequence of actions mapping s0 to SG

Question 4

Optimal

Answer 4

minimises sum of action costs

Question 5

Blind search

Answer 5

Use basic ingredients for general search algorithms

Question 6

Heuristic search

Answer 6

Use heuristic functions which estimate the distance to the goal.
Much better for satisficing planning, not so much better for optimal planning

Question 7

Systematic search

Answer 7

Consider a large number of search nodes simultaneously

Question 8

Local search algorithms

Answer 8

Work with at most a few candidate solutions at a time.
Doesn’t work for optimal planning but successful cases of satisficing.

Question 9

Satisficing planning

Answer 9

“Good enough” planning

Question 10

Search node n

Answer 10

state reached by the search plus information about how it was reached (e.g. cost, parent node)

Question 11

Path cost g(n)

Answer 11

Cost of the path reaching a search node, n

Question 12

Optimal cost g*

Answer 12

Cost of an optimal solution path. For state s, g*(s) is the cheapest path to reach s

Question 13

Node expansion

Answer 13

Generating all successors of a node by applying all actions applicable to the node’s state s

Question 14

Search strategy

Answer 14

Method for deciding which node to expand next

Question 15

Open list/Frontier

Answer 15

Set of all candidate nodes for expansion. AKA frontier

Question 16

Closed list/Explored set

Answer 16

All states that were already expanded. Used only in graph search not tree search

Question 17

Safe

Answer 17

h(s) = ∞ ⇒ h * (s) = ∞
h * (s) < ∞ ⇒ h(s) < ∞
If the optimal heuristic thinks we’re stuck, so does our heuristic.

Question 18

Goal-aware

Answer 18

h(s) = 0 ∀ s ϵ SG

Question 19

Admissible

Answer 19

h(s) ≤ h*(s) ∀ s ϵ S
Heuristic is optimistic

Question 20

Consistent

Answer 20

h(s) ≤ h(s’) + c(a) ∀ transitions s – a → s’
Heuristic is optimistic throughout the path