An official website of the United States government
A bounded cost path planning method is developed for underwater vehicles assisted by a data-driven flow modeling method. The modeled flow field is partitioned as a set of cells of piece-wise constant flow speed. A flow partition algorithm and a parameter estimation algorithm are proposed to learn the flow field structure and parameters with justified convergence. A bounded cost path planning algorithm is developed taking advantage of the partitioned flow model. An extended potential search method is proposed to determine the sequence of partitions that the optimal path crosses. The optimal path within each partition is then determined by solving a constrained optimization problem. Theoretical justification is provided for the proposed extended potential search method generating the optimal solution. The path planned has the highest probability to satisfy the bounded cost constraint. The performance of the algorithms is demonstrated with experimental and simulation results, which show that the proposed method is more computationally efficient than some of the existing methods.
more »
« less
Method of evolving junction on optimal path planning in flows fields
We propose an algorithm using method of evolving junctions to solve the optimal path planning problems with piece-wise constant flow fields. In such flow fields, we prove that the optimal trajectories, with respect to a convex Lagrangian in the objective function, must be formed by piece-wise constant velocity motions. Taking advantage of this property, we transform the infinite dimensional optimal control problem into a finite dimensional optimization and use intermittent diffusion to solve the problems. The algorithm is proven to be complete. At last, we demonstrate the performance of the algorithm with various simulation examples.
more »
« less
- PAR ID:
- 10359103
- Date Published:
- Journal Name:
- Autonomous Robots
- ISSN:
- 0929-5593
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Soner, Mete (Ed.)We develop a backward-in-time machine learning algorithm that uses a sequence of neural networks to solve optimal switching problems in energy production, where electricity and fossil fuel prices are subject to stochastic jumps. We then apply this algorithm to a variety of energy scheduling problems, including novel high-dimensional energy production problems. Our experimental results demonstrate that the algorithm performs with accuracy and experiences linear to sub-linear slowdowns as dimension increases, demonstrating the value of the algorithm for solving high-dimensional switching problem. Keywords. Deep neural networks, forward-backward systems of stochastic differential equations, optimal switching, Monte Carlo algorithm, optimal investment in power generation, planning problemsmore » « less
-
null (Ed.)We consider a general class of finite-horizon online decision-making problems, where in each period a controller is presented a stochastic arrival and must choose an action from a set of permissible actions, and the final objective depends only on the aggregate type-action counts. Such a framework encapsulates many online stochastic variants of common optimization problems including bin packing, generalized assignment, and network revenue management. In such settings, we study a natural model-predictive control algorithm that in each period, acts greedily based on an updated certainty-equivalent optimization problem. We introduce a simple, yet general, condition under which this algorithm obtains uniform additive loss (independent of the horizon) compared to an optimal solution with full knowledge of arrivals. Our condition is fulfilled by the above-mentioned problems, as well as more general settings involving piece-wise linear objectives and offline index policies, including an airline overbooking problem.more » « less
-
Alternative current optimal power flow (ACOPF) problems have been studied for over fifty years, and yet the development of an optimal algorithm to solve them remains a hot and challenging topic for researchers because of their nonlinear and nonconvex nature. A number of methods based on linearization and convexification have been proposed to solve ACOPF problems, which result in near-optimal or local solutions, not optimal solutions. Nowadays, with the prevalence of machine learning, some researchers have begun to utilize this technology to solve ACOPF problems using the historical data generated by the grid operators. The present paper reviews the research on solving ACOPF problems using machine learning and neural networks and proposes future studies. This body of research is at the beginning of this area, and further exploration can be undertaken into the possibilities of solving ACOPF problems using machine learning.more » « less
-
Reductions combine collections of input values with an associative and often commutative operator to produce collections of results. When the same input value contributes to multiple outputs, there is an opportunity to reuse partial results, enabling reduction simplification. Simplification often produces a program with lower asymptotic complexity. Typical compiler optimizations yield, at best, a constant fold speedup, but a complexity improvement from, say, cubic to quadratic complexity yields unbounded speedup for sufficiently large problems. It is well known that reductions in polyhedral programs may be simplified automatically, but previous methods cannot exploit all available reuse. This paper resolves this long-standing open problem, thereby attaining minimal asymptotic complexity in the simplified program. We propose extensions to prior work on simplification to support any independent commutative reduction. At the heart of our approach is piece-wise simplification, the notion that we can split an arbitrary reduction into pieces and then independently simplify each piece. However, the difficulty of using such piece-wise transformations is that they typically involve an infinite number of choices. We give constructive proofs to deal with this and select a finite number of pieces for simplification.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s10514-022-10058-5
