Searching For Solutions

The first example we examine is the vacuum world (See Figure ai.01) This can be formulated as a problem as follows:

States : The state is determined by both the agent location and the dirt locations. The agent is in one of two locations, each of which might or might not contain dirt. Thus, there are 2 x 2²= 8 possible world states. A larger envirorunent with n locations has n.2ⁿ states.
Initial State : Any state can be designated as the initial state.
Actions : In this simple environment, each state has just three actions: Left, Right, and Suck. Larger environments might also include Up and Down.
Transition Model : The actions have their expected effects, except that moving Left in the leftmost square, moving Right in the rightmost square, and Sucking in a clean square have no effect.
Goal Test : This 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.

Figure ai.01 A vacuum cleaner world with just two location
In the simplest case of an agent reasoning about what it should do, the agent has a state-based model of the world, with no uncertainty and with goals to achieve. This is either a flat (non-hierarchical) representation or a single level of a hierarchy. The agent can determine how to achieve its goals by searching in its representation of the world state space for a way to get from its current state to a goal state. It can find a sequence of actions that will achieve its goal before it has to act in the world.The one kind of goal-based agent called a problem-solving agent. Intelligent agents are supposed to maximize their performance measure. Problem-solving agents use atomic representations, a problem can be defined formally by five components:

The initial state that the agent starts in. For example, the initial state for our agent in Romania might be described as In(Arad).
A description of the possible actions available to the agent. Given a particular states, ACTIONS(s) retwns the set of actions that can be executed in s. We say that each of these ctions is applicable in s. For example, from the state In(Arad), the applicable actions are { Go(Sibiu), Go( Timisoara ), Go(Zerind)}.
A description of what each action does; the formal name for this is the transition model, specified by a function RESULT(8, a) that returns the state that results from doing action a in state 8. We also use the term successor to refer to any state reachable from a given state by a single action. For example, we have RESULT(In(Amd), Go(Zerind)) = In(Zerind). Together, the initial state, actions, and transition model implicitly define the state space of the problem-the set of all states reachable from the initial state by any sequence of actions. The state space forms a directed network or graph in which the nodes are states and the links between nodes are actions. (The map of Romania shown in Figure ai.02 can be interpreted as a state-space graph if we view each road as standing for two driving actions, one in each direction.) A path in the state space is a sequence of states connected by a sequence of actions.

The goal test, which determines whether a given state is a goal state. Sometimes there is an explicit set of possible goal states, and the test simply checks whether the given state is one of them. The agent's goal in Romania is the singleton set { In(Bucharest) }. Sometimes the goal is specified by an abstract property rather than an explicitly enumerated set of states. For example, in chess, the goal is to reach a state called "checkmate” where the opponent's king is under attack and can't escape.
A path cost function that assigns a numeric cost to each path. The problem-solving agent chooses a cost function that reflects its own performance measure. For the agent trying to get to Bucharest, time is of the essence, so the cost of a path might be its length in kilometers. In this chapter, we assume that the cost of a path can be described as the STEP cosr sum of the costs of the individual actions along the path. The step cost of taking action a in state 8 to reach state s' is denoted by ( c, a, s'). The step costs for Romania are shown in Figure ai.02 as route distances. We asstune that step costs are nonnegative.

Figure ai.02 A simplified roadmap of part of Romania
The problem-solving approach has been applied to a vast array of task environments. We list some of the best known here, distinguishing between toy and real-world problems. A toy problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact description and hence is usable by different researchers to compare the performance of algorithms. A real-world problem is one whose solutions people actually care about. Such problems tend not to have a single agreed-upon description, but we can give the general flavor of their formulations.

Having formulated some problems, we now need to solve them. A solution is an action sequence, so search algorithms work by considering various possible action sequences. Figure ai.03 shows the first few steps in growing the search tree for finding a route from Arad to Bucharest. The root node of the tree corresponds to the initial state, ln(Arad). The first step is to test whether this is a goal state. (Clearly it is not, but it is important to check so that we can solve trick problems like "starting in Arad, get to Arad.") Then weneed to consider taking various actions. We do this by expanding the current state; that is, applying each legal action to the current state, thereby generating a new set of states. In this case, we add three branches from the parent node ln(Arad) leading to three new child nodes: ln(Sibiu), ln(Timisoara), and ln(Zerind). Now we must choose which of these three possibilities to consider further.

Figure ai.03 Partial search trees for finding a route from Arad to Bucharest
This is the essence of search-following up one option now and putting the others aside for later, in case the first choice does not lead to a solution. Suppose we choose Sibiu first. We check to see whether it is a goal state (it is not) and then expand it to get ln(Arad), ln(Fagaras), ln(Oradea), and ln(RimnicuVilcea). We can then choose any of these four or go back and choose Timisoara or Zerind. Each of these six nodes is a leaf node, that is, a node with no children in the tree. The set of all leaf nodes available for expansion at any given point is called the frontier. (Many authors call it the open list, which is both geographically less evocative and less accurate, because other data structures are better suited than a list.) In Figure ai.03, the frontier of each tree consists of those nodes with bold outlines.
The eagle-eyed reader will notice one peculiar thing about the search tree shown in Figure ai.03, it includes the path from Arad to Sibiu and back to Arad again! We say that ln(Arad) is a repeated state in the search tree, generated in this case by a Ioopy path. Considering such loopy paths means that the complete search tree for Romania is infinite because there is no limit to how often one can traverse a loop.
On the other hand, the state space-the map shown in Figure ai.02-has only 20 states. certain algorithms to fail, making otherwise solvable problems unsolvable. Fortunately, there is no need to consider loopy paths. We can rely on more than intuition for this: because path costs are additive and step costs are nonnegative, a loopy path to any given state is never better than the same path with the loop removed.
Loopy paths are a special case of the more general concept of redundant paths, which exist whenever there is more than one way to get from one state to another. Consider the paths Arad-Sibiu (140 km long) and Arad-Zerind-Oradea-Sibiu (297 km long). Obviously, the second path is redundant-it's just a worse way to get to the same state. If you are concerned about reaching the goal, there's never any reason to keep more than one path to any given state, because any goal state that is reachable by extending one path is also reachable by extending the other.

Searching For Solutions

Searching For Solutions

www.CodeNirvana.in