Algorithm #3 for Segment A

PseudoCode #3 for Task A

CIS447

Transition from C to A:

The same rubric used for Segment C can be applied to Segment A to yield a fairly simple, though inefficient algorithm. Notice that for every node there are exactly 4 directions. Using the pairing:

0 North

1 East

2 South

3 West

we can use the numbers to indicate directions. But we must fill in all slots. Those that have no hallways must be filled in with nil.

Basic Algorithm:

1. For direction = 0 to 3

a. Move in direction

b. Move back

c. Record information gained

2. If there are any unexplored nodes then:

a. Move to closest unexplored node

b. Go to Step #1

2b. Otherwise, return adjacency list that was created. DONE.

Data Structures:

*Environment*: adjacency list as it is being constructed by robot.

*eNodes*: list of nodes added to environment.

*cNodes*: list of completed nodes.

[Note: in the description below the *var* is usually written only as var].

Structural Details:

Environment: List of adjLists

adjList:

nodeNum: the node identifier

cdList: compass-direction list of neighbors, as their relative positions become

known

Example: (8 (3 1 ? ?))

nodeNum: 8

cdList: (3 1 ? ?)

Functions:

Environment functions:

moveRobi called by robot to move; argument is an integer indicating a compass point.

Updates its own environment information accordingly.

Returns an integer, indicating the node number of the node reached, and a list,

indicating whether or not there are hallways for each compass direction at that

junction.

whereAmI? called by robot to ascertain location & existence (or not) of hallways.

Returns the same pair as moveRobi, but without changing the position of the robot.

Robot functions:

curNodeOf – grabs the node number off the value given by the Environment program

hallwaysOf – grabs the hallway configuration list

addNewNode

Assumption:

newNode could actually have already been encountered. Therefore we need to

check before we take the action.

Parms:

newNode newly encountered node

Action:

If newNode Ï eNodes then:

1. eNodes ¬ cons(curNode, eNodes)

2. Create new adjList for newNode

adjList ¬ list(newNode ‘(? ? ? ?))

3. Add new adjList to Environment

Returns:

Choice: could return nothing or adjList or Environmnet

recordInfo

Parm:

curNode node to move from

neighNode neighboring node found

direction direction in which move was made to find this node

Action:

1. Fetch adjList of curNode

2. Grab cdList of adjList

3. Replace ? in direction^th slot of cdList with neighNode

4. Replace old cdList with new one in adjList

5. Replace old adjList with new one in Environmnet

Returns:

Choice: could return nothing or adjList or Environmnet

findCUnode

Parm:

curNode node to move from

Action:

1. uNodes = eNodes – cNodes

2. pathTo ¬ nil

3. treeNode ¬ List(curNode, pathTo)

4. treeNodes ¬ List(treeNode)

5. dcList ¬ directionize(cdListOf(curNode))

Note: directionize creates a list of nodes & directions

Example: cdList of node #5 = (2 6 9 8)

Then dcList of node #5 = ((0 2) (1 6) (2 9) (3 8))

6. If one of the nodes of dcList is unexplored, add its direction to the path of

curNode, and return that value.

6b. Otherwise, for each node of dcList that is not already found on treeNodes

create a treeNode for it and add that to treeNodes

7. Choose the next node of treeNodes, make that curNode, and Goto Step #3.

Returns:

Path from curNode to the nearest unexplored node.

Detailed Algorithm:

1. SetUp

a. newEnvirons ¬ whereAmI?

b. exploringNode ¬ curNodeOf(newEnvirons)

c. cNodes ¬ nil

d. eNodes ¬ nil

e. Call addNewNode(curNode)

2. Explore this node:

For direction = 0 to 3

a. If direction^th slot of cdList of curNode is nil

then Call recordInfo(exploringNode, nil, direction)

a’. Otherwise, carry out the steps below:

b. newEnvirons ¬ moveRobi(exploringNode, direction)

c. reachedNode ¬ curNodeOf(newEnvirons)

d. Call addNewNode(reachedNode, numNeighborsRN)

e. Call moveRobi(reachedNode, oppositeDir(direction))

f. Call recordInfo(exploringNode, reachedNode, direction)

3. Add explored node to completed node list

a. cNodes ¬ cons(exploringNode, cNodes)

4. Move to closest unexplored node:

a. curNode ¬ exploringNode

b. path ¬ findCUNode(exploringNode)

Note: path must be returned as a list of move directions (not nodes!)

c. While path ≠ nil

a. direction ¬ 1^st(path)

b. Pop path

