In this note, we discuss and analyse a shortest path nding approach using strong spatial cognition. It is compared with a symbolic graph-based algorithm and it is shown that both approaches are similar with respect to structure and complexity. Nevertheless, the strong spatial cognition solution is easy to understand and even pops up immediately when one has to solve the problem.
In discussions among cognitive scientists over the past 25 years or so about the
undisputed merit of graphic depictions for problem solving, the use of classical
formal analysis of graphic information processing occasionally caused some
discomfort. Firstly, because intuitively graphical procedures often appear simpler
than their formal counterparts, and secondly, because even highly accomplished
theoreticians emphasize the usefulness of graphics for getting insight into
suitable problem-solving approaches [
While debates about the complexity of graphic information processing focused on the use of static spatial information in graphics, the strong spatial cognition (SSC) paradigm goes one step further and addresses spatial transformation of spatial con gurations for problem solving, i.e. replacing computational operations by physical operations.
Such problems have in common that parts of the problem are real world
objects, instead of representations within a computer. In [
Another famous example for using mild abstractions for solving real world problems is the hanging chain method used to model catenary curves. This is used e.g. by the Catalan architect Gaudi for the construction of organic designs of churches, like the Sagrada Familia. Gaudi used weighted strings to determine the optimal static design of arcs in his architecture, instead of computing the curves, whose math was well known at this time (due to work of Leibniz, Huygens and Bernoulli on these catenary curves). This techniques is used in modern architecture as well. As an example the 'Multihalle Mannheim' together with its chain model is shown in Figure 2
In spatial cognition research there is increasing work, which aims at developing models that take into account the role of the body and the spatial environment. The interaction between mind, body, and environment helps to nd solutions to spatial problems. As an example, we will analyse in this paper a shortest path solution which is based on the mild abstraction as given in We will now use strings as a mild abstraction as illustrated in Figure 1. Here, we use strings to represent routes between two locations. The intersections of those strings represent the intersections in a route network. The length of the strings are given by a xed scaling factor of the corresponding routes. So the relative lengths of the routes are preserved. The task is is to nd the shortest path between two locations A and B within a route network. This is the SSCSP Problem. We now use this string representation in order to solve it. The locations A and B have representations A0 and B0 in the string model. In order to nd the shortest path between A and B one simply has to pull apart strings at A0 and B0 | voila. It is immediately clear that the shortest route is given by those strings that are pulled straight and the length of the shortest path is represented by the distance between A0 and B0. This is the SSCSP-Solution. Interestingly, we managed to solve the problem without analysing the network in any way, all we had to do was to pull.
The complexity seems to be constant | you need one operation 'pulling apart'. In contrast, if we represent the network by a graph using a data structure in a computer, we know that the complexity of the problem is exponential in the number of nodes on the path.
It is astonishing how humans manage to solve the shortest path problem immediately by just pulling the strings. And even more: they are convinced that this yields a shortest path | this property is just 'popping up'. This motivates us to analyze this solution within the mild abstraction paradigm in more detail, putting special emphasis on the complexity aspect.
In computer science we focus on information and we are interested in the complexity of algorithms wrt. information processing e ort required in terms of processing steps and storage capacity. We do not take into account mass and energy when we discuss complexity of information processing. But how can we assess the complexity of problem-solving processes appropriately when we manipulate information by other means than in classical telecommunication or computer architectures, where bits of information are propagated through static or ad hoc networks? To our knowledge, there is no speci c theory for information processing complexity of graphic information processing such as in depictive geometry, scienti c graphs, or geographic maps where some of the operations may consist of manipulating physical and spatial entities.
We are interested in the question of whether the complexity of solving a problem is inherent only in the problem and its information-theoretical representation and processing structures or whether it also can be a function of the physical and spatial substrate in which the problem is manifested.
In the following section we will transform the structured SSCSP-Solution into a graph-based algorithm, namely breath- rst search | a common approach in symbolic problem solving. Furthermore, we propose an approach for comparing complexities of both methods. We will see that both methods, the structured SSCSP-Solution and the graph-search have a very similar structure | the astonishing e ect is that one needs not to be aware of this structure, when the problem is solved using the mild abstraction. Once the problem is transformed into a symbolic graph-based representation, one needs to know about algorithms for graph-search to solve the problem. 3
We start by analysing a simpli ed version of the problem: We assume that all strings connecting nodes have the same length d. Furthermore, we will only pull on node A0 instead of both, A0 and B0. Now, we observe the pull operation and notice that the closer a node is to A0, the earlier it starts to move.
In order to get this more precisely, we change our model. We assume the network is spread on a at surface. Instead of pulling nodes apart, we assume an operation grab, which selects only one node and the pulling apart is changed into a lift of the grabbed node vertically into the third dimension until B0 is lifted from the surface as well. Once B0 is lifted, the shortest path is given by the sequence of strings by which B0 hangs from A0. Now, we can decompose the lift into single steps, where we only pull up until a new node is lifted from the surface (this is depicted in Figure 3). With respect to the work needed to lift nodes we see easily that lifting the nodes into the third dimension certainly can be seen as an upper bound compared to the work necessary to pull the nodes apart in two dimensions. This enables us to describe our solution to shortest path in a more detailed way than before.
The structured SSCSP-Solution is given by: { grab node A0 { repeat until node B0 is lifted:
increase height of A0 over surface by distance d
Note that, if a node x is lifted from the surface, the next lifting operation causes all adjacent nodes of x still on the surface to be lifted together. This is another simpli cation of our model; depending on the structure of the network it may happen that during one lift-operation an adjacent node is lifted earlier than its neighbors. This may occur e.g. if one node has no adjacent node, while its neighbor is connected to larger part of the network. The connecting string to the latter will form a kind of hanging chain curve, because of the friction of the part of network, which is still on the surface. This node is lifted after a distance smaller than d, whereas the other node, the one without a further connection, will be lifted only at the end of the lift operation by distance d. This e ect is ignored in the following { we simply assume that there is no friction between nodes and the surface. Thus work is only necessary for lifting nodes.
With these assumptions, we can construct a formal method of solving the shortest path problem for uniform edge length in a theoretical representation as an undirected graph. We represent the lifting of nodes simply by adding nodes to a set lift | in one lift operation all adjacent nodes of a node are lifted at the same time. This corresponds to the insertion of all adjacent nodes in one step into the set lift . The nodes in the set lift correspond to those nodes which are lifted above the surface.
As graph search we have the following algorithm: { lift = fA0g { repeat until node B0 2 lift
for each element in lift add all its adjacent nodes to lift
This is actually a breadth rst search algorithm (BFS )[
Despite the apparent similarity of both approaches, the time complexities are rather di erent. The time of the structured SSCSP-Solution is linear in the distance between A0 and B0 and the time of BFS depends on the structure of the graph. Comparing the two approaches shows immediately that in iteration i of the structured SSCSP-Solution all nodes that are i nodes or less away from A0 are lifted by d. They are all lifted simultaneously. Whereas in BFS in iteration i all nodes distance i or less are added to lift . The run-time of this depends on the implementation and the architecture available. The structured SSCSP-Solution can be seen as a kind of parallel version of BFS. However, if there are su ciently many parallel processes available and with the appropriate implementation, BFS can have a similar run-time.
Time complexity of graph algorithms usually is measured by counting the number of nodes which have to be visited during search. Instead of counting nodes, we base our complexity analysis on the physical work necessary to perform the lift operation of nodes. For the complexity of the structured SSCSP-Solution we now assume all nodes have a weight w and the strings are weightless. It requires a work of w d to lift a node. For simpli cation, let us assume that the grab operation requires also work w d. Let l(i) be the number of nodes with distance (i.e. number of nodes on shortest path) i from A0. Let the n be the distance from A to B. A node with distance i from A0 is lifted (n i + 1) times. The work required by the structured SSCSP-Solution is
For the complexity of BFS we now assume that adding nodes requires a time t for each node in the resulting set lift . For simpli cation, let us assume that the initialization of lift requires time t. The time required by BFS is w d n X(n i=0
i + 1) l(i): t n X(n
1 i)
X g(x)A : x2N(i)
1 i)
X g(x)A : x2N(i)
Comparing Equations 1 and 2 shows immediately that the work of SSCSP directly corresponds to the running time of BFS.
However, in common implementations of BFS, the run-time is not only dependent on how many nodes are added. Rather, we pick each node x in lift and then add all its adjacent nodes consecutively. This often results in nodes being added multiple times in a single iteration. Assume now that each such node addition requires time t. Let N (i) be the set of nodes that have distance i to A0. Let g(x) be the out{degree of a node x. Now, the time required by BFS is
This complexity also transfers to the structured SSCSP-Solution if we assume that each string has a weight w and the nodes are weightless. Since the nodes are weightless the grab operation requires no work and lifting a node x by d requires work g(x) w.4 The work required by the structured SSCSP-Solution is (3) (4)
The BFS is usually accelerated. In each iteration, it is enough to add only nodes adjacent to nodes newly added in the previous iteration. Here, we could show that the complexity is similar to the SSCSP -Solution if we assume that only lifting a string o the surface requires work. This, however, seems to be an unrealistic assumption; the previously lifted nodes have to be also lifted, which of course, needs more work. This is an example for an optimization of BFS which does not carry over to SSCSP.
If we do not require uniform string length between nodes, the parallels
become less clear. The most prominent approach here is Dijkstra's shortest path
algorithm[
We would like to emphasize again, that the complexity consideration in Equation 4 was done mainly to analyse the structure of the SSCSP -Solution and to compare it with the symbolic BFS. We are aware, that the representation of a problem by using mild abstractions allows very well an adaption of the physical objects to the power available for the solution. E.g. in the SSCSP -Problem from Figure 1 the entire layout of the graph and the lenghth of the strings is such, that we can do the pulling apart very easily - without beeing aware of the 'work-complexity' de ned above. 4 The work to lift a string from the surface is obviously smaller than g(x) w, because the string which corresponds to an edge is not lifted at once in entirety. Moreover, this is done in a continuous way resulting in less work. Hence, Equation 4 is an over estimation.
In this note we presented and analyzed a shortest path procedure using strong spatial cognition. We compared the approach with a symbolic graph search algorithm by estimating the amount of physical work required to construct a shortest path. We arrived at the conclusion that structure and complexity of both approaches can easily be mapped to one another. This is surprising as the solution of the problem when presented with mild abstraction, i.e. by employing physical objects, pops up immediately; we do not become aware of the internal structure and the physical complexity of the approach. In comparison, the symbolic graph-based algorithm can be designed and applied only with knowledge about data and graphs available.
What is the reason for our perception of di erent complexity of the symbolic vs. the physical problem solving approach to the shortest path problem? In the symbolic approach, we compose algorithms from structurally simple elements, using knowledge about the length of path segments and explicitly combining these elements to essentially building up the network of paths, keeping track of those parts of the network that promise to yield the shortest overall path. In comparison, in the SSC approach we do not deal with components; we do not even have to know any length to identify a shortest path. The approach exploits intrinsic spatial relations that are implicit in the network of strings and cannot be violated. For this reason it will be di cult to program the approach incorrectly. Physical a ordances and constraints do the work for us and we do not have to understand how the strings and nodes move for the approach to yield a correct result.