Algorithm #1 for Task C
CIS447
Algorithm:
1. Using from-node as reference, rotating clockwise choose 1st unexplored hallway.
2. If all hallways at the current node are explored, pop stack and backtrack.
3. If stack is empty, then return the environment as an adjacency list of nodes.
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. Stack = sequence of nodes visited; used for backtracking.
5. Env’t (changes) = changes that are made to the data structure containing the environment map being constructed.
6. E-Nodes = list of nodes in the environment map at that point.
Frm At Stack Env’t (changes) E-Nodes
Æ Æ
0 [8] 4 (4) 4: (? ? ?) (4)
1 4 3 (4 3) 4: (? 3 ?)
3: (4 ? ?) (4 3)
2 3 7 (4 3 7) 3: (4 7 ?)
7: (3 ? ?) (4 3 7)
3 7 8 (4 3 7 8) 7: (3 8 ?)
8: (7 ? ? ? ?) (4 3 7 8)
4 8 4 (4 3 7 8 4) 8: (7 4 ? ? ?)
4: (8 3 ?) (4 3 7 8)
5 4 1 (4 3 7 8 4 1) 4: (8 3 1)
1: (4 ? ?) (4 3 7 8 1)
6 1 3 (4 3 7 8 4 1 3) 1: (4 3 ?)
3: (4 7 1)
[Even though arrival is NOT from 4, we can place the 1 into 3’s neighbors, since there is only 1 ? to fill;
AtNode is complete Þ pop the stack & backtrack]
7 3 1 (4 3 7 8 4 1) None (4 3 7 8 1)
8 1 2 (4 3 7 8 4 1 2) 1: (4 3 2)
2: (1 ? ?) (4 3 7 8 1 2)
9 2 6 (4 3 7 8 4 1 2 6) 2: (1 6 ?)
6: (2 ? ? ?) (4 3 7 8 1 2 6)
10 6 12 (4 3 7 8 4 1 2 6 12)
6: (2 12 ? ?)
12: (6 ?) (4 3 7 8 1 2 6 12)
11 12 11 (4 3 7 8 4 1 2 6 12 11)
12: (6 11)
11: (12 ? ? ?) (4 3 7 8 1 2 6 12 11)
12 11 10 (4 3 7 8 4 1 2 6 12 11 10)
11: (12 10 ? ?)
10: (11 ? ?) (4 3 7 8 1 2 6 12 11 10)
13 10 7 (4 3 7 8 4 1 2 6 12 11 10 7)
10: (11 7 ?)
7: (3 8 10) [arrival is NOT from 3].
AtNode is complete Þ pop the stack & backtrack.
14 7 10 (4 3 7 8 4 1 2 6 12 11 10)
No changes
15 10 8 (4 3 7 8 4 1 2 6 12 11 10 8)
10: (11 7 8)
[Arrival is NOT from 7 & Node 8 has 5 neighbors. Therefore we do not know where to place Node 10. Even worse, we cannot choose the next unexplored hallway because we have lost our orientation to nodes 7 & 4. Because this will be a problem unless we come to 8 from 7 or 4 (and would be an even greater problem if the max # of nodes was, say, 10) we look for a new representation.
Currently: (nodeNum (nghbr nghbr . . nghbr))
New: (nodeNum numNghbrs (nghbr. . nghbr) ((nghbor . . nghbr) . . (nghbor . . nghbr))
The last list-of-lists contains incomplete information. As soon as any node there matches any other node in our lists, we can merge the lists.]
Current Environment:
(
(4 3 (8 3 1) ())
(3 3 (4 7 1) ())
(7 3 (3 8 10) ())
(8 5 (7 4 ? ? ?) ((10 ? ? ? ?))
(1 3 (4 3 2) ())
(2 3 (1 6 ?) ())
(6 4 (2 12 ? ?) ())
(12 2 (6 11) ())
(11 4 (12 10 ? ?) ())
(10 3 (11 7 8) ())
)
ReStart:
15 10 8 (4 3 7 8 4 1 2 6 12 11 10 8)
10: (11 7 8)
8: 5 (7 4 ? ? ?) ((10 ? ? ? ?))
(4 3 7 8 1 2 6 12 11 10)
[Here we seem to have a choice – take 1st CW from 4 or from 10. In reality, though, we have no choice, since we do not know which hallway leads to node 4. So we must go CW from 10].
16 8 7 (4 3 7 8 4 1 2 6 12 11 10 8 7)
8: (7 4 ? ? ?) ((10 7 ? ? ?))
[Now we can merge the main representation with the “side” representation].
8: (10 7 4 ? ?) ()
[Since 7 is completed, we pop & backtrack].
17 7 8 (4 3 7 8 4 1 2 6 12 11 10 8)
[And since we have regained our overall orientation at 8, we can return to our main algorithm].
18 8 5 (4 3 7 8 4 1 2 6 12 11 10 8 5)
8: (10 7 4 5 ?)
5: (8 ? ? ?) (4 3 7 8 1 2 6 12 11 10 5)
19 5 2 (4 3 7 8 4 1 2 6 12 11 10 8 5 2)
5: (8 2 ? ?)
2: (1 6 5)
[Pop & backtrack]
20 2 5 (4 3 7 8 4 1 2 6 12 11 10 8 5)
No changes
21 5 6 (4 3 7 8 4 1 2 6 12 11 10 8 5 6)
5: (8 2 6 ?)
6: (2 12 ? ?) ((5 ? ? ?))
22 6 2 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 2)
6: (2 12 ? ?) ((5 2 ? ?))
6: (5 2 12 ?) ()
2: complete
[Pop & backtrack]
23 2 6 (4 3 7 8 4 1 2 6 12 11 10 8 5 6)
No changes
24 6 9 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 9)
6: (5 2 12 9)
9: (6 ? ?) (4 3 7 8 1 2 6 12 11 10 5 9)
25 9 11 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 9 11)
9: (6 11 ?)
11: (12 10 ? ?) ((9 ? ? ?))
26 11 12 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 9 11 12)
11: (12 10 ? ?) ((9 12 ? ?))
11: (9 12 10 ?) ()
12: complete
[Pop & backtrack]
27 12 11 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 9 11)
No changes
28 11 8 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 9 11 8)
11: (9 12 10 8)
8: (10 7 4 5 11)
[Pop & backtrack]
29 8 11 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 9 11)
Done
[Pop & backtrack]
30 11 9 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 9)
No changes
31 9 5 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 9 5)
9: (6 11 5)
5: 5: (8 2 6 9)
[Pop & backtrack]
32 5 9 (4 3 7 8 4 1 2 6 12 11 10 8 5 6 9)
9: done
[Pop & backtrack]
33 9 6 (4 3 7 8 4 1 2 6 12 11 10 8 5 6)
6: done
[Pop & backtrack]
34 6 5 (4 3 7 8 4 1 2 6 12 11 10 8 5)
5: done
[Pop & backtrack]
35 5 8 (4 3 7 8 4 1 2 6 12 11 10 8)
8: done
[Pop & backtrack]
36 8 10 (4 3 7 8 4 1 2 6 12 11 10)
10: done
[Pop & backtrack]
37 10 11 (4 3 7 8 4 1 2 6 12 11)
11: done
[Pop & backtrack]
38 11 12 (4 3 7 8 4 1 2 6 12)
12: done
[Pop & backtrack]
39 12 6 (4 3 7 8 4 1 2 6)
6: done
[Pop & backtrack]
40 6 2 (4 3 7 8 4 1 2)
2: done
[Pop & backtrack]
41 2 1 (4 3 7 8 4 1)
1: done
[Pop & backtrack]
42 1 4 (4 3 7 8 4)
4: done
[Pop & backtrack]
43 4 8 (4 3 7 8)
8: done
[Pop & backtrack]
44 8 7 (4 3 7)
7: done
[Pop & backtrack]
45 7 3 (4 3)
3: done
[Pop & backtrack]
46 3 4 (4)
4: done
[Pop]
()
Þ ALGORITHM COMPLETE
Discussion
1. There is no move #0. The fromNode is listed to show original orientation of robot.
2. At moves 1 & 4 a trick is used, since we know that the 1st time we arrive back at the starting node the node we came from is the original orienting fromNode. This may be more work to implement than it is worthwhile.
3. At move #31, if we checked all the Environment information we would see that all the nodes are completed. Therefore, we do not need to backtrack. We could simply return the map at that point and save 15 unnecessary moves. In that case the total number of moves would be 31. Given that there are 20 edges in the graph, that is still a fairly high number of moves.
4. For a larger environment, if we encountered situations where the backtracking occurs for many nodes in sequence, we could investigate whether it would speed things up to seek the shortest route back to the first unfinished node.