g. curNode ¬ curNodeOf(moveRobi(curNode, direction)

Note: At this point we have arrived at an unexplored node

d. exploringNode ¬ curNode

e. Goto Step #2.

How the mapping process proceeds:

Frm At cdList (changes) eNodes

0 [8] 4 (4) New node to explore

4: (nil nil ? ?) {attempts to move N & E}

1 4 8 No change (4 8)

2 8 4 4: (nil nil 8 ?)

3 4 3 No change (4 8 3)

4 3 4 4: (nil nil 8 3) cNodes = (4)

5 4 8 No change New node to explore

6 8 4 No change

7 4 8 8: (4 ? ? ?)

8: (4 nil ? ?) {attempt to move E}

8 8 13 No change (4 8 13)

9 13 8 8: (4 nil 13 ?)

10 8 7 No change (4 8 13 7)

11 7 8 8: (4 nil 13 7) cNodes = (4 8)

12 8 13 No change New node to explore

13 13 8 No change

14 8 13 13: (8 ? ? ?)

13: (8 nil nil ?) {attempts to move E & S}

15 13 12 No change (4 8 13 7 12)

16 12 13 13: (8 nil nil 12) cNodes = (4 8 13)

17 13 12 No change New node to explore

18 12 10 No change (4 8 13 7 12 10)

19 10 12 12: (10 ? ? ?)

20 12 13 No change

21 13 12 12: (10 13 ? ?)

12: (10 13 nil ?) {attempt to move S}

22 12 11 No change

23 11 12 12: (10 13 nil 11) cNodes = (4 8 13 12)

24 12 10 No change New node to explore

25 10 7 No change

26 7 10 10: (7 ? ? ?)

10: (7 nil ? ?) {attempt to move E}

27 10 12 No change

28 12 10 10: (7 nil 12 ?)

29 10 9 No change (4 8 13 7 12 10 9)

30 9 10 10: (7 nil 12 9) cNodes = (4 8 13 12 10)

31 10 7 No change New node to explore

32 7 3 No change (4 8 13 7 12 10 9 3)

33 3 7 7: (3 ? ? ?)

34 7 8 No change

35 8 7 7: (3 8 ? ?)

36 7 10 No change

37 10 7 7: (3 8 10 ?)

7: (3 8 10 nil) {attempt to move W} cNodes = (4 8 13 12 10 7)

38 7 3 No change New node to explore

3: (nil ? ? ?) {attempt to move N}

39 3 4 No change

40 4 3 3: (nil 4 ? ?)

41 3 7 No change

42 7 3 3: (nil 4 7 ?)

43 3 2 No change (4 8 13 7 12 10 9 3 2)

44 2 3 3: (nil 4 7 2) cNodes = (4 8 13 12 10 7 3)

45 3 2 No change New node to explore

2: (nil ? ? ?) {attempt to move N}

44 2 3 No change

45 3 2 2: (nil 3 ? ?)

46 2 6 No change (4 8 13 7 12 10 9 3 2 6)

47 6 2 2: (nil 3 6 ?)

48 2 1 No change (4 8 13 7 12 10 9 3 2 6 1)

49 1 2 2: (nil 3 6 1) cNodes = (4 8 13 12 10 7 3 2)

50 2 6 No change New node to explore

51 6 2 No change

52 2 6 6: (2 ? ? ?)

6: (2 nil nil ?) {attempts to move E & S}

53 6 5 No change (4 8 13 7 12 10 9 3 2 6 1 5)

54 5 6 6: (2 nil nil 5) cNodes = (4 8 13 12 10 7 3 2 6)

55 6 5 No change New node to explore

56 5 1 No change

57 1 5 5: (1 ? ? ?)

58 5 6 No change

59 6 5 5: (1 6 ? ?)

60 5 9 No change

61 9 5 5: (1 6 9 ?)

5: (1 6 9 nil) {attempt to move W}cNodes =(4 8 13 12 10 7 3 2 6 5)

62 5 1 No change New node to explore

1: (nil ? ? ?) {attempt to move N}

63 1 2 No change

64 2 1 1: (nil 2 ? ?)

65 1 5 No change

66 5 1 1: (nil 2 5 ?)

1: (nil 2 5 nil) cNodes =(4 8 13 12 10 7 3 2 6 5 1)

67 1 5 No change {move to CUnode}

67 5 9 No change New node to explore

68 9 5 No change

69 5 9 9: (5 ? ? ?)

70 9 10 No change

71 10 9 9: (5 10 ? ?)

72 9 11 No change (4 8 13 7 12 10 9 3 2 6 1 5 11)

73 11 9 9: (5 10 11 ?)

9: (5 10 11 nil) cNodes =(4 8 13 12 10 7 3 2 6 5 1 9)

74 9 11 No change New node to explore

75 11 9 No change

76 9 11 11: (9 ? ? ?)

77 11 12 No change

78 12 11 11: (9 12 ? ?)

11: (9 12 nil nil) {attempts to move S & W}

cNodes =(4 8 13 12 10 7 3 2 6 5 1 9 11)

All nodes completed. Return the adjacency list for the environment.

Þ ALGORITHM COMPLETE

Discussion

1. By the analysis below, there are 17 hallways to traverse. Therefore each hallway is being traversed, on the average, more than 4 times.

2. As mentioned before, this algorithm is much easier and quicker to code. Thus, it fits the bill of a “rapid prototype”. And from a simulation standpoint, the inefficiency does not play a critical role. But, as stated before, there are many real world cases where we need to find the optimal path for the robot to follow to accomplish its task.

Analysis of Environment as a Graph

Degrees of each vertex:

1. 2 2. 3 3. 3 4. 2 5. 3 6. 2 7. 3 8. 3 9. 3 10. 3 11. 2 12. 3 13. 2

Sum of degrees vertices = 34

Therefore the number of edges = 17