Hot-Link Menu in Right-Side Column
Shop the Low Price Leader from Home:
A problem can be defined formally by five components:
Result(In(Arad), Go(Zerind)) = In(Zerind).
Together, the initial state, actions and transition model implicilty define the state space of the problem. The state space is the set of all states reachable from the initial state by any sequence of actions. The state space forms a directed network of graphs in which the nodes are states and the links between nodes are actions. As an example, turn your attention to the map of Romania depicted in Figure Agent-2. This map can be interpreted as a state space graph if each city is viewed as a node, and the roads are considered bidirectional (as they are, of course, in the real world).
PathCost = Sum(Costs of All Paths taken to reach goal).
The preceding elements define a problem and can be gathered together into a single data structure that is given as input to a problem-solving algorithm. A solution to a problem is an action sequence that leads from the initial state to a goal state. Solution quality is measured by the path cost function, and an optimal solution has the lowest path cost among all solutions.
If you would like to keep your costs inline, take a visit to:
at the link above to find Top Quality Products at competitive prices.
In the preceding section we proposed a formulation of the problem of getting to Bucharest in terms of the initial state, actions, transition model, goal test, and path cost. This formulation seems reasonable, but is still a model - an abstract mathematical description - and not the real thing. Compare the simple state description we have chosen, In(Arad), to an actual cross-country trip, where the state of the world includes so many things: the traveling companions, what is on the radio, the scenery out the window, whether there are any law enforcement officers nearby, how far it is to the next rest stop, the condition of the road, the weather, and so on. All these considerations are left out of our state descriptions because they are irrelevant to the problem of finding a route to Bucharest. The process of removing detail from a representation is called abstraction.
In addition to abstracting the state description, we must abstract the actions themselves. A driving action has many effects. Besides changing the location of the vehicle and its occupants, it takes up time, consumes fuel, generates pollution, and changes the agent. Our formulation takes into account only the change in location. Also, there are many actions that we will omit altogether: turning on the radio, stopping at McDonald's, getting speeding tickets, and thrown in jail for drunk driving, and so on. And of course, we don't specify turning the steering wheel 97 degrees, or screaming at the kids.
Can we be more precise about defining te appropriate level of abstraction? Probably not, but let's give it a shot anyways. Think of the abstract states and actions we have chosen as corresponding to large sets of detailed world states and detailed action sequences. Now consider a solution to the abstract problem: the path from Arad to Sibiu to Rimnicu Vilcea to Pitesti to Bucharest. This abstract solution corresponds to a large number of more detailed paths. For example, we could drink beer between Sibiu and Rimnicu Vilcea, then smoke pot for the rest of the trip, although this may add to the mileage, since we forgot where we were going, but didn't care anyways. The abstraction is valid if we can expand any abstract solution into a solution in the more detailed world; a sufficient condition is that for every detailed state that is In(Arad), there is a detailed path to some state that is In(Sibiu), and so on. The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem; in this case they are easy enough that they can be carried out without further search or planning by an average driving agent. But, if we are planning on drinking beer on this trip, and we don't want to get arrested, we had better plan on having a Better than average driving agent. The choice of a good abstraction thus involves removing as much detail as possible while retaining validity and ensuring that the abstract actions are easy to carry out. Were it not for the ability to construct useful abstractions, intelligent agents would not be considered very intelligent, especially when being swamped by activities in the real world.
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. They tend not to have a single agreed-upon description, so we will do our best describing the formulations used.
The first example we will examine is the vacuum world. as diagrammed in Figure Agent-3:
The problem is formulated as follows:
Compared with the real world, this toy problem has discrete locations, discrete dirt, reliable cleaning, and it never gets messed up once cleaned.
Artificial IntelligenceBig O Notation
Problem DefinitionFormulating Problems
The Knuth Sequence
Real World Problems
Route Finding Problems
Traveling Salesperson Problem
Automatic Assembly Sequencing
Searching For Solutions
Frontier Node ExpansionSearch Algorithm Infrastructure
Child Node Creation
Measuring Algorithm Performance
Uninformed Search StrategiesBreadth-First Search
C++ Breadth-First Search Code
Breadth-First Data Structure
Breadth-First Main ProgramBreadth-First Make Map
Breadth-First Make Neighbor
Breadth-First Point of Origin
Breadth-First Print CitiesBreadth-First Initial Listing
Breadth-First Path RecordBreadth-First Get Child City
C++ Breadth-First Search Code
Breadth-First Print Goal PathUniform-Cost Search
Depth-First SearchDepth-First C++ Solution
Depth-First Data Structure
Depth-First MakeMap()Depth-First Display Data
Depth-First Initial Listing
Depth-First GetChildCity()Depth-First Path Record
Depth-First Search Function
Depth-First PrintGoalPath()Depth-First Main()
Iterative Depth SearchBidirectional Search
Informed Search StrategiesGreedy Best-First
Conditions For OptimalityOptimality of A*
C++ A* Search CodeA* Search Data Structure
A* Search Data Entry
A* Search GetChildCity()C++ Min Priority Queue
C++ A* Search Code FunctionC++ A* Headers & Prototypes
C++ A* Search Main()
Normalized Information Distance