Representing a Problem's State-Space

State-Space Search (SSS) [Nil71], [Rus03] is a theory that utilizes the vertices and arcs of a graph to represent various conditions of a problem. The initial condition, all intermediate conditions, and the final condition are represented as vertices on the graph and all transitions between preceding and succeeding conditions are depicted as arcs on the graph.

The collection of all conditions is referred to as the state-space and each individual condition is called a state. The endeavor to execute precise transitions from a specific initial state to a particular goal state is termed "state-space search." A path represents a solution derived from SSS. More precisely, it is a sequence that commences with the initial state, encompasses all intermediate states in a sequential manner, and concludes with the goal state. Hence the primary objective of SSS is to identify a particular path within a graph.

Several fields offer solutions that utilize SSS to solve problems. Optimal Control theory has one widely used solution known as Dynamic Programming (DP) [Bro74], [Bar93]. The field of Operations Research offers two distinct approaches for identifying the shortest path within a graph: (1) the Dijkstra algorithm [Win94], [Mit88] and (2) the Branch and Bound technique [Win94]. Also, Artificial Intelligence (AI), has various methods for discovering the shortest path within a graph: these include blind search strategies such as breadth-first and depth-first, greedy search methods (e.g., best-first, iterative-deepening), and heuristic search (e.g., A*) [Nil71], [Rus03]. This article describes graph theory, its concepts, and terminology as used to frame and solve problems in various fields including operations research, optimal control theory, and AI.

Graphs

A graph G is comprised of two sets: the set V of vertices and the set E of edges; this is expressed mathematically in the Equation 1.1 below:

G = {V, E}                                         (1.1)

where

G is the graph;
V is the set of vertices (or nodes) in the graph;
E is the set of edges or arcs in the graph.        

In graphs, vertices are linked to other vertices with edges or arcs. In terms of graph terminology, the literature uses the term 'nodes' in place of 'vertices' and the terms 'edges' and 'arcs' for the connecting elements of graphs. These terms are not interchangeable. Edges are bidirectional, while arcs are unidirectional. Graphs that use arcs exclusively to connect the nodes are unidirectional, whereas graphs that have some edges connecting the vertices are bidirectional. When depicted, edges have two arrowheads and arcs have only one arrowhead.

Traveling Salesman Problem (TSP)

TSP is a problem often explained using a graph consisting of vertices and/or arcs. The vertices represent the set of cities, and the edges represent the set of roads connecting the cities. In TSP graphs, weights are assigned to each edge, where the edge's weight represents the distance between the cities. This concept is illustrated in Illustration 1.1 below.

The TSP graph G is an example of a labeled and explicit graph. In labeled graphs, the nodes have values written inside or next to them. This applies to arcs and edges too. The value associated with an arc or edge is referred to as the cost or weight for transitioning from one node to another. Labeled graphs are always explicit since all the vertices are clearly defined as with the graph G above. All explicit graphs fall under the category of finite graphs and their sets can be rendered. This is not the case for infinite graphs and they are always implicit since all their sets of nodes and edges cannot be explicitly represented.

Paths

Paths are sub-graphs (i.e. subsets) of a parent graph. Their elements are members of the parent graphs sets of vertices and edges. Paths can generally be made explicit except when dealing with large or infinite graphs where it's best to leave them implicit since precisely generating the entire set of paths, besides being time-consuming, can be impractical, inefficient, and even impossible — especially if only one particular path is sought — since finite graphs contain a combinatorial set of paths and infinite graphs have an infinite set of paths.

Graph G from Illustration 1.1 contains a set of paths T. This set T contains different sequences that represent each distinct path T_i. Each of these paths is made up of a combination of vertices C_i, representing all the cities. All the vertices of G are included in each path T_i since each valid path visits each of the n cities. All the paths of T are sub-graphs of G, i.e., T ? G. These relationships are summarized by Equations 1.2 below.

