Research

In this paper we consider the optimization of a functional F defined as the convolution of a function f with a Gaussian kernel. This type of objective function is of interest in the optimization of the expensive output of complex computational simulations, which often present some form of deterministic noise and need to be smoothed for the results to be meaningful. We introduce a derivative-free algorithm that computes trial points from the minimization of a regression model of the expensive function f over a trust region. The regression model is constructed from function values at sample points that are chosen randomly around iterates and trial points of the algorithm. The weights given to the individual sample points in the regression problem are obtained according to an adaptive multiple importance sampling strategy. This has two advantages. First, it makes it possible to re-use all expensive function values collected over the course of the optimization. Second, the resulting regression model converges to the second-order Taylor approximation of the convolution functional F. We prove that, with probability 1, each limit point of the iterates is a stationary point of F. Computational experiments on a set of benchmark problems with noisy functions compare the proposed algorithm with a regular derivative-free trust-region method. It is demonstrated that the proposed algorithm performs similarly efficient in the early stages of the optimization and is able to overcome convergence problems of the regular method, which might get trapped in spurious local minima induced by the noise.

We study sample average approximations under adaptive importance sampling. Based on a Banach-space-valued martingale strong law of large numbers, we establish uniform convergence of the sample average approximation to the function being approximated. In the optimization context, we obtain convergence of the optimal value and optimal solutions of the sample average approximation.

This paper characterizes time-optimal trajectories in anisotropic (direction-dependent) environments where path curvatures are bounded by the inverse of the minimum-turning radius of a mobile agent. Such problems are often faced in the navigation of aerial, ground and naval vehicles when a mobile agent cannot instantaneously change its heading angle. The work presented is a generalization of the Dubins car problem, which considers the fastest paths with bounded curvature while assuming constant speed and minimum-turning radius. We relax this assumption and discuss fastest-path finding problems for the generalized direction-dependent speed and minimum-turning radius functions, to account for the effects of waves, winds and slope of the terrain on the agent’s motions. We establish that there exists an optimal path such that it is a portion of a path of the type where denotes a sharpest-turn curve and a straight-line segment. We further analyze a special case wherein the speed polar plot is convex, and show that in that case there exists an optimal path with the same structure as for the Dubins problem: or . An algorithm that implements our results for the convex speed polar plot is also presented.

This paper presents an algorithm that constructs a fastest curvature-constrained path in a direction-dependent environment for given initial and target locations and heading angles. The problem studied here is a generalization of the classical Dubins car problem, where the vehicle speed and minimum turning radius are assumed to be constant. This assumption is relaxed and the settings where the two parameters are arbitrary functions of the agent’s heading angle are considered, such as a maneuvering sailboat for example. This paper is concerned with the extension and implementation of the authors’ earlier results that establish the fastest path between two positions in the plane for a Dubins-like vehicle in a (possibly) anisotropic medium to be of the form (or any subset of this word) where denotes a sharpest-turn curve and denotes a straight line segment. While the authors’ preceding work has derived the structure of a fastest path, the actual implementation of the results presents a significant challenge and remained unsolved. The main contribution of this paper is an algorithm that implements those results and illustrates several specific instances in which the results developed here can be applied. This work is particularly relevant for vehicles whose interaction with their surrounding environment creates direction-dependent dynamics, such as aerial or surface vehicles in wind or strong currents.

Considerable research has been done on the vehicle routing problem and its variants; however only limited amount of existing work deals with possible environmental conditions and their effects on the vehicle routes. This paper presents the multiple-depot vehicle routing problem for surface vessels, where the vehicles must traverse a time-invariant direction-dependent medium. Our model captures environ-mental effects and vessel dynamics on the considered paths. Three heuristic solution methods are developed and tested on simulated scenarios. The first approach exactly solves an approximate formulation of the problem, the second approximately solves an approximate problem formulation, while the third approximately solves the exact problem. Performance of the algorithms are compared to assess the tradeoff between computational cost and quality of the found solutions.