Hot-Link Menu in Right-Side Column

Wal Mart Online → Best Selection
WM468X60_ko_static.gif


8-puzzle

The 8-puzzle, an illustration of which is depicted in Figure Agent-4, is composed of a 3 Χ 3 board with eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the space. The object is to reach a specified goal state, such as the diagram illustrated on the right side of the figure:

8-Puzzle

Figure Agent-4: A typical instance of the 8-puzzle.


The object is to reach a specified goal state, such as the one shown on the right of the figure. The standard formulation is as follows:

  • States: A state description specifies the location of each of the eight tiles and the blank in one of the nine squares.

  • Initial State: Any state can be designed as the initial state. Note that any given goal can be reached from exactly half of the possible initial states.

  • Actions: The simplest formulation defines the actions as movements of the blank space Left, Right, Up, or Down. Different subsets of these are possible depending one where the blank is.

  • Transition Model: Given a state and action, this returns the resulting state; for example if we apply Left to the start state as in Figure Agent-4, the resulting state has the 5 and the blank switched since the commands refer to the moving of the blank space.

  • Goal Test: This checks whether the state matches the goal configuration shown in Figure Agent-4.

  • Path Cost: Each step costs 1, so the path cost is the number of steps in the path.

The actions above are abstracted to their beginning and final states only. The intermediate locations of when the block is sliding are ignored. Abstracted actions would include shaking the board when the pieces get stuck, extracting the pieces with a screwdriver and pounding them back in with a hammer and so on. This leaves us with a description of the rules of the puzzle, and allowing us to ignore the details of physical manipulation.

The 8-puzzle belongs to the family of sliding-block puzzles, which are often used as test problems for new search algorithms in AI. This family is known to be NP-complete, so we are not expecting to methods significantly better than the search algorithms described later in this guide. However, if you would like to make a significant contribution to AI, you can come up with a more efficient search algorithm than those presented here. The 8-puzzle has has 9!/2 or 181,440 reachable states so is easily solved. Next, is the 15-puzzle which is the 4 χ 4 board giving 1.3 trillion states. The best search algorithms can solve this puzzle optimally in a few milliseconds. The 24-puzzle (on a 5 chi; 5 board) has around 1025 states, and random instances can take several hours to solve optimally.

In order to decrease the time you need to optimally solve some of your pesky algorithms, you can develop your own more efficient algorithms, and be entered into the AI Hall of Fame, or simply follow the links below to purchase a more powerful machine with increased processing power and more memory at incredible savings for you:

Centurion Online → Computers → Laptops


8-Queens Problem

The goal of the 8-queens problem is to place eight queens on a chessboard such that no queen attacks any other. (A queen attacks any piece in the same row, column or diagonal.) Figure Agent-5 shows an attempted solution that fails since the queen in the rightmost column is attacked by the queen at the top left.

8-Queens

Figure Agent-5: Almost a solution to the 8-Queens problem.

Although efficient special-purpose algorithms exist for this problem and for the whole N-Queens family, it remains a useful test problem for search algorithms. There are two main kinds of formulation. An incremental formulation involves operators that augment the state description, starting with an empty state; for the 8-Queens problem, this means that each action adds a queen to the state. A complete-state formulation starts with all 8 queens on the board and moves them around. In either case, the path cost is of no interest because only the final state counts. The first incremental formulation one might try is the following:

Although efficient special-purpose algorithms exist for this problem and for the whole N-Queens family, it remains a useful test problem for search algorithms. There are two main kinds of formulation:

  1. Incremental Formulation: involves operators that augment the state description, starting with an empty state. For the 8-Queens problem this means that each action adds a queen to the state.

  2. Complete-State Formulation: starts with all 8 queens on the board and moves them around.

In either case, the path cost is of no consequence since only the final state is relevant. An example incremental formulation might be:

  • States: Any arrangement of 0 to 8 queens on the board is a state.
  • Initial State: No queens on the board.
  • Actions: Add a queen to any empty square.
  • Transition Model: Returns the board with a queen added to the specified square.
  • Goal Test: 8 queens are on the board, none attacked.

