An exact algorithm for kinodynamic planning in the plane

Planning time-optimal motions has been a major focus of research in robotics. In this paper we consider the following problem: given an object in two-dimensional physical space, an initial point, and a final point, plan a time-optimal obstacle-avoiding motion for this object subject to bounds on the velocity and acceleration of the object. We give the first algorithm which solves the problem exactly in the case where the velocity and acceleration bounds are given in theL _∞ norm. We further prove the following important results: a tracking lemma and a loop-elimination theorem, both of which are applicable to the case of arbitrary norms. The latter result implies that, with or without obstacles, a path which intersects itself can be replaced by one which does not do so and which takes time less than or equal to that taken by the original path. The work of J. Canny and A. Rege was supported by NSF Grants IRI-89-58577 and IRI-90-14490 and by a David and Lucile Packard Fellowship. J. Reif's work was supported in part by DARPA/ARO Contract DAAL03-88-K-0185, Air Force Contract AFSOR-87-0386, ONR Contract N00014-K-0310, and DARPA/ISTO Contract N00014-88-K-0458.     

Packet routing and job-shop scheduling inO(congestion+dilation) steps

In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, inO(c+d) steps, wherec is the congestion of the paths in the network, andd is the length of the longest path. The result has applications to packet routing in parallel machines, network emulations, and job-shop scheduling.This research was conducted while the authors were at MIT. Support was provided by the Defense Advanced Research Projects Agency under Contract N00014-87-K-825, the Office of Naval Research under Contract N00014-86-K-0593, the Air Force under Contract OSR-86-0076, and the Army under Contract DAAL-03-86-K-0171. Tom Leighton is supported by an NSF Presidential Young Investigator Award with matching funds provided by IBM.     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

A General framework for local interpolation

Summary We present a general framework for the construction of local interpolation methods with a given approximation order. Some applications to multivariate spline spaces are presented.Supported by the National Science Foundation, Contract Nos. DMS-8602337 and DMS-8701190Sponsored by Defense Advanced Research Projects Agency (DARPA), under contract No. MDA 972-88-C-0047 for DARPA Initiative in Concurrent Engineering (DICE)     

Asymptotic expansions for Markov processes with lévy generators

This paper considers a deterministic flow inn-dimensional space, perturbed by a Markov jump process with small variance. Asymptotic expansions are obtained for certain functionals of Feynman—Kac type, in powers of a small parameter representing a noise intensity. The methods are analytical rather than probabilistic.The research of the first author was partly supported by AFOSR under Contract No. 91-0116-0, by ONR under Contract No. N0014-83-K-0542, and by the Institute for Mathematics and Its Applications with funds provided by the NSF and ONR. The second author's research was partly supported by NSF under Contract No. DMS-8702537, and by the Institute for Mathematics and Its Applications with funds provided by the NSF and ONR.     

Two approaches to optimal routing and admission control in systems with real-time traffic

This paper addresses the problem of routing and admission control of real-time traffic in a queueing system where customers must begin service within given deadlines (or complete service within given deadlines), otherwise they are considered lost. Performance in such systems is measured by the probability a customer is lost. For a system ofK parallel servers with a probabilistic routing and admission control scheme, the problem of the optimal routing and admission control is considered and two approaches are presented. Assuming the availability of a closed-form expression for the probability of loss at each server, the problem is solved under general conditions and properties of the optimal flow allocation are given. However, such closed-form expressions are often unavailable. This motivates a second approach, which involves a gradient-based stochastic optimization algorithm with on-line gradient estimation. The gradient estimation problem for loss probabilities is solved through a recently-developed smoothed perturbation analysis (SPA) technique. The effectiveness of on-line stochastic optimization using this type of gradient estimator is demonstrated by combining the SPA algorithm with a sampling-controlled stochastic optimization algorithm for the aforementioned routing and admission control problem.This work was supported in part by the Office of Naval Research under Contract N00014-87-K-0304, by the Rome Air Development Center under Contract F30602-88-D-0027, by NASA under Contract NAG 2-595, and by the National Science Foundation under Grant EID-92-12122.The authors are grateful to Don Towsley for several contributions to Section 2 and to an anonymous reviewer for pointing out a redundant assumption in the proof of Lemma 2.1.     

A generalization of Dirac’s theorem for K(1,3)-free graphs

It is known that if a 2-connected graphG of sufficiently large ordern satisfies the property that the union of the neighborhoods of each pair of vertices has cardinality at leastn/2, thenG is hamiltonian. In this paper, we obtain a similar generalization of Dirac’s Theorem forK(1,3)-free graphs. In particular, we show that ifG is a 2-connectedK(1,3)-free graph of ordern with the cardinality of the union of the neighborhoods of each pair of vertices at least (n+1)/3, thenG is hamiltonian. We also investigate several other related properties inK(1,3)-free graphs such as traceability, hamiltonian-connectedness, and pancyclicity. Partially Supported by O. N. R. Contract Number N00014-88-K-0070. Partially Supported by O. N. R. Contract Number N00014-85-K-0694.     

