Developing Spatial Sense in a 3D-Block-world
Kaustuv DeBiswas | MIT | Fall 07 | Prof. Whitman Richards



Project Description | Previous Work | Algorithm | Discussion


Imagine yourself in an unknown city wandering around the streets trying to acquire a spatial understanding of the neighborhood. Such map making or developing a sense of place is prevalent in our everyday lives. Once you form a mental model of your neighborhood not only can you describe how to go from one node (say your hotel) to another node (the nearest coffee shop), but also, with all your human genius, ascertain shortest routes to places and mark landmarks on the way. The problem at hand is to query such a map making process and formalize a technique whereby an autonomous agent (a mobile robot) can generate a topological map of an unknown world and place landmarks through exploration.

Topological map making in simple graph like worlds have been dealt with previously [Dudek, Freedman and Hadjres, 1993] . However the model ignores some of the available and vivid 'intrinsic' knowledge structure of the agent (eg. Distance and Direction metrics). Considering just the topological connections of the graph world leads to ambiguity and errors. Though the model introduces the concept of an extended signature for ascertaining the uniqueness of every node, it is not a robust algorithm for more complex worlds than the examples cited in the paper.

In this work, the mobile robot traverses in three dimensional block like worlds and as it explores such a world, generates a topological map of the world in its memory. It also additionally locates possible landmarks using statistical analysis of the codimensions of the nodes in the map.

Additionally, the project enquires whether multiple agents can collaboratively develop a global map.

The project is divided into the following two parts:

Part A

Generation of a topological map of a three-dimensional block world through agent exploration.

*Idea of memory | Humans don't have perfect memory

*Idea of Landmarks | Humans express directions using landmarks

Part B

Collaborative Map making -> Is there a way agents can talk to each other about their experience and collectively form a global understanding?


Following is a video of the current program at run time:

The video content presented here requires JavaScript to be enabled and the latest version of the Macromedia Flash Player. If you are you using a browser with JavaScript disabled please enable it now. Otherwise, please update your version of the free Flash Player by downloading here.


Complex Worlds

The program is robust for large complex worlds. The following is a 26x26 block world

The agent generates the following topological graph,
+ZoomIn <A> , <B>, <C>