Optimal path finding in direction, location, and time dependent environments

Irina S. Dolinskaya*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

This article examines optimal path finding problems where cost function and constraints are direction, location, and time dependent. Recent advancements in sensor and data-processing technology facilitate the collection of detailed real-time information about the environment surrounding a ground vehicle, an airplane, or a naval vessel. We present a navigation model that makes use of such information. We relax a number of assumptions from existing literature on path-finding problems and create an accurate, yet tractable, model suitable for implementation for a large class of problems. We present a dynamic programming model which integrates our earlier results for direction-dependent, time and space homogeneous environment, and consequently, improves its accuracy, efficiency, and run-time. The proposed path finding model also addresses limited information about the surrounding environment, control-feasibility of the considered paths, such as sharpest feasible turns a vehicle can make, and computational demands of a time-dependent environment. To demonstrate the applicability and performance of our path-finding algorithm, computational experiments for a short-range ship routing in dynamic wave-field problem are presented.

Original languageEnglish (US)
Pages (from-to)325-339
Number of pages15
JournalNaval Research Logistics
Volume59
Issue number5
DOIs
StatePublished - Aug 2012

Keywords

  • dynamic environment
  • dynamic programming
  • path-planning
  • vessel routing

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Optimal path finding in direction, location, and time dependent environments'. Together they form a unique fingerprint.

Cite this