---
title: "Map Validation and Self-location in a Graph-like World"
authors:
  - "Gregory Dudek"
  - "Michael R. M. Jenkin"
  - "Evangelos E. Milios"
  - "David Wilkes"
doi: ""
url: "https://ijcai.org/proceedings/1993/228"
pdf: "https://ijcai.org/proceedings/1993/0228.pdf"
venue: "Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence"
year: 1993
pages: "1648-1652"
track: "Robotics and Vision"
keywords:
---

# Map Validation and Self-location in a Graph-like World

Gregory Dudek, Michael R. M. Jenkin, Evangelos E. Milios, David Wilkes

*Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence*, pages 1648-1652.

## Abstract

We present algorithms for the discovery and use of topological maps of an environment by an active agent (such as a person or a mobile robot). We discuss several issues dealing with the use of pre-existing topological maps of graph-like worlds by an autonomous robot and present algorithms, worst cases complexity, and experimental results (for representative real-world examples} for two key problems. The first of these problems is to verify that a given input map is a correct description of the world (the VALIDATION PROBLEM} . The second is to determine the robot's physical position on an input map (THE SELF-LOCATION PROBLEM)' We present algorithms which require O(N ) and O(N 3 ) steps to validate and locate the robot in a map (where N is the number of places in the map).