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 B: Decision Time

In this section we compare the decision times in non-hierarchical and hierarchical representations. For a one-dimensional environment (see Figure B1) that contains 32 places we build a hierarchical representation shown in Figure B2. This hierarchy contains multiple representations of the same environment at different resolutions. On one hand, the time to spread the activity between place 1 and place 32 only by using the representation with the highest resolution is proportional to the number of connections in between place 1 and place 32, namely 31. On the other hand, the time to spread the activity between place 1 and place 32 when all levels of the hierarchy are used is proportional to twice the depth of the hierarchy, namely 10 (= 2 * 5). This is the number of steps required by the spreading activity from place 32 to reach place 1. We can extrapolate that in general, whereas the reaction time for spreading the activity between two places in the case of a nonhierarchical representation of space is linear with the distance between the two places, in the case of a hierarchical representation of space it varies logarithmically with the distance between the two places (see Figure B3). Therefore, by using hierarchical, low-resolution representations of the environment the agent can speed the spatial planning process.

Figure B1. One-dimensional environment that contains 32 places.

 

Figure B2. Multiple level representation of a one-dimensional environment that contains 32 places.

 

Figure B3. Linear and logarithmic reaction times as a function of the distance between places. Circles represent time to spread the activity in a hierarchical representation of space; diamonds represent time to spread the activity in a non-hierarchical representation of space.

        ©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.