Grid Discretization Based Method for Anisotropic Shortest Path Problem Over Continuous Regions

Abstract

The paper presents a method to find the shortest path between two points over a continuous region. The length of a path Is the integral of the cost along the path. The cost can be anisotropic, meaning that it depends on both the position on the path and its direction. The method uses a simple rectangular grid to discretize the region, independent of the cost. Because the cost Is anisotropic, rectlinear paths connecting adjacent grid points may not approximate the optimal path. To overcome this "limit-on-direction" problem, the method searches over shifted versions of the rectilinear paths A Bellman. Ford style algorithm finds the best shifted path. Theoretical analysis and numerical experiments ensure efficiency of the algorithm.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 2004
Accession Number
ADA424102

Entities

People

  • Pravin Varaija
  • Zhanfeng Jia

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Air Platforms
  • Weapons Technologies

DTIC Thesaurus Topics

  • Air Force
  • Air Force Research Laboratories
  • Aircrafts
  • Algorithms
  • Applied Mathematics
  • Computations
  • Computer Science
  • Electrical Engineering
  • Heuristic Methods
  • Integrals
  • Mathematics
  • Motion Planning
  • Radar
  • Sampling
  • Statistical Sampling
  • Two Dimensional
  • Unmanned Aerial Vehicles

Fields of Study

  • Computer science

Readers

  • Operations Research
  • Plasma Physics / Magnetohydrodynamics