Exploration and Navigation Using Hierarchical Cognitive Maps

Nestor Schmajuk1 and  Horatiu Voicu 2
1 Department of Psychological and Brain Sciences, Duke University
2 Institute for Intelligent Systems, University of Memphis

Chapter Outline & Navigation

Return to Cyberchapter

Appendix A: Cognitive Map Memory Size

Appendix B: Decision Time

Appendix C: Description of the Associative Network

Appendix D: Basic Procedures

Appendix E: Updating the Upper Level Map

Appendix  D: Basic Procedures

Under the supervision of the control system, different blocks are activated, thereby processing information in alternative ways in order (a) to decide whether all places in a given region have been examined and (b) to create new regions.

Figure D1. Examined places. Under the supervision of the control system, the current place  activates the following representations: current region , all places in current region , the goal of all places in the current region being examined . Thick lines represent flow of information.

 

Figure D2. Examined places. The activation of g1 depends on the active places and the values of the associations between places and the exploratory goal.

 

Figure D3. Examined places. The agent represented with a gray oval examines places 2, 3, 4, 6, 7, 8, 10, 11, and 12. Places 2, 6, and 10 are occupied by obstacles. Places 1, 5, and 9 remain unexamined. Black lines radiating from the agent represent sensors, black circles represent examined places, and white circles represent unexamined places. Places 2, 6 and 10 contain an obstacle.

Examined places. While moving through a region, the representation of the current place (see  in Figure D1) activates the representation of the region where that place is located through place-region associations (see  in Figure D1). In turn, region-place associations activate the representations of all places in that region (see  in Figure D1) and, as explained below, through place-exploratory goal associations the agent is able to determine whether or not all places have been examined (see  in Figure D1).

Figure D2 shows the unit that stores the connections, Wi,g1, between places and the goal being examined (see Figure 3). When all the places that belong to the current region are activated, if all Wi,g1 are zero, then g1 Api Wi,g1 = 0. This means that the whole region has been examined. If, on the other hand, there is at least one place for which Wi,g1> 0, then there still are unexamined places.

Figure D3 shows that places adjacent to examined places and occupied by obstacles are counted as examined (places 2, 6, and 10). Places that are not adjacent to examined places due to the presence of obstacles and therefore out of the reach for the agent's sensors, are counted as unexamined places (places 1, 5, 9).

Creation of a new region. If not all places have been examined (g1 > 0), then some unexplored places in the region are unreachable when the agent is at any place of the already explored places. Therefore, a new subregion should be defined.

There are three possible cases concerning the status of an explored region.

Case 1: All places can be examined, there are no obstacles. Figure D4 shows 6 accessible places in a region that has not been explored. Because the agent can enter all the places in the regions the weights connecting all place representations remain equal to 1. When the agent applies the examined places procedure mentioned above, g1 equals 0.

Figure D4. Accessibility: Continuous region. All places are examined and the region remains the same.

Case 2: All places can be examined, some contain obstacles. Figure D5 shows 5 accessible places in an unexplored region. Because place 2 cannot be entered, the connections between the representations of all places and place 2 are set to 0. All other connections remain equal to 1. As before, when the agent applies the examined places procedure, g1 equals 0. Even if place 2 is occupied by an obstacle, it is considered as examined.

Figure D5. Accessibility: Continuous region with one obstacle. All places are examined. The region remains the same.

 Case 3: Not all places can be examined. Figure D6 shows 4 accessible places in a region that has not been explored. When the agent is in place 1 or place 4, because places 2 and 5 are not accessible their connectivity with places 1 and 4 are made equal to 0, whereas the connection between place 1 and place 4 stays equal to 1. As mentioned, places 2 and 5 are occupied by obstacles and are considered as examined. Because they are out of reach for the sensors of the agent, place 3 and 6 are considered unexamined. Therefore, when the agent applies the examined places procedure, g1 is greater than 0. This result indicates that there are unexamined places that are disconnected from places 1 and 4, and therefore, two new subregions should be defined.

Figure 6. Accessibility: Continuous region. All places are examined and the region remains the same.

In order to update the place-region and region-place connections, the system activates the representation of the examined places (see Figure D7) and the representation of region E, and as a consequence, places E1, E2, E4 and E5 remain part of that region. At the same time because the representations of the unexamined places are not active when the representation of region E is active,  unexamined places E3 and E6 are disconnected  from region E. When the previous step is completed, because region E has not been completely explored, a new region E' is connected to the unexamined places E3 and E6.

Figure D7. Connected places. By using the LLM the control system activates the following representations: the goal of examined places in the current region  and then all examined places in the current region . Thick lines represent flow of information.


 

        2005 All copyrights for the individual chapters are retained by the authors. All other material in this book is copyrighted by the editor, unless noted otherwise. If there has been an error with regards to unacknowledged copyrighted material, please contact the editor immediately so that this can be corrected. Permissions for using material in this book should be sent to the editor.