Artificial Intelligence – Problem Solving

Provided by Know Labs in Partnership with Stanford University’s Engineering Department
URL: http://www.ai-class.com/

“Online Introduction to Artificial Intelligence is based on Stanford CS221, Introduction to Artificial Intelligence. This class introduces students to the basics of Artificial Intelligence, which includes machine learning, probabilistic reasoning, robotics, and natural language processing.”
Source – ai-class.com

Problem Solving

Definition of a problem:

  • Initial State
  • Action (state) –> { action1, action2, action3 … }
    Takes a state as input, and returns a set of possible actions.
  • Result (state, action) –> state1
    Takes as input state & action and delivers results as new state.
  • Goal Test (state) –> True | False
    Takes a state and returns a boolean value verifying if the state is a goal or not.
  • Path Cost (state:action –> state:action –> state:action) –> number.
    Takes a sequence of state to action transitions and returns a cost (number).

Tree Search Video

function treeSearch(problem) :
frontier = { [ initial.state ] }
loop:
if frontier is empty : (failure)
else (path = remove.frontierChoice (newFrontier))
state = path.end
if ( state == goal) : return path
else (path.extend)
for a in actions :
add [ path + action = result (state, action) ] to frontier

function graphSearch(problem) :
frontier = { [ initial.state ] } ; explored = { }
loop:
if frontier is empty : (failure)
else (path = remove.frontierChoice (newFrontier))
state = path.end ; add s to explored
if ( state == goal) : return path
else (path.extend)
for a in actions :
add [ path + action = result (state, action) ] to frontier
unless result (state, action) in frontier.explored

Tree Search Types

  • Breadth First (Counts nodes in the tree, using shortest node length first)
  • Cheapest First (Counts the total costs of each path, using shortest total cost first)
  • Depth First (Counts the total cost of each node, using the longest node first. Cannot find a finite value goal)
  • Greedy Best – First (Estimates the fastet way to reach a the goal, and continues on that path until the goal is reached. Does not always find the fastest path to a goal as it will not consider moving away from a goal as a possibile method of reach the goal.)
    Greedy Best Search
  • A* Search
    function = g + h
    g(path) = path cost
    h(path) = h(state) = estimated distance to goal
0
  Related Posts