Edge-clique graphs

The edge-clique graphK(G) of a graphG is that graph whose vertices correspond to the edges ofG and where two vertices ofK(G) are adjacent whenever the corresponding edges ofG belong to a common clique. It is shown that every edge-clique graph is a clique graph, and that ifG is either an interval graph or a line graph, then so too isK(G). An algorithm is provided for determining whether a graph is an edge-clique graph. A new graph called the STP graph is introduced and a relationship involving this graph, the edge-clique graph, and the line graph is presented. The STP graphs are also characterized.Research supported in part by Office of Naval Research Contract N00014-88-K-0018.Research supported in part by Office of Naval Research Contract N00014-88-K-0163.     

Consistency of infinitesimal perturbation analysis estimators with rates

We study a class of infinitesimal perturbation analysis (IPA) algorithms for queueing systems with load-dependent service and/or arrival rates. Such IPA algorithms were originally motivated by applications to large queueing systems in conjunction with aggregation algorithms. We prove strong consistency of these estimators through a type of birth and death queue. This work was supported in part by the NSF under Grants Nos. ECS85-15449 and CDR-8803012, by ONR under Contracts Nos. N00014-89-J-0075 and N00014-90-K-1093, and by the US Army under Contract No. DAAL-03-83-K-0171. This paper was written while the author was with the Division of Applied Sciences at Harvard University.     

Optimal rigid body motions,part 2: Minimum time solutions

The time-optimal control of rigid-body angular rates is investigated in the absence of direct control over one of the angular velocity components. The existence of singular subarcs in the time-optimal trajectories is explored. A numerical survey of the optimality conditions reveals that, over a large range of boundary conditions, there are in general several distinct extremal solutions. A classification of extremal solutions is presented, and domains of existence of the extremal subfamilies are established in a reduced parameter space. A locus of Darboux points is obtained, and global optimality of the extremal solutions is observed in relation to the Darboux points. The continuous dependence of the optimal trajectories with respect to variations in control constraints is noted, and a procedure to obtain the time-optimal bang-bang solutions is presented.This work was supported in part by DARPA under Contract No. ACMP-F49620-87-C-0016, by SDIO/IST under Contract No. F49620-87-C0088, and by Air Force Grant AFOSR-89-0001.     

Effect of model uncertainty on some optimal routing problems

We study the effect of model uncertainties on optimal routing in a system of parallel queues. The uncertainty arises in modeling the service time distribution for the customers (jobs, packets) to be served. For a Poisson arrival process and Bernoulli routing, the optimal mean system delay generally depends on the variance of this distribution. However, as the input traffic load approaches the system capacity, the optimal routing assignment and corresponding mean system delay are shown to converge to a variance-invariant point. The implications of these results are examined in the context of gradient-based routing algorithms. An example of a model-independent algorithm using on-line gradient estimation is also included and its performance compared with that of model-based algorithms.This work was supported in part by the National Science Foundation under Grant ECS-88-01912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595.     

On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method

Interest in linear programming has been intensified recently by Karmarkar’s publication in 1984 of an algorithm that is claimed to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming, the transformed problem can be solved by a “projected Newton barrier” method. This method is shown to be equivalent to Karmarkar’s projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications for future developments in linear programming are discussed. The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AA03-76SF00326, PA No. DE-AS03-76ER72018; National Science Foundation Grants DCR-8413211 and ECS-8312142; the Office of Naval Research Contract N00014-85-K-0343; and the U.S. Army Research Office Contract DAAG29-84-K-0156. The research of J.A. Tomlin was supported by Ketron, Inc. and the Office of Naval Research Contract N00014-85-C-0338.     

Linear complexity algorithms for semiseparable matrices

Linear complexity algorithms are derived for the solution of a linear system of equations with the coefficient matrix represented as a sum of diagonal and semiseparable matrices. LDU-factorization algorithms for such matrices and their inverses are also given. The case in which the solution can be efficiently update is treated separately.This work was supported in part by the U.S. Army Research Office, under Contract DAAG29-83-K-0028, and the Air Force Office of Scientific Research, Air Force Systems Command under Contract AF83-0228.     

Simulation methods for queues: An overview

