Mapping, exploration, and navigation strategies for a mobile robot operating in an unknown environment

  • Amna Al Shamsi

Student thesis: Doctoral Thesis


Replacing humans with robots, or at least assisting them, in time critical hazardous missions,such as in search and rescue operations, is a necessity given the risks and dangershuman forces might be exposed to. In this research we present new mapping, exploration,and navigation strategies to reduce the exploration time while simultaneouslyincreasing the robot’s knowledge about its surroundings. A robot’s ability to successfullycomplete a required task, such as searching or exploration, is bound by its knowledge aboutthe operational environment. Thus, the robot must be able to collect information from itssurroundings and map it accurately to create a correct representation of the environmentand use it as a return path later. An increasing number of applications, such as surveillanceand search and rescue, impose time constraints on the mapping and explorationprocess.The proposed Triangulation-Based exploration maps the environment incrementallyusing our Incremental Triangulation Algorithm to accelerate the exploration process.This method maps the environment geometrically and captures its connectivityand represents it internally in a compact format. The captured connectivity allows thegeneration of paths during the exploration process despite the incompleteness of the environmentmap. A return path can be maintained as a critical safe path that can be usedin applications and missions that implicitly requires maintaining a safe return back.To achieve those objectives this work introduces the Dynamic Triangulation Tree,DTT, which is a tree-like structure built incrementally during the Incremental Triangulationmapping. The DTT compactly represents the geometry of the environment whichis utilized for minimizing the overall exploration time. Our solution drives the explorationprocess towards areas that will provide the robot with greater exposure to its surroundingsby considering not only the distances to the frontiers but also the currently knownsurroundings of the environment. The DTT was also employed in the navigation phaseto generate feasible paths for the robot to traverse when progressing from one frontier to the other during the exploration process.All three modules of this work have been designed to suit low cost robotic systemssince it requires minimal memory and computation requirements. The effectiveness andefficiency of all the proposed algorithms are validated in simulations using various scenariosand comparisons to demonstrate their main advantages over their counterparts found inthe literature. For further future validation efforts two directions have been studied, the3D simulation environment USARSIM and the real-time physical application DroneAid.
Date of Award2015
Original languageAmerican English
SupervisorSeneviratne Seneviratne (Supervisor)


  • Mapping
  • exploration
  • and navigationstrategies for a mobile robot operating inan unknown environment

Cite this