Introduction to Artificial Intelligence with Python

Terms

agent: entity that perceives its environment and acts upon that environment.

state: a configuration of the agent and its environment.

initial state: the state in which the agent begins.

actions: choices that can be made in a state.

ACTIONS(s) returns the set of actions that can be executed in state s.

transition model: a description of what state results from performing any applicable action in any state.

RESULTS(s,a) returns that state resulting from performing action a in state s.

state space: the set of all states reachable from the initial state by any sequence of actions.

goal test: way to determine whether a given state is a goal state.

path cost: numerical cost associated with a given path.

optima solution: a solution that has the lowest path cost among all solutions.

Search Problems

  • initial state
  • actions
  • transition model
  • goal test
  • path cost function

node:

a data structure that keeps track of

  • a state
  • a parent(node that generated this node)
  • an action(action applied to parent to get node)
  • a path cost(from initial state to node)

Approach

  • Start with a frontier that contains the initial state .
  • Repeat:
    • If the frontier is empty, then no solution.
    • Remove a node from the frontier.
    • If node contains goal state, return the solution.
    • Expand node add resulting nodes to the frontier.

Revised Approach

  • Start with a frontier that contains the initial state.
  • Start with an empty explored set.
  • Repeat:
    • If the frontier is empty, then no solution.
    • Remove a node from the frontier.
    • If node contains goal state, return the solution.
    • Add the node to the explored set.
    • Expand nodes, add resulting nodes to the frontier if they aren’t already in the frontier or the explored set.

search algorithm that always expands the deepest node in the frontier.

stack

last-in first-out data type

search algorithm that always expands the shallowest node in the frontier.

queue

first-in first-out data type

search strategy that uses no problems specific knowledge