PseudoCode #3 for Task C

 

CIS447

 

Note:

Although the information below is oriented toward Lisp notation, it can easily be adapted to any programming language.  For example, most Lisp lists can be transformed into 1-d arrays and lists of lists can be represented fairly easily as simple structured data types, e.g., structs of C or Types of Visual Basic.

 

Incremental Development:

The Principle of Incremental Development (PID) calls for writing and testing code in increments.  The increments can be whole pieces (e.g., functions) or layers.  The layers can be individual pieces which are written in skeleton form, then expanded upon at subsequent stages of development.  Or they can be aggregations of individual pieces, again expanded upon/ added to layer by layer.

 

Agile Project Development:

A fairly recent innovation in software development is Agile Project Development (APD) or Agile Programming.  There are forms of APD, but most have as a basic ingredient the idea that a deliverable is prepared at specified intervals (e.g., every 30 days).

 

Rapid Prototyping:

Often a very skeletal form of a software project, called a prototype, is developed as a “proof of concept”.  If this is more than just “bare bones” it can be the 1st deliverable of the APD approach.  Or, it can be fleshed out to create the 1st deliverable.

 

Application to Project #3:

Segments B, C & D of Project #3 present a conceptual challenge.  The actual coding is not as difficult as is the process of mapping out a good strategy and creating the maximally efficient algorithm.  Thus, it becomes a good place to apply PID & APD.  One way to create a rapid prototype is to ignore issues of efficiency and simply adopt the strategy of choosing an algorithm that is easiest to code.  Thus, we have Algorithm #3 for Segment C of the project.

 

Basic Algorithm:

1. For direction = 0 to numNeighbors

   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

numNeighs: number of neighboring nodes

cwList: clockwise list of neighbors, as their relative positions become known

    Example: (8 5 (3 1 ? ? ?))

nodeNum: 8

numNeighs: 5

cwList: (3 1 ? ? ?)

 

Functions:

 

Environment functions:

     moveRobi called by robot to move; argument is an integer indicating a hallway

calculated CW starting with the “from” hallway.

Updates its own environment information accordingly. 

Returns a pair of integers indicating the node number of the node reached and the

number of hallways that meet at that junction.

     whereAmI? called by robot to ascertain location & number 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

     numNeighborsOf – grabs the number of neighbors

     addNewNode

Assumption:

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

check before we take the action.

Parms:

   newNode newly encountered node

   numNeighs number of

Action:

 If newNode Ï eNodes then:

   1. eNodes ¬ cons(curNode, eNodes)

   2. Create new adjList for newNode

        adjList ¬ list(newNode numNeighs (makeCWlist numNeighs))

   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 cwList of adjList

   3. Replace ? in directionth slot of cwList with neighNode

   4. Replace old cwList with new one in adjList

   5. Replace old adjList with new one in Environmnet

Returns:

  Choice: could return nothing or adjList or Environmnet

     findCUnode

Assumption:

   It is assumed that curNode’s orientation matches that associated with its cwList. If

that assumption cannot be guaranteed, it would be necessary to reorient the robot.

Parm:

   curNode node to move from

Action:

   1. uNodes = eNodes – cNodes

   2. pathTo ¬ nil

   3. treeNode ¬ List(curNode, pathTo)

   4. treeNodes ¬ List(treeNode)

   5. dwList ¬ directionize(cwListOf(curNode))

Note: directionize creates a list of nodes & directions

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

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

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

curNode, and return that value.

   6b. Otherwise, for each node of cwList 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.

 

Basic Algorithm:

1. For direction = 0 to numNeighbors

   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.

 

Detailed Algorithm:

1. SetUp

  a. newEnvirons ¬ whereAmI?

  b. exploringNode ¬ curNodeOf(newEnvirons)

  c. numNeighbors ¬ numNeighborsOf(newEnvirons)

  d. cNodes ¬ nil

  e. eNodes ¬ nil

  f. Call addNewNode(curNode, numNeighbors)

2. Explore this node:

     For direction = 0 to numNeighbors

  a. newEnvirons ¬ moveRobi(exploringNode, 1)

  Note: The robot’s orientation is always with respect to the hallway it just came from

          – therefore the 1 direction is immediately CW from its orientation.  This guarantees