In this formulation we have 64 * 63 * 62 ... *57 ==> 1.8 x 1014 possible sequences to investigate. A better formulation would prohibit placing a queen in any square that is already attacked:

In this formulation we have 64 * 63 * 62 .. * 57 → 1.8 X 1014 possible sequences requiring investigation. A better heuristic would prohibit placing a queen in any square that is already attacked:

  • States: All possible arrangements on n Queens (0≤n≤8), one per column i the leftmost n columns, with no queen attacking another.

  • Actions: Add a queen to any square in the leftmost empty column such that it is not attacked by any other queen.

This formulation reduces the 8-Queens space from 1.8 x 1014 to just 2,057 and solutions are easy to find. On the other hand, for 100 queens the reduction is from roughly 10400 state to about 1052 states. A big improvement, but not enough to make the problem tractable.


The Knuth Sequence

This final toy problem was devised by Donald Knuth in 1964 and illustrates how infinite spaces can arise. Knuth conjectured that one can start with the number 4, apply a sequence of factorial, square root, and floor operations, and arrive at any desired positive integer. For example:

Knuth
    The problem definition is very simple:

  • States: Positive Numbers.
  • Initial State: 4.
  • Actions: Apply factorial, square root, or floor operation. Factorial can be applied only to integers.

  • Transition Model: As given by mathematical definitions of the operations.

  • Goal Test: State is the desired positive integer.

To our knowledge there is no bound on how large a number might be constructed in the process of reaching a given target - for example, 620,448,401,733,239,439,360,000 is generated in the expression for 5 - so the state space for this problem is infinite. Such state spaces arise very frequently in tasks involving the generation of mathematical expressions, circuits, proofs, programs, and other recursively defined objects.

Excellent Tech Support - Centurion Approved


Real World Problems

Route Finding Problems

We have already seen how the route-finding problem is defined in terms of specified locations and transitions along links between them. Route-finding algorithms are used in a variety of applications. Some, such as Web sites and in-car systems that provide driving directions, are relatively straightforward extensions of the Romania example. Others, such as routing video streams in computer networks, military operations planning, and airline travel planning systems, involve much more complex speciifcations. Consider the airline travel problems that must be solved by a travel planning Web site:

Recalling our session with Intelligent Agents we have seen how route-finding problems can be defined in terms of specified locations and transitions along links between them. Route-finding algorithms are used in a variety of applications. Some, such as Web sites and in-car systems that provide driving directions, are a relatively straightforward extension of the Romanian map problem. Others, such as routing video streams in computer networks, military operations planning and airline travel planning systems, involve much more complex specifications. These and other fascinating AI topics are discussed and solved in much greater detail and can be found by following the links above at:

Centurion Online → Books → Computer Science

Consider the airline travel problems that must be solved by a travel planning Web site:

  • States: Each state obviously includes a location, for the heck of it, let's call the location an 'airport', and the current time. Furthermore, because the cost of an action, let's be original and call this a 'flight', may depend on previous flight segments, their fare base, and perhaps whether they were domestic or international, because more regulations apply.

  • Initial State: This is specified by the user's query.

  • Actions: Take any flight from the current location, in any seat class, leaving after the current time, leaving enough time for within-airport transfer if there was a preceding flight segment.

  • Transition Model: The state resulting from taking a flight will have the flight's destination as the current location and the flight's destination as the current location and the flight's arrival time as the current time.

  • Goal Test: Are we at the final destination specified by the user?

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

Commercial travel advice systems use a problem formulation of this kind, with many additional complications to handle the byzantine fare structures that airlines impose, e.g. They want to charge me for a whole row when I forget to put on my deodorant. If it is such a big deal, then why don't they just have a community anti-perspirant, that we all could share? As any seasoned traveler knows, however, that not all air travel goes according to plan. A really good system should include contingency plans - such as backup reservations on alternate flights - to the extent that these are justified by the cost and likelihood of failure of the original plan.


Touring Problems

