Back to search

Georgia Institute of Technology

Navigation among movable obstacles in unknown environments

Abstract

dc:description.abstract

This work presents a new class of algorithms that extend the domain of Navigation Among Movable Obstacles (NAMO) to unknown environments. Efficient real-time algorithms for solving NAMO problems even when no initial environment information is available to the robot are presented and validated. The algorithms yield optimal solutions and are evaluated for real-time performance on a series of simulated domains with more than 70 obstacles. In contrast to previous NAMO algorithms that required a pre-specified environment model, this work considers the realistic domain where the robot is limited by its sensor range. It must navigate to a goal position in an environment of static and movable objects. The robot can move objects if the goal cannot be reached or if moving the object significantly shortens the path. The robot gains information about the world by bringing distant objects into its sensor range. The first practical planner for this exponentially complex domain is presented. The planner reduces the search-space through a collection of techniques, such as upper bound calculations and the maintenance of sorted lists with underestimates. Further, the algorithm is only considering manipulation actions if these actions are creating a new opening in the environment. In the addition to the evaluation of the planner itself is each of this techniques also validated independently.

Degree

thesis:*
Department dc:contributor.department
Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Levihn, Martin
Advisor dc:contributor.advisor
  • Stilman, Mike
Committee members dc:contributor.committeemember
  • Mynatt, Elizabeth D.
  • Bell, Genevieve
  • Foley, James
  • Forlizzi, Jodi

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/39559

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Levihn, Martin. Navigation among movable obstacles in unknown environments. Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/39559