Federico Mengozzi

Introduction

A problem can be defined formally by several components

  • Initial state is the state that the solving agent starts in. Actions are the possible applicable operation that the agent can perform in a particular state
  • Transition model is the description of what the action does. An action applied at a given state will produce a new state (called successor). A state space is defined using the initial state, the actions and the transitional model. It defines a graph where each node represent a state and each edge represent the action.
  • The goal test is used to determine whether a state represent the actual goal.
  • Path cost is a function that assign a numeric cost to each path (a set of nodes and edges from the initial state to the goal state). The step cost represent the cost of going from one state to another with a single action. Finally, a solution is defined as a set of actions that leads from initial state to goal state.

When formulation a problem, there can be two kind of formulation

  • Complete - The initial state contains the entire data to solve the problem. It’s only a matter of finding the right action that modify the data that is already available.
  • Incremental - Starting from the initial state, an operator that augment the state description is used add the data to get to the goal state

Searching for solutions

The possible actions sequence starting from the initial state represents a search tree. To reach a solution, the initial state is first expanded: a new set of state is generate by applying each legal action to the current state. The new state are child node of the previous state that can be in turn expanded (the set of state yet to be expanded is called frontier or open list). What differentiate a search algorithm from one another is the search strategy, namely the policy they use to expand new node.

It may happen that legal action bring inevitably to already seen state. A search algorithm that produce redundant path is called three-search algorithm, while an algorithm that avoid them is called graph-search algorithm and can be constructed by augment the tree-search with a new data structure to keep track of the expanded node (usually called explored set or closed list).

When analyzing a search algorithm it’s important to consider different criteria

  • Completeness: Will the algorithm always find a solution when there is one?
  • Optimality: Will the algorithm find the optimal/best solution to the problem?
  • Time and memory complexity: How much time and memory is required by algorithm to find the solution?
Go to top