Image based navigation of autonomous agents - biologically inspired orientation strategies in open environments

View-based homing using snapshots [1997-1, 1998-2]

The snapshot theory has been developed by Cartwright and Collett (1987, Biol. Cybern. 57, 85-93) to explain the search behaviour of honey bees which enables them to relocate a food source using a snapshot of the surrounding scenery taken during a previous visit. The direction of the food source after a displacement can be inferred from the actual view by comparing it to the snapshot: image regions in the direction of the displacement are expanded while the image in the direction of the food source is contracted.

To estimate the goal direction we warp the current view using pre-defined parameterized displacement fields that are typically generated by a translation in cylindrical environments. The parameters obtained from the best match between warped view and snapshot are used to determine in which direction the robot has to drive next. The computational simplicity of this algorithm allows for a continuous home vector calculation at frame rate. The map shows the computed home vectors for all positions in our toy house arena (gif 168K). The catchment area is depicted in blue, trajectories of the homing robot in red. The image database used for this plot can be downloaded here.

View graph representation of space [1995-1, 1997-2,3, 1998-1]

In contrast to traditional robotics approaches, where space is represented by a global metric map, our research has been focused on generating spatial behaviour from graphs consisting of connected views. Connections are established by simple behaviours, such as (in mazes) turning and wall-following, or, in open environments, homing (as described above).

In discretized environments such as mazes (gif 35K), snapshots are taken at junctions - the only locations where movement decisions need to be taken. Open environments require exploration strategies that allow the acquisition of useful snapshots to define nodes of the view graph (gif 28K).

In our approach, we use the Euclidian image distance to the already known snapshots as a criterion. If the current view is sufficiently different, a new snapshot is taken. The above image shows the image distance map for a snapshot taken in the center of a toy house arena. The color temperature corresponds to the minimum distance which can be obtained by rotating the respective views (cf. 1997-2).

Robot implementation [1995-2, 1997-2, 1998-1]

Our algorithms for view-based homing and graph learning were developed and tested first in simple two-dimensional worlds (gif 28K), then in VR environments (gif 56K) generated with Performer (TM), before we built a first robot version. (gif 140K)

To record 360-degree views (gif 262K) we use a video camera pointing to a conical mirror. The camera system is mounted on top of a Khepera (R) (gif 77K) miniature robot which is used for experiments in toy-like worlds (gif 168K). The same camera system is also used on our new fully autonomous prototype Toaster (gif 203K) with on-board PC for indoor navigation.


Documents

1998
  1. Franz, M.O., Schölkopf, B., Mallot, H.A. & Bülthoff, H.H. 1998. Learning View Graphs for Robot Navigation. Autonomous Robots, 5, 111-125
  2. Franz, M.O., Schölkopf, B., Mallot, H.A. & Bülthoff, H.H. 1998. Where did I take that snapshot? Scene-based homing by image matching. Biol. Cybern. 79, 191-202
  3. Franz, M.O., Hengstenberg, R., & Krapp, H.G. 1998. VS-neurons as matched filters for self-motion-induced optic flow fields. In N. Elsner, R. Wehner (Eds.): Göttingen Neurobiology Report 1998. Proc. 26th Göttingen Neurobiology Conf. 1998, Vol. II, p. 419, Georg Thieme Verlag, Stuttgart (1 page, 56K)
  4. Franz, M.O., Schölkopf, B., Mallot, H.A., Bülthoff, H.H. & Zell, A. 1998. Navigation mit Schnappschüssen. In P. Levi, R.-J. Ahlers, F. May, M. Schanz (Eds.): Mustererkennung 1998. Proc. 20. DAGM-Symposium, pp. 421-428, Springer, Berlin (8 pages, 725K)
  5. Franz, M.O. & Krapp, H.G. 1998. Wide-field, motion-sensitive neurons and optimal matched filters for optic flow. (Technical Report No. 61, MPIK, June 1998, 18 pages, 453 K) [Abstract].
  6. Mallot, H.A. & Franz, M.O. 1998. Mechanisms of Navigation and Spatial Memory. Tutorial SAB 98 (8 pages, 148K)
  7. Huber, S.A., Franz, M.O. & Bülthoff, H.H. 1998. On robots and flies: Modeling the visual orientation behavior of flies. Subm. to Robotics and Autonomous Systems (31 pages, 505K)
  8. Franz, M.O. & Mallot, H.A. 1998. Biomimetic robot navigation. Subm. to Robotics and Autonomous Systems (Technical Report No. 65, MPIK, October 1998, 17 pages, 168 K) [Abstract].
  9. Franz, M.O 1998. Minimalistic visual navigation. PhD thesis, Departm. Computer Science, Eberhard-Karls-Universität Tübingen, VDI Verlag, Düsseldorf (in press).
  10. Distler, H.K., Van Veen, H.A.H.C., Braun, S.J., Heinz, W., Franz, M.O. & Bülthoff, H.H. 1998. Navigation in real and virtual environments: Judging orientation and distance in a large-scale landscape. In M. Göbel, J. Landauer, M. Wapler, U. Lang (Eds.): Virtual Environment '98: Proc. Eurographics Workshop Stuttgart, Springer, Wien.