C_i ? G                                            (1.2)
T ? G
T_i = {C_s, ..., C_s}

where 

G is the graph; 
T is the set of paths in G; 
i is the index associated with the ith vertex; 
C_s is the vertex representing the start and end vertex of the path; 
 … are all the different combinations of the vertices in G excluding C_s; 
T_i is the set of all paths in G that begin and end with vertex C_s.        

Any solution to the TSP problem is an instance of a path. The path T_min represents the path with the minimum travel distance, d_min, from this set of paths, T, which begins and ends in the same city C_s. T_min has several aliases including the shortest path, shortest cost, the minimum (or lowest) cost path, and the optimum (or optimal) path. It does occur for graphs to contain more than one path T_min with the lowest cost value c_min. A use case of this occurs in graph G from Illustration 1.1 since the edge costs are symmetric.

The total cost c_p of each path T_i is computed by summing all the edge costs c_jk on the path as in Equation 1.3 below. c_jk is the cost between cities C_j and C_k. The minimal distance path T_min for the graph G can be identified by comparing the travel distances of all the path in T. That is, the shortest path T_min in G is the path from the set T whose total cost c_p is d_min.

c_p = ∑c_jk for all (j, k ? v)                     (1.3)
c_jk >= 0

where 

c_p is the total cost of the ith path T_i;
v is the set of vertices in the ith path T_i;
j, k are the indexes associated with a pair of vertices v_j and v_k;
c_jk is the edge cost between the vertices v_j and v_k.        

Cycles

A cycle is a special path that begins and ends at the same vertex. An instance of a cycle is found in the TSP graph G from Illustration 1.1 where the path starts and ends at the same vertex. In fact, the TSP graph G serves as an example of a cycle in itself. A cycle resulting from this graph is the path that starts at vertex C_1. The next eight elements of the cycle comprise the other vertices of the graph, and the last element of the cycle is once again the vertex C_1. One cycle formed by the vertices in the TSP graph G is T_1 = {C_1, C_2, C_3, C_4, C_5, C_6, C_7, C_8, C_9, C_1}. Another cycle within the graph G is T_2 = {C_1, C_2, C_1}. Note that the graph G contains a combinatorial set of cycles. Graphs that include cycles are referred to as cyclic graphs, while those that do not are termed acyclic graphs. Even though not all graphs contain cycles, cycles can appear in both unidirectional and bidirectional graphs.

Negative Edge Costs

Equation 1.3 above cannot be utilized to find the shortest path in cyclic graphs that incorporate negative edge costs. It is impossible to discover a shortest path within this type of graph since it leads to an infinite search. For example, consider the cycle T_1 = {C_1, C_2, C_1}, where the cost c_p is zero before the search enters the cycle, and the edge cost between C_1 and C_2 is -1. As the search exits the loop T_1, the cost c_p becomes -1. If the search proceeds to vertex C_2, which cannot be skipped since the search must explore all adjacent vertices, the cost becomes -2. Consequently, a path with a smaller cost is discovered. This outcome continues to occur since a path with a smaller cost is found after each successive iteration within the loop T_1 since the search is concurrently computing the cost and constructing the shortest path it has discovered. Therefore, this negative accumulation persists until the cost c_p reaches -∞. Consequently, a shortest path will not be found as there will always be a path with a lower cost than the previous one.

Connected Graphs

A graph is considered connected if it is possible to reach each of its individual vertices from any other vertex within the same graph. This connection between any two vertices can be established through an arc, an edge, or a path. Therefore, it's important to note that for a graph to be considered connected, it is not necessary for each pair of connected vertices to be adjacent to each other. The TSP graph G shown in Illustration 1.1 serves as an instance of a connected graph. There, the TSP graph G does not have all the vertices adjacent to each other, but they are all interconnected. However, it is possible to reach any two vertices from any other vertex within the graph.

Classic Test Problems

