Algorithm #2 for Task C
CIS447
Algorithm:
1. From current node travel each hallway & back (except do not return from last hallway).
2. Make node reached from last hallway the current node. Goto #1.
Columns:
1. In red, the move number.
2. Frm = node from which move is made.
3. At = node arrived at after move is made.
4. Env’t (changes) = changes that are made to the data structure containing the environment map being constructed.
5. E-Nodes = list of nodes in the environment map at that point.
Frm At Env’t (changes) E-Nodes
Ć
0 [8] 4 4: (? ? ?) (4)
1 4 3 4: (3 ? ?)
3: (4 ? ?)
2 3 4 No change
3 4 1 4: (3 1 ?) (4 3 1)
1: (4 ? ?)
4 1 4 No change
5 4 8 4: (3 1 8) (4 3 1 8)
8: (4 ? ? ? ?)
6 8 5 8: (4 5 ? ? ?) (4 3 1 8 5)
5: (8 ? ? ?)
7 5 8 No change
8 8 11 8: (4 5 11 ? ?) (4 3 1 8 5 11)
11: (8 ? ? ?)
9 11 8 No changes
10 8 10 8: (4 5 11 10 ?) (4 3 1 8 5 11 10)
10: (8 ? ?)
11 10 8 No change
12 8 7 8: (4 5 11 10 7) (4 3 1 8 5 11 10 7)
7: (8 ? ?)
13 7 10 7: (8 10 ?) (4 3 1 8 5 11 10 7)
10: (8 ? ?) (7)
[Here we encounter the same problem as with AlgC-1, i.e., we do not know which slot node 7 goes into. The resolution, though, is slightly different, since we will not be traveling out from node 10 down an unexplored hallway. Here we simply make a single list of all nodes from which we can arrive to the current node.]
14 10 7 No change
15 7 3 7: (8 10 3)
[Now we have a new problem. We already have some information about node 3 and our algorithm calls for us to explore from node 3. Should we represent node 3 information as:
(3 3 (4 ? ?) (7))
or as: (3 3 (7 ? ?) (4)), since our orientation is from 7 and not from 4?
The second seems preferable. But then we should change the representation at move #1 to: (3 3 (? ? ?) (4)). But if we do that, then we have to do the same for all the other unexplored nodes. This yields the following restructuring of the 1st 15 moves:
0 [8] 4 4: (? ? ?) (4)
1 4 3 4: (3 ? ?)
3: (? ? ?) (4)
2 3 4 No change
3 4 1 4: (3 1 ?) (4 3 1)
1: (? ? ?) (4)
4 1 4 No change
5 4 8 4: (3 1 8) (4 3 1 8)
Completed nodes: (4)
8: (4 ? ? ? ?)
6 8 5 8: (4 5 ? ? ?) (4 3 1 8 5)
5: (? ? ? ?) (8)
7 5 8 No change
8 8 11 8: (4 5 11 ? ?) (4 3 1 8 5 11)
11: (? ? ? ?) (8)
9 11 8 No changes
10 8 10 8: (4 5 11 10 ?) (4 3 1 8 5 11 10)
10: (? ? ?) (8)
11 10 8 No change
12 8 7 8: (4 5 11 10 7) (4 3 1 8 5 11 10 7)
Completed nodes: (4 8)
7: (8 ? ?)
13 7 10 7: (8 10 ?) (4 3 1 8 5 11 10 7)
10: (? ? ?) (8 7)
14 10 7 No change
15 7 3 7: (8 10 3)
Completed nodes: (4 8 7)
3: (7 ? ?) (4)
[The reason we do not represent this node as:
3: (? ? ?) (4 7)
is that, since node 7 is done, we will be exploring out of node 3].
16 3 1 3: (7 1 4)
Completed nodes: (4 8 7 3)
[Since there is only one slot left, node 4 goes there;
Also, we must recognize that, since node 3 is now complete, we do not return there, but continue on from node 1].
1: (3 ? ?) (4)
17 1 2 1: (3 2 4) (4 3 1 8 5 11 10 7 2)
Completed nodes: (4 8 7 3 1)
[Again, we do not return to node 1, but continue on from node 2. Therefore, we do not use the normal node representation {{2: (? ? ?) (1)}}. Instead we use the representation of an “exploring” node].
2: (1 ? ?)
18 2 6 2: (1 6 ?) (4 3 1 8 5 11 10 7 2 6)
6: (? ? ? ?) (2)
19 6 2 No change
20 2 5 2: (1 6 5) (4 3 1 8 5 11 10 7 2 6 5)
Completed nodes: (4 8 7 3 1 2)
5: (2 ? ? ?)
21 5 6 5: (2 6 ? ?)
6: (? ? ? ?) (2 5)
22 6 5 No change
23 5 9 5: (2 6 9 ?) (4 3 1 8 5 11 10 7 2 6 9)
9: (? ? ?) (5)
24 9 5 No change
25 5 8 5: (2 6 9 8)
Completed nodes: (4 8 7 3 1 2 5)
8: Done
[At this point we need to choose an unexplored node to complete. If one of the neighbors of the current node fits the bill, then we do not make any extra moves. The first such node in the adjacency list for node 8 is 11. So we choose that node].
[Since we will be exploring out of this node, we change its representation from:
11: (? ? ? ?) (8)
to:
11: (8 ? ? ?)
26 8 11 11: (8 ? ? ?)
27 11 9 11: (8 9 ? ?)
9: (? ? ?) (5 11)
28 9 11 No change
29 11 12 11: (8 9 12 ?) (4 3 1 8 5 11 10 7 2 6 9 12)
12: (? ?) (11)
30 12 11 No change
31 11 10 11: (8 9 12 10)
Completed nodes: (4 8 7 3 1 2 5 11)
10: (11 ? ?) (8 7)
32 10 7 10: (11 7 8)
Completed nodes: (4 8 7 3 1 2 5 11 10)
Since node 10 is complete, we look at all the neighbors of node7. But we find that they are all complete also. Can we find our way to an unexplored node (hopefully the closest one)? The unexplored nodes are: (6 9 12). This, unfortunately, is not a trivial problem. Even though the path to each of these nodes has a length of 3, the search tree constructed looking for that path has 33 nodes on it! If there were 50 or 100 nodes in the environment the size of the search tree could be immense.
Our goal is to find a simple way to prune the tree. Since we are studying state-space search, it is worthwhile working out the details. We start out building a search tree as above, except that we never add a state that is already present. This guarantees that the number of nodes on the search tree will never exceed the number of states (nodes in our environment). Creating a search tree from node 7 (state 7) gives us the figure below.
If we build this tree in a breadth-first manner we are guaranteed to find the path and it will be the shortest one. It is obvious that a path will be found, since every state will eventually be placed into the tree. But, can there be a shorter one? Then, in the complete search tree the goal node must be found at a higher level. Moreover, at some point the path to it must have been pruned. I.e., the state that would have been placed into the tree must already be in the tree at the same or at a higher level.
But, in that case the complete search tree must have another path to the goal – a path that is equal or shorter in length. And that path is either in the pruned search tree or not. If it is not, we repeat the above argument for the new path until, eventually, the path (i.e., the shortest path) will be in the pruned search tree. So this method is both complete and optimal.
Applying this to our situation we head from node 7 to node 6 via the shortest route.
33 7 8 No change
34 8 5 No change
35 5 6 No change
36 6 2 6: (5 ? ? ?) (2)
6: (5 2 ? ?)
[Since we do not know what the relationship between 2 & 5 is, we do not know how to avoid going there for naught. So we revert to our old strategy: move CW with respect to the from direction].
2: done
37 2 6 No change
38 6 12 6: (5 2 12 ?)
12: (? ?) (11)
12: (6 11)
39 12 6 No change
40 6 9 6: (5 2 12 9)
9: (? ? ?) (5 11)
9: (6 ? ?) (5 11)
41 9 11 9: (6 ? ?) (5 11)
9: (6 11 5)
All nodes completed. Return the adjacency list for the environment.
Ţ ALGORITHM COMPLETE
Discussion
1. This algorithm required 10 more moves, which translates into a 32% increase.
2. On the other hand this algorithm should be easier to implement, although it requires that we also code the “find nearest unexplored node” algorithm.
3. If time permits we will look at both algorithms at the pseudo-code level, starting with the second one.