Discrete Warehouse Problem

Abstract

A discrete warehouse is a collection of objects (robot and obstacles) which are allowed to move along the grid edges of a two-dimensional grid. In this paper, we consider motion planning problems of a unit-square robot moving on a square grid among unit-square obstacles, which are movable. In such a setup one is allowed to move some of the obstacles in order to navigate the robot between an initial and a final position of the robot in the warehouse. The final positions of the obstacles are unimportant for our problems. We consider two forms of obstacle manipulations: (a) Remote, when the obstacles are moved by a remote mechanism, and (b) Contact, when the obstacles are moved only by direct contact of the robot. We present necessary and sufficient conditions for the existence of a motion in both cases, and propose efficient algorithms for constructing feasible motions. Thus, we establish the first known class of tractable motion planning problems with multiple movable obstacles.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1988
Accession Number
ADA205336

Entities

People

  • Majid Sarrafzadeh
  • Sanjeev R. Maddila

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Classification
  • Clearances
  • Computer Science
  • Construction
  • Engineering
  • Environment
  • Geometry
  • Illinois
  • Motion Planning
  • Notation
  • Robotics
  • Security
  • Sequences
  • Two Dimensional
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.
  • Robotics and Automation.

Technology Areas

  • AI & ML
  • AI & ML - Autonomous Systems
  • AI & ML - Machine Learning Algorithms
  • Autonomy