Artificial Intelligence : Tree Search Problems and Searches

Question 1

Problem with reaching a goal

Answer 1

There are multiple actions, but they require an order.

Question 2

Problem Formulation

Answer 2

The process of describing the goal, the relevant states of the world, the possible actions and the optimality criterion.

Question 3

The Search Graph

Answer 3

First determine the set S of possible states of the problem, then the search graph for our problem is given by the set of states (s), the start state (sstart), the goal states (sgoal), the set of actions (A) that can be performed and that take the agent from one state in S to another state in S, and a cost function.

Question 4

Abstract State

Answer 4

Set of real states

Question 5

Abstract action

Answer 5

Complex combination of real actions

Question 6

Abstract Solution

Answer 6

Set of real paths that are solutions in the real world

Question 7

Successor States

Answer 7

States that follow on from other states

Question 8

Search

Answer 8

Systematic exploration of the search tree.

Question 9

Imaginary

Answer 9

Cannot be stored

Question 10

Don’t care non-determinism

Answer 10

No better option

Question 11

Breadth First

Answer 11

FIFO / Levels
Works in [S0,S1,S2,S1.1,S1.2,S2.2]
1 + b + b^2 + … + b^d with d being the shortest path to the goal state

Question 12

Depth First

Answer 12

LIFO / Left to Right
1 + b + b^2 + … + b^m, with m possibly being infinite

Question 13

Depth Limited Search

Answer 13

Limits the depth on a certain path (especially if you know the length of the solution)
1 + b + b^2 + …+ b^l with l being the depth limit

Question 14

Iterative Deepening

Answer 14

DLS depth n = 0, if solution found, return it, if not, depth n = n+1 ; complete version

IDS is complete and the solution is guaranteed to be the shortest.

1 + (1 + b) + (1 + b + b^2) + … + (1 + b + b^2 … + b^d), with d being the length of the shortest path to goal state

Always puts results at the back.

Question 15

Bidirectional Search

Answer 15

Search the goal state backwards as well as from initial state forwards.
Two steps per depth : searches up to depth d/2.
2 x (1 + b + b^2 + b^3).

Question 16

Uniform Cost Search

Answer 16

Gives a cost to each path. g = paths -> real numbers.
Guaranteed to find cheapest solution assuming the path cost grows monotonically.

Question 17

Heuristics

Answer 17

Problem specific knowledge (trial and error etc.) ; we know how good a certain state is. h = states -> real numbers.
h(s) = 0 is s is the goal state.
A heuristic is admissible if it does not overestimate the length to the goal state (is optimistic ; h(s) <= h(s), where h is the true cost from s to the goal) / doesn’t take any unnecessary steps.
Weighing the heuristic more can help with solutions faster (instead of g + h you could do g + 1.5h).

Question 18

Greedy Search

Answer 18

Expands to the path that appears to be closest to the goal.
Does not find the shortest path, but instead finds the cheapest path (cheapest node, not cheapest path).
Uses heuristics.
STILL RETURNS PATH COST.

Question 19

A* Search

Answer 19

Combines greedy search with uniform cost search.
f(O -> K) = g(0 -> k) + h(K)

Question 20

Manhattan Distance

Answer 20

Horizontal and vertical steps from the desired location.