Artificial Intelligence Series: Problem Solving Agents
In the previous articles of this series, we have discussed about various structures of agent programs.
In this article we are going to discuss about Problem Solving agents which is type of goal based agent. Since the direct mapping from states to actions of a simple reflex agent is too large to store for a complex environment, we use goal based agents that that can consider future actions and the desirability of outcomes.
Problem Solving Agents
Intelligent agents are supposed to maximize its performance measure. Achieving this can be simplified if the agent can adopt a goal and aim to satisfy it.
Setting goals help the agent organize its behavior by limiting the objectives that the agent is trying to achieve and hence the actions it needs to consider. This Goal formulation based on the current situation and the agent’s performance measure is the first step in problem solving.
We consider the agent’s goal to be a set of states. The agent’s task is to find out actions in the present and in the future that could reach the goal state from the present state. Problem formulation is the process of deciding what actions and states to consider, given a goal.
“ An agent with several immediate options of unknown value can decide what to do by first examining the future actions that eventually lead to states of known value ”
After Goal formulation and problem formulation, the agent has to look for a sequence of actions that reaches the goal. This process is called Search. A search algorithm takes a problem as input and returns a sequence of actions as output.
After the search phase, the agent has to carry out the actions that are recommended by the search algorithm. This final phase is called execution phase.
Formulate — Search — Execute
Thus the agent has a formulate, search and execute design to it.
Problems and Solutions
Before we get into more about problem formulating phase, we need to first understand what a problem is in terms of problem solving agents.
The problem can be defined formally in five components:
- Initial State
- Actions
- Transition Model
- Goal Test
- Path Cost
Initial State
The first component that describes the problem is the initial state that the agent starts in. For example, if a taxi agent needs to get to location(B) but the taxi is currently at location(A) then the initial state of the problem would be location(A).
Actions
The second component that describes the problem is a description of the possible actions available to the agent. Given a state s, Actions(s) returns the set of actions that can be executed in s. We say that each of these actions is applicable in s.
Transition Model
The third component is the description of what each action does which is called the transition model. It is specified by a function Result(s , a) that returns the state that results from doing action a in state s.
The initial state, actions and transition model together define the state space of a problem which is a set of all states reachable from the initial state by any sequence of actions. The state space forms a graph in which the nodes are states and the links between the nodes are actions.
Goal Test
The goal test determines whether a given state is a goal state or not. Sometimes there is an explicit set of possible goal states and the test simply checks whether the given state is one of them. Sometimes the goal is specified by an abstract property rather than an explicitly enumerated set of states.
Path Cost
The last component of the problem is the path cost which is a function that assigns a numeric cost to each path. The problem solving agent chooses a cost function that reflects its own performance measure.
The solution to the problem is an action sequence that leads from initial state to goal state and the solution quality is measured by the path cost function. An optimal solution has the lowest path cost among all the solutions.
An Example Problem Formulation
Let us take the example of vacuum world that was introduced in the starting of this series, There is a vacuum cleaner agent and it can move left or right and its jump is to suck up the dirt from the floor.
The problem for vacuum world can be formulated as follows:
States: The state is determined by both the agent location and the dirt location. The agent is in one of two locations, each of which might or might not contain dirt. Therefore, there are 2 x 2² = 8 possible world states.
A larger environment would have n x 2 to the power of n states.
Initial State: Any state can be assigned as the initial state in this case.
Action: In this environment there are three actions, Move Left , Move Right , Suck up the dirt.
Transition Model: All the actions have expected effects, except for when the agent is in leftmost square and the action is Left, when the agent is in rightmost square and the action is Right and the square is clean when the action is to Suck.
Goal Test: Goal test checks whether all the squares are clean.
Path Cost: Each step costs 1, so the path cost is the number of steps in the path.
The vacuum world problem is a toy problem and involves only discrete locations, discrete dirt etc. Therefore, this problem is a Toy Problem. There are many Real-World Problems like the automated taxi world. Try to formulate problems of real world and see what would be the states be and what actions could be chosen etc.
In this article we have discussed mainly about problem formulation. In the next article of this series we will be discussing about finding solutions using Searching Methods.
Reference
Artificial Intelligence: A Modern Approach, by Peter Norvig and Stuart J. Russell