This paper gives an overview of those aspects of simulation methodology that are (to some extent) peculiar to the simulation of queueing systems. A generalized semi-Markov process framework for describing queueing systems is used through much of the paper. The main topics covered are: output analysis for simulation of transient and steady-state quantities, variance reduction methods that exploit queueing structure, and gradient estimation methods for performance parameters associated with queueing networks.The research of this author was supported by the U.S. Army Research Office under Contract DAAG29-84-K-0030.The research of this author was supported by the U.S. Army Research Office under Contract DAAG29-84-K-0030 and National Science Foundation Grant DCR-85-09668.     

On stable laws for estimating functions and derived estimators

Summary Stable laws forM-estimators, maximum likelihood and other estimators and obtained through parallel results for the estimating functions and relative compactness of some related estimating functional processes. Work supported by the Office of Naval Research, Contract No. N00014-83-K-0387.     

Homoclinic and heteroclinic orbits for a class of Hamiltonian systems

The existence of a rich structure of homoclinic and heteroclinic solutions is established for a family of Hamiltonian systems that serve as a simpler model for the multiple pendulum system. The proof is based on recently developed arguments from the calculus of variations that have proved useful in finding actual solutions of an equation near approximate solution.This research was sponsorted in part by the National Science Foundation under grant #MCS-8110556 and the U. S. Army Research Office under Contract #DAAL03-87-K-0043. Any reproduction for the purpose of the United States Government is permitted.     

SomeL 1 existence and dependence results for semilinear elliptic equations under nonlinear boundary conditions

In this paper we study questions of existence, uniqueness, and continuous dependence for semilinear elliptic equations with nonlinear boundary conditions. In particular, we obtain results concerning the continuous dependence of the solutions on the nonlinearities in the problem, which in turn implies analogous results for a related parabolic problem. Such questions arise naturally in the study of potential theory, flow through porous media, and obstacle problems.Sponsored by the United States Army under Contract Nos. DAAG29-80-C-0041 and DAAL03-87-K-0043, and by the Air Force Office of Scientific Research under Contract No. AFOSR 84-0252 and by the National Science Foundation under Grant No. DMS-8505531. Research of the third author was carried out in part while visiting the Institute for Mathematics and Its Applications at the University of Minnesota.     

Nonlocal regularization of L. C. Young's tacking problem

L. C. Young's tacking problem is a prototype of a nonconvex variational problem for which minimizing sequences for the energy do not attain a minimum. The minimizer of the energy is usually described as a Young-measure or generalized curve. In many studies, the tacking problem is regularized by adding a higher-order viscosity term to the energy. This regularized energy has classical minimizers. In this paper we regularize instead with a spatially nonlocal term. This weakly regularized problem still has measure-valued minimizers, but as the nonlocal term becomes stronger, the measure-valued solutions organize, coalesce, and eventually turn into classical solutions. The information on the measure-valued solutions is obtained by studying equivalent variational problems involving moments of the measures.The research of D. Brandon has been partially supported by the Office of Naval Research under Grant Number N00014-88-K-0417 and by DARPA Grant F4920-87-C-0116, and that of R. C. Rogers has been partially supported by the Office of Naval Research under Grant Number N00014-88-K-0417 and by the National Science Foundation under Grant Number DMS-8801412.     

The optimal control of diffusions

Using a differentiation result of Blagovescenskii and Freidlin calculations of Bensoussan are simplified and the adjoint process identified in a stochastic control problem in which the control enters both the drift and diffusion coefficients. A martingale representation result of Elliott and Kohlmann is then used to obtain the integrand in a stochastic integral, and explicit forward and backward equations satisfied by the adjoint process are derived.This research was partially supported by NSERC under Grant A7964, the U.S. Air Force Office of Scientific Research under Contract AFOSR-86-0332, and the U.S. Army Research Office under Contract DAAL03-87-K-0102.     

Fully discrete approximation methods for the estimation of parabolic systems and boundary parameters

A spatially and temporally discrete numerical approximation scheme is developed for the identification of a class of semilinear parabolic systems with unknown boundary parameters. The identification problem is formulated as a least squares fit to data subject to an equivalent representation for the dynamics in the form of an abstract evolution equation. Finite-dimensional difference equation state approximations are constructed using a cubic spline-based, Galerkin method and the Padé rational function approximations to the exponential. A sequence of approximating identification problems result, the solutions of which are shown to exist and, in a certain sense, approximate solutions to the original identification problem. Numerical results for two examples, one involving the modeling of biological mixing in deep sea sediment cores, and the other, the estimation of transport parameters for indoor mixing, are discussed. In both examples, the identification is based upon actual experimental data.Parts of the research were carried out while the authors were visitors at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, Virginia, which is operated under NASA Contracts No. NAS1-17070 and No. NAS1-17130.Research supported in part by NSF Grant MCS-8205355, AFOSR Contract 81-0198 and ARO Contract ARO-DAAG-29-K-0029.