Touring Problems are closely related to route-finding problems, but, with an important, very important, difference. Consider, just consider, for a moment, if you will, the problem "Visit every city in Figure Agent-2 at least once, starting and ending in Bucharest." As with route finding, the actions correspond to trips between adjacent cities. The state space, however is quite different. Each state must include not just the current location but also the set of cities Agent Smart has visited. So, the initial state would be: In(Bucharest), Visited({Bucharest}), a typical intermediate state would be: In(Vaslui), Visited({Bucharest, Urziceni, Vaslui}), and the goal test would check whether Agent Smart is in Bucharest and has visited all 20 cities.


Traveling Salesperson Problem

The Traveling Salesperson 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 NP-hard, but an enormous amount of effort has been expended to improve the capabilities of TSP algorithms. In addition to planning trips for traveling salespersons, these algorithms have been used for tasks such as planning movements of automatic circuit board drills and of stocking machines on shop floors.


VLSI Layout

A VLSI layout problem requires positioning millions of components and connections on a chip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize manufacturing yield. The layout problem comes after the logical design phase, and is usually split into two parts: cell layout and channel routing. In cell layout, the primitive components of the circuit are grouped into cells, each of which performs some recognized function. Each cell has a fixed footprint (size and shape) and requires a certain number of connections to each of the other cells. The aim is to place the cells on the chip so that they do not overlap and so that there is room for the connecting wires to be placed between the cells. Channel routing finds a specific route for each wire through the gaps between the cells. These search algorithms are extremely complex, but definitely worth solving.


Robot Navigation

Robot Navigation is a generalization of the route-finding problem described earlier. Rather than a discrete set of routes, a robot can move in a continuous space with (in principle) an infinite set of possible actions and states. For a circular robot moving on a flat surface, the space is essentially two-dimensional. When the robot has arms and legs or wheels that must also be controlled, the search space becomes many-dimensional. Advanced techniques are required just to make the search space finite. In addition to the complexity of the problem, real robots must also deal with errors in their sensor readings and motor controls.


Automatic Assembly Sequencing

Automatic assembly sequencing of complex objects by a robot was first demonstrated by Freddy. Progress since then has been slow but sure, to the point where the assembly of intricate objects such as electric motors is economically feasible. In assembly problems, the aim is to find an order in which to assemble the parts of some object. If the wrong order is chosen, there will be no way to add some part later in the sequence without undoing some of the work already done. Checking a step in the sequence for feasibility is a difficult geometrical search problem closely related to robot navigation. Thus, the generation of legal actions is the expensive part of assembly sequencing. Any practical algorithm must avoid exploring all but a tiny fraction of the state space. Another important assembly problem is protein design, in which the goal is to find a sequence of amino acids that will fold into a three-dimensional protein with the right properties to cure some disease.

In order to continue with this guide, and continue the discussion on Romanian Map Problems and Solutions: Press the Button below:

Last Updated 7-27-2010

Home


Artificial Intelligence

Big O Notation

NP Completeness

Intelligent Agents


Problem Definition

Formulating Problems

Toy Problems

Vacuum World


8-Puzzle

8 Queens

The Knuth Sequence

Real World Problems

Route Finding Problems

Touring Problems

Traveling Salesperson Problem

VLSI Layout

Robot Navigation

Automatic Assembly Sequencing


Searching For Solutions


Frontier Node Expansion

Search Algorithm Infrastructure

Child Node Creation

Measuring Algorithm Performance


Uninformed Search Strategies

Breadth-First Search

Breadth-First Characteristics

C++ Breadth-First Search Code

Breadth-First Data Structure


Breadth-First Main Program

Breadth-First Make Map

Breadth-First Make Neighbor

Breadth-First Point of Origin


Breadth-First Print Cities

Breadth-First Initial Listing


Breadth-First Path Record

Breadth-First Get Child City

C++ Breadth-First Search Code


Breadth-First Print Goal Path

Uniform-Cost Search


Depth-First Search

Depth-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()

Depth-Limited Search


Iterative Depth Search

Bidirectional Search

Comparing Strategies


Informed Search Strategies

Greedy Best-First

A* Search


Conditions For Optimality

Optimality of A*


C++ A* Search Code

A* Search Data Structure

A* Search Data Entry


A* Search GetChildCity()

C++ Min Priority Queue


C++ A* Search Code Function

C++ A* Headers & Prototypes

C++ A* Search Main()


Normalized Information Distance