GODZILA: A low-resource algorithm for path planning in unknown environments

P. Krishnamurthy, F. Khorrami

Research output: Contribution to journalArticle

Abstract

We propose a novel sensor-based path-planning and obstacle avoidance algorithm GODZILA for navigation in unknown environments. No prior knowledge of the environment is required. The path-planning algorithm follows a purely local approach using only the current range sensor measurements at each sampling instant and requiring only a small number of stored variables in memory. No map of the environment is built during navigation. This minimizes the memory and computational requirements for implementation of the algorithm, a feature that is especially attractive for small autonomous vehicles. The algorithm utilizes three components: an optimization algorithm, a local straight-line path planner to visible targets, and random navigation. It is proved, for navigation in any finite-dimensional space, that the path-planning algorithm converges in finite time with probability 1. The performance of the algorithm is demonstrated through simulations for path-planning in two-dimensional (2D) and three-dimensional (3D) spaces. It is seen that a relatively small number of range sensor measurements is sufficient even in complex unknown environments.

Original languageEnglish (US)
Pages (from-to)357-373
Number of pages17
JournalJournal of Intelligent and Robotic Systems: Theory and Applications
Volume48
Issue number3
DOIs
StatePublished - Mar 2007

Keywords

  • Autonomous vehicles
  • Low-resource
  • Obstacle avoidance
  • Path planning
  • Unknown environments

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Mechanical Engineering
  • Industrial and Manufacturing Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'GODZILA: A low-resource algorithm for path planning in unknown environments'. Together they form a unique fingerprint.

  • Cite this