Planning Monotone Paths to Visit a Set of Obstacles

Abstract

Computing a shortest collision-free path connecting points s and t that visits a given set of obstacles in two dimensions is like the travelling salesman problem and is NP-hard. We consider a restricted version of the above problem called the s-t-monotone visit problem that asks for a monotone path connecting s and t that visits the maximum number of obstacles. We give an O(n squared) time algorithm to solve this problem, where n is the size of the obstacle scene.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1990
Accession Number
ADA226923

Entities

People

  • Laxmi P. Gewali

Organizations

  • University of Nevada, Las Vegas

Tags

Communities of Interest

  • Autonomy
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Collisions
  • Computations
  • Computer Science
  • Geometry
  • Information Processing
  • Mathematics
  • Military Research
  • Motion Planning
  • New Jersey
  • Polygons
  • Robotics
  • Robots
  • Security
  • Two Dimensional

Fields of Study

  • Computer science
  • Mathematics

Readers

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