Artificial Intelligence/Basic Problem Solving

Terminology

• FSE - Formulate, Search, Execute.
• Path - A sequence of states, connected by a sequence of actions.
• Initial State - The agent's starting state.
• Successor State - Any state reachable by a single action, from the current state.
• State Space - The set of all states reachable from the initial state, after some set of actions.
  • Note: This exclude any states that are only reachable by proceeding past the goal state.

Formal Approach

The following are general steps to formally define a problem:

• Goal Formulation - Determine goal state(s).
• Problem Formulation - Consider the starting values, and valid intermediary states that allow us to meet the goal.
• Implement a search algorithm that returns a solution, as a sequence of actions.

Five components are required for proper problem formulation:

• Initial State
• Actions - The permissible set of actions, for each state.
• Transition Model - Returns the resulting state, using the current state and chosen action.
• Goal Test - A means to check if the agent is in the goal state.
• Action/Path Cost - A numerical value assigned to each state, to determine the optimal action set.

Determining the above might require a state-space graph.
This is a graph that visually depicts all states, linked together by all possible actions at each state.

Note: When defining a problem, it's generally best to define the action set in the simplest possible manner.

Problem Types

Single-State Problem:

• The solution is a sequence of actions, and the agent knows exactly what state it will be in.
• Deterministic, fully observable.

Conformant Problem:

• The solution, if exists, is a sequence of actions, and the agent may have no idea where it is at a given stage.
• Non-observable.

Contingency Problem:

• Percepts provide new information about current state.
• Non-deterministic, partially observable.

Exploration Problem:

• Unknown state space.
• Agent needs to explore to learn about the environment.

Online Problem Solving:

• Solving that uses incomplete environmental knowledge.
• State of environment and agent must be checked at various points (such as after every action) to determine next best action.

Offline Problem Solving:

• Deterministic solving that assumes complete environmental knowledge.
• The solution can be formulated at the start of problem, before taking any actions.

Tree Search Algorithms:

• An "Offline Problem" in which a tree is used to determine the problem solution.
• The tree nodes represent states, the root of the tree is the initial state, and the branches are possible actions from each node (state).
• For more on tree search algorithms, see Search Algorithms for AI.