that every hallway will be explored.

  b. reachedNode ¬ curNodeOf(newEnvirons)

  c. numNeighborsRN ¬ numNeighborsOf(newEnvirons)

  d. Call addNewNode(reachedNode, numNeighborsRN)

  e. Call moveRobi(reachedNode, 0)

  Note: The direction the robot came from is always the 0 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 ¬ 1st(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.

 

The mapping process proceeds quite differently now:

 

Frm  At    cwList (changes)    eNodes

 

                                                      Æ

 

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

1 4    3      No change                  (4 3)

2 3    4      4: (3 ? ?)                  

3 4    1      No change                  (4 3 1)

4 1    4      4: (3 1 ?)

5 4    8      No change                  (4 3 1 8)

6 8    4      4: (3 1 8)                                           cNodes = (4)

7 4    8      No change                                          New node to explore

8 8    5      No change                  (4 3 1 8 5)

9 5    8      8: (5 ? ? ? ?)

10 8  11     No change                  (4 3 1 8 5 11)

11 11 8      8: (5 11 ? ? ?)

12 8  10     No change                  (4 3 1 8 5 11 10)

13 10  8     8: (5 11 10 ? ?)

14 8  7      No change                  (4 3 1 8 5 11 10 7)

15 7  8      8: (5 11 10 7 ?)

16 8  4      No change

17 4  8      8: (5 11 10 7 4)                                          cNodes = (4 8)

18 8  5      No change                                          New node to explore

19 5  2      No change                  (4 3 1 8 5 11 10 7 2)

20 2  5      5: (2 ? ? ?)

21 5  6      No change                  (4 3 1 8 5 11 10 7 2 6)

22 6  5      5: (2 6 ? ?)

23 5  9      No change                  (4 3 1 8 5 11 10 7 2 6 9)

24 9  5      5: (2 6 9 ?)

25 5  8      No change

26 8  5      5: (2 6 9 8)                                        cNodes = (4 8 5)

23 5  2      No change                                          New node to explore

24 2  1      No change

25 1  2      2: (1 ? ?)

24 2  6      No change

25 6  2      2: (1 6 ?)

26 2  5      No change

27 5  2      2: (1 6 5)                                           cNodes = (4 8 5 2)

28 2  1      No change                                          New node to explore

29 1  4      No change

30 4  1      1: (4 ? ?)

31 1  3      No change

32 3  1      1: (4 3 ?)

33 1  2      No change

34 2  1      1: (4 3 2)                                           cNodes = (4 8 5 1)

35 2  1      No change                                          New node to explore

36 1  3      No change

36 3  4      No change

37 4  3      3: (4 ? ?)

38 3  7      No change

39 7  3      3: (4 7 ?)

40 3  1      No change

41 1  3      3: (4 7 1)                                           cNodes = (4 8 5 1 3)

42 3  7      No change                                          New node to explore

43 7  8      No change

44 8  7      7: (8 ? ?)

45 7  10     No change

46 10  7     7: (8 10 ?)

47 7  3      No change

48 3  7      7: (8 10 3)                                         cNodes = (4 8 5 1 3 7)

49 7  10     No change                                          New node to explore

50 10  8     No change

51 8  10     10: (8 ? ?)

52 10  11   No change

53 11  10   10: (8 11 ?)

54 10  7     No change

55 7  10     10: (8 11 7)

54 10  7     No change

55 7  10     10: (8 11 7)                                        cNodes = (4 8 5 1 3 7 10)

56 10 11    No change                                          New node to explore

57 11  8     No change

58 8  11     11: (8 ? ? ?)

59 11  9     No change

60 9  11     11: (8 9 ? ?)

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

62 12  11   11: (8 9 12 ?)

63 11  10   No change

64 10  11   11: (8 9 12 10)                           cNodes = (4 8 5 1 3 7 10 11)

65 11 9     No change                                  New node to explore

66 9  5      No change

67 5  9      9: (5 ? ?)

68 9  6      No change

69 6  9      9: (5 6 ?)

70 9  11     No change

71 11  9     9: (5 6 11)                                 cNodes = (4 8 5 1 3 7 10 11 9)

72 9  6     No change                                  New node to explore

73 6  5      No change

74 5  6      6: (5 ? ? ?)

75 6  2      No change

76 2  6      6: (5 2 ? ?)

77 6  12     No change

78 12  6     6: (5 2 12 ?)

79 6  9      No change

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

81 6  2      No change                                  New node to explore

82 2  5      No change

83 5  2      2: (5 ? ?)

84 2  1      No change

85 1  2      2: (5 1 ?)

86 2  6      No change

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

88 2  6      No change

89 6  12     No change                          New node to explore

90 12 11    No change

91 11  12   12: (11 ?)

92 12 6      No change

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

 

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

                                Þ   ALGORITHM COMPLETE

 

Discussion

 

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

2. In fact, the 93 moves is exactly 3 times the number of moves of Algorithm #1.

3. On the other hand, 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.

4. Can the inefficiency be ignored, then?  Clearly not.  Suppose instead of hallways we are looking at streets, or suppose they are hallways but it takes a long time for the robot to travel down each hallway.  In that case reducing the number of edges (be they hallways or streets) traveled would become important.  And it would be well worth our while to devise the optimal map-making algorithm.

 

Analysis of Environment as a Graph

 

Degrees of each vertex:

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

 

Sum of degrees vertices = 40

 

Therefore the number of edges = 20