We have already seen how the route finding problem is defined in terms of specified locations and transitions along links between them.

Route - Finding algo are used in a variety of application such as routing in computer networks, military operations planning and air line travel planning systems. These problems are typically complex to specify.

Consider a simplified example of an airline travel problem specified as follows:

- States : Each is represented by location (example: an airport) and the current time.

- Initial state : This is specified by the problem.

- Successor function : This returns the states resulting from taking any scheduled flight, leaving later than the current time plus the within airport transit time, from the current airport to another.

- Goal test : Are we at the destination by some prespecified time?

- Path cost : This depends on monetary cost, waiting time, flight time, customs and immigration procedures, seat quality, time of day, type of airplane, frequent – flyer mileage awards and so on.

A really good system should include contingency plans – such as backup reservations on alternate lights – to the extent that these are justified by the cost and likelihood of failure of the original plan.

Touring problems:

These are closely related to route finding problems, but with an important difference. Consider example: the problem “visit every city in figure at least once, starting and ending in Bucharest”.

As with route finding, the action correspond to trips between adjacent cities. The state space, however, is quite different. Each state much include not just the current location but alo the set of cities the agent has visited. So the initial state would be, “In Bucharest, visited {Bucharest}”, a typical intermediate state would be “In vashi, visited {Bucharest, urziccni, valslui}”, and the goal test would check whether the agent is in Bucharest and all 20 cities have been visited. The travelling sales person problem (TSP) is a touring problem in which each city must be visited exactly once.

The aim is to find the shortest tour, the problem is known to be Np-hard, but an enormous amount of effort has been expended to improve the capabilities of TSP algorithms. In addition to planning trips for travelling sales persons, these algo, have been used for tasks such as planning movements of automatic circuit – board drills and of stocking machines on shop floors.