Fastest-Path Planning for Direction-Dependent Speed Functions
- PDF / 671,411 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 11 Downloads / 195 Views
Fastest-Path Planning for Direction-Dependent Speed Functions Irina S. Dolinskaya · Robert L. Smith
Received: 27 March 2012 / Accepted: 10 December 2012 / Published online: 29 December 2012 © Springer Science+Business Media New York 2012
Abstract We discuss path planning in a direction-dependent environment illustrated by the fastest-path problem with anisotropic speed function. The difficulty of optimalpath finding in a direction-dependent medium comes from the fact that our travel-time function is asymmetric and, in general, violates the triangle inequality. We present an analytical form solution for the fastest-path finding problem in an obstacle-free domain without making any assumptions on the structure of the speed function. Subsequently, we merge these results with visibility graph search methods to develop an obstacle-avoiding fastest-path finding algorithm for an anisotropic speed function. Optimal routing of a vessel in a stationary random seaway is discussed throughout the paper to motivate and demonstrate applications of our work. Keywords Shortest path · Direction-dependent · Anisotropic medium · Obstacle-avoiding path
1 Introduction In this paper, we address a broad class of problems for finding a direction-dependent optimal path in an anisotropic environment. For ease of exposition, we focus our discussion on fastest-path finding problems for direction-dependent speed functions; however, our analysis and results can be easily extended to an arbitrary anisotropic Communicated by Gianni Di Pillo. I.S. Dolinskaya () Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208, USA e-mail: [email protected] R.L. Smith Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48109, USA
J Optim Theory Appl (2013) 158:480–497
481
cost function. We are given the points of origin and destination, and a time and space homogeneous speed which is a sole function of heading. Our objective is to find a path that minimizes the total travel time. Problems of optimal-path finding in an obstaclefree domain, as well as in the presence of polygonal obstacles, are addressed. An application in this problem class which motivated this research is optimal short-range routing of vessels in a seaway. In recent years, comprehensive seakeeping models have been developed to accurately estimate the effects of waves on vessel performance. In [1], the average added drag of head and oblique waves is evaluated in a stationary random seaway. In addition, a number of operability constraints, such as probability of wet deck and root-mean-squared roll values, are computed for various vessel headings and sea states (i.e., wave-field distributions). The integrated seakeeping model delivers the expected maximum attainable speed for a containership as a function of its heading angle relative to the dominant wave direction. The resulting anisotropic speed function has irregular structure that cannot be evaluated analytically (see Fig. 10). Our analysis m
Data Loading...