1997
  1. Franz, M.O., Schölkopf, B. & Bülthoff, H.H. 1997. Homing by parameterized scene matching. In P. Husbands, I. Harvey (Eds.): Proc. 4th European Conf. on Artificial Life, pp. 236 - 245, MIT Press, Cambridge [Abstract].
  2. Franz, M.O., Schölkopf, B., Georg, P., Mallot, H.A. & Bülthoff, H.H. 1997. Learning View Graphs for Robot Navigation. In W. L. Johnson (ed.): Proceedings of the First International Conference on Autonomous Agents, pp. 138 - 147, ACM Press, New York [Abstract].
  3. Mallot, H.A., Franz, M.O., Schölkopf, B. & Bülthoff, H.H. 1997. The View-Graph Approach to Visual Navigation and Spatial Memory. In W. Gerstner, A. Germond, M. Hasler, J.-D. Nicoud: Proc. 7th Intl. Conf. Artificial Neural Networks, ICANN 97, pp. 751-756, Springer Lecture notes in Computer Science (6 pages, 397 K)
1996
  1. Franz, M.O., Schölkopf, B., Mallot, H.A. & Bülthoff, H.H. 1996. Aktives Erwerben eines Ansichtsgraphen zur diskreten Repräsentation offener Umwelten. In M. Thielscher, S.-E. Bornscheuer (Eds.), Fortschritte der Künstlichen Intelligenz, 20. Jahrestagung für künstliche Intelligenz (KI96), p.92 Dresden. Dresden University Press (1 page, 14K)
1995
  1. Franz, M. & Zhang, M. 1995. Supression and creation of chaos in a periodically forced Lorenz system. Phys. Rev. E, 52:3558-3565.

Further publications on view graphs

1997
  1. Gillner, S. and Mallot, H.A. 1997. Navigation and acquisition of spatial knowledge in a virtual maze. Journal of Cognitive Neuroscience 10:445-463 [Abstract]
1995
  1. Schölkopf, B.; and Mallot, H. A. 1995. View-based cognitive mapping and path planning. Adaptive Behavior, 3:311-348 [Abstract].
  2. Mallot, H. A.; Bülthoff, H. H.; Georg, P.; Schölkopf, B.; and Yasuhara, K. 1995. View-based cognitive map learning by an autonomous robot. In: F. Fogelman-Soulie and P. Gallinari (eds.), Proceedings ICANN'95 - International Conference on Artificial Neural Networks, Vol. II, 381-386, EC2, Nanterre, France (6 pages, 81 K). [Abstract]
  3. Schölkopf, B.; Georg, P.; and Mallot, H. A. 1995. Perception and action in view-based maze navigation. European Conference on Visual Perception, Tübingen. [Abstract] appeared in: Perception, 24:95.
  4. Mallot, H.A.; & Schölkopf, B.; 1995. Learning of cognitive maps from sequences of views. In: Verleysen, M. (ed.): ESANN'95 Proceedings. Brüssel (D facto), 277-290.
1994
  1. Schölkopf, B. 1994. View-based navigation in labyrinths. Diplomarbeit, Fakultät für Physik, Eberhard-Karls-Universität Tübingen (93 pages, 1.2 M). [Deutschsprachige Zusammenfassung]