Many studies on algorithms published in the Journal of Artificial Intelligence include the algorithm's run times and benchmarking results. These results are typically obtained through experimentation or empirical testing conducted on algorithms that utilize a game or puzzle as their testbed. Such puzzles include, but are not limited to: TSP, chess, 8-queens, Othello, 8-puzzle, Rubik’s Cube, and the Towers of Hanoi.

The 8-Puzzle

The 8-puzzle is a sliding-block puzzle consisting of a grid with nine square slots on a board divided into three rows and three columns. It also features eight tiles numbered from 1 to 8. This board and tile arrangement is shown below in Illustration 1.2.

The tiles are positioned within the slots of the board’s grid and are restricted to occupying only one slot at a time and they cannot partially occupy a slot. Since the grid has nine slots and eight tiles, there will always be one empty slot, commonly referred to as "the space." The space is allowed to change slots, meaning it can move within the board. However, it cannot move directly to a diagonal slot and its movements are always discrete, and it must remain on the board and cannot skip over slots to reach a location. When the space moves to a new slot, it displaces the tile that was occupying the slot and the displaced tile is relocated to the space’s previous location.

The 8-puzzle consists of a discrete set of configurations. Illustration 1.2 above shows one configuration of the 8-puzzle. The tiles can be rearranged into a different configuration by moving the space successively. A different configuration that could result from this is depicted in Illustration 1.3 below.

The configurations shown in Illustrations 1.2 and 1.3 are states within the problem’s state-space. The set that encompasses all the possible configurations of the 8-puzzle constitutes the problem's state-space. The initial configuration is referred to as the initial or starting state, while the destination configuration is referred to as the goal state. Any of the configurations within the problem’s state-space can serve as the problem's initial or goal state.

Trees and the Successor Operator

When working with implicit graphs, graph-searching algorithms employ a successor operator, denoted as Γ, to generate the search graph. This graph explicitly represents a subset of the implicit state-space, and the successor operator, derived from the problem description, facilitates this process.

Initially, the graph-searching algorithm is provided with a state from the problem's state-space, which serves as the foundation for establishing the first node in the search graph. Next the algorithm passes this node (or state) to the successor operator which expands it, resulting in the addition of new nodes to the search graph. These nodes are connected to the root node through arcs originating from the root as displayed below in Illustration 1.4.

Illustration 1.4 shows that the successors of the root are in the middle row and that when the successor operator was applied to those nodes, child nodes were produced in the bottom row.

Conclusion

State-Space Search and it's utilization of graph theory serves as a fundamental framework for solving complex problems in various fields, including Operations Research, Optimal Control theory, and AI. At its core, SSS leverages the structure of graphs, utilizing vertices to represent different problem states and arcs to capture transitions between these states. The overarching goal of SSS is to navigate through these states, seeking a path from an initial condition to a desired goal state.

References

[Bar93] Barto, A. G., S. J. Bradtke and S. P. Singh, “Learning to act using real-time dynamic programming”, Artificial Intelligence, Vol. 72, pp. 81-138.

[Bro74] Brogan, W. L., Modern Control Theory, Quantum Publishers Inc., 1974.

[Kum88] Kumar, V., and L. N. Kanal, “The CDP: A unifying formulation for heuristic search, dynamic programming, and branch-and-bound” in Search in Artificial Intelligence, ed. Kanal and Kumar, Springer-Verlag, 1988” pp. 91-130.

[Mit88] Mitchell, J.S.B., “An Algorithmic Approach to Some Problems in Terrain Navigation,” Artificial Intelligence, Vol. 37, pp. 171-201.

[Nil71] Nilsson, N. J., Problem-solving methods in artificial intelligence, McGraw-Hill, Inc., 1971.

[Rus03] Russell, S. and Norvig, P., Artificial intelligence: a modern approach, 2nd Ed., Prentice-Hall, 2003.

[Win94] Winston, W. L., Operations research: applications and algorithms, 3rd Ed., International Thomson Publishing, 1994.