| 1. |
- Bergman, Kristoffer, 1990-, et al.
(författare)
-
An Optimization-Based Motion Planner for Autonomous Maneuvering of Marine Vessels in Complex Environments
- 2020
-
Ingår i: 2020 59th IEEE Conference on Decision and Control (CDC). - : Institute of Electrical and Electronics Engineers (IEEE). - 9781728174471 ; , s. 5283-5290
-
Konferensbidrag (refereegranskat)abstract
- The task of maneuvering ships in confined environments is a difficult task for a human operator. One major reason is due to the complex and slow dynamics of the ship which need to be accounted for in order to successfully steer the vehicle. In this work, a two-step optimization-based motion planner is proposed for autonomous maneuvering of ships in constrained environments such as harbors. A lattice-based motion planner is used in a first step to compute a feasible, but suboptimal solution to a discretized version of the motion planning problem. This solution is then used to enable efficient warm-start and as a terminal manifold for a second recedinghorizon improvement step. Both steps of the algorithm use a high-fidelity model of the ship to plan feasible and energy-efficient trajectories. Moreover, a novel algorithm is proposed for automatic computation of spatial safety envelopes around the trajectory computed by the lattice-based planner. These safety envelopes are used in the second improvement step to obtain collision-avoidance constraints which complexity scales very well with an increased number of surrounding obstacles. The proposed optimization-based motion planner is evaluated with successful results in a simulation study for autonomous docking problems in a model of the Cape Town harbor.
|
|
| 2. |
- Bergman, Kristoffer, 1990-, et al.
(författare)
-
An Optimization-Based Receding Horizon Trajectory Planning Algorithm
- 2020
-
Ingår i: IFAC-PapersOnLine. - : ELSEVIER. - 2405-8963. ; , s. 15550-15557
-
Konferensbidrag (refereegranskat)abstract
- This paper presents an optimization-based receding horizon trajectory planning algorithm for dynamical systems operating in unstructured and cluttered environments. The proposed approach is a two-step procedure that uses a motion planning algorithm in a first step to efficiently find a feasible, but possibly suboptimal, nominal solution to the trajectory planning problem where in particular the combinatorial aspects of the problem are solved. The resulting nominal trajectory is then improved in a second optimization-based receding horizon planning step which performs local trajectory refinement over a sliding time window. In the second step, the nominal trajectory is used in a novel way to both represent a terminal manifold and obtain an upper bound on the cost-to-go online. This enables the possibility to provide theoretical guarantees in terms of recursive feasibility, objective function value, and convergence to the desired terminal state. The established theoretical guarantees and the performance of the proposed algorithm are verified in a set of challenging trajectory planning scenarios for a truck and trailer system.
|
|
| 3. |
- Bergman, Kristoffer, 1990-, et al.
(författare)
-
Improved Path Planning by Tightly Combining Lattice-Based Path Planning and Optimal Control
- 2021
-
Ingår i: IEEE Transactions on Intelligent Vehicles. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 2379-8858 .- 2379-8904. ; 6:1, s. 57-66
-
Tidskriftsartikel (refereegranskat)abstract
- This paper presents a unified optimization-based path planning approach to efficiently compute locally optimal solutions to optimal path planning problems in unstructured environments. The approach is motivated by showing that a lattice-based planner can be cast and analyzed as a bilevel optimization problem. This insight is used to integrate a lattice-based planner and an optimal control-based method in a novel way. The lattice-based planner is applied to the problem in a first step using a discretized search space. In a second step, an optimal control-based method is applied using the lattice-based solution as an initial iterate. In contrast to prior work, the system dynamics and objective function used in the first step are chosen to coincide with those used in the second step. As an important consequence, the lattice planner provides a solution which is highly suitable as a warm-start to the optimal control step. This proposed combination makes, in a structured way, benefit of sampling-based methods ability to solve combinatorial parts of the problem and optimal control-based methods ability to obtain locally optimal solutions. Compared to previous work, the proposed approach is shown in simulations to provide significant improvements in terms of computation time, numerical reliability and objective function value.
|
|
| 4. |
- Bergman, Kristoffer, 1990-, et al.
(författare)
-
Combining Homotopy Methods and Numerical Optimal Control to Solve Motion Planning Problems
- 2018
-
Ingår i: Proceedings of the 29th IEEE Intelligent Vehicles Symposium. - : IEEE. - 9781538644515 ; , s. 347-354
-
Konferensbidrag (refereegranskat)abstract
- This paper presents a systematic approach for computing local solutions to motion planning problems in non-convex environments using numerical optimal control techniques. It extends the range of use of state-of-the-art numerical optimal control tools to problem classes where these tools have previously not been applicable. Today these problems are typically solved using motion planners based on randomized or graph search. The general principle is to define a homotopy that transforms, or preferably relaxes, the original problem to an easily solved problem. In this work, it is shown that by combining a Sequential Quadratic Programming (SQP) method with a homotopy approach that gradually transforms the problem from a relaxed one to the original one, practically relevant locally optimal solutions to the motion planning problem can be computed. The approach is demonstrated in motion planning problems in challenging 2D and 3D environments, where the presented method significantly outperforms both a state-of-the-art numerical optimal control method and a state-of-the-art open-source optimizing sampling-based planner commonly used as benchmark.
|
|
| 5. |
- Bergman, Kristoffer, 1990-
(författare)
-
Exploiting Direct Optimal Control for Motion Planning in Unstructured Environments
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- During the last decades, motion planning for autonomous systems has become an important area of research. The high interest is not the least due to the development of systems such as self-driving cars, unmanned aerial vehicles and robotic manipulators. The objective in optimal motion planning problems is to find feasible motion plans that also optimize a performance measure. From a control perspective, the problem is an instance of an optimal control problem. This thesis addresses optimal motion planning problems for complex dynamical systems that operate in unstructured environments, where no prior reference such as road-lane information is available. Some example scenarios are autonomous docking of vessels in harbors and autonomous parking of self-driving tractor-trailer vehicles at loading sites. The focus is to develop optimal motion planning algorithms that can reliably be applied to these types of problems. This is achieved by combining recent ideas from automatic control, numerical optimization and robotics.The first contribution is a systematic approach for computing local solutions to motion planning problems in challenging unstructured environments. The solutions are computed by combining homotopy methods and direct optimal control techniques. The general principle is to define a homotopy that transforms, or preferably relaxes, the original problem to an easily solved problem. The approach is demonstrated in motion planning problems in 2D and 3D environments, where the presented method outperforms a state-of-the-art asymptotically optimal motion planner based on random sampling.The second contribution is an optimization-based framework for automatic generation of motion primitives for lattice-based motion planners. Given a family of systems, the user only needs to specify which principle types of motions that are relevant for the considered system family. Based on the selected principle motions and a selected system instance, the framework computes a library of motion primitives by simultaneously optimizing the motions and the terminal states.The final contribution of this thesis is a motion planning framework that combines the strengths of sampling-based planners with direct optimal control in a novel way. The sampling-based planner is applied to the problem in a first step using a discretized search space, where the system dynamics and objective function are chosen to coincide with those used in a second step based on optimal control. This combination ensures that the sampling-based motion planner provides a feasible motion plan which is highly suitable as warm-start to the optimal control step. Furthermore, the second step is modified such that it also can be applied in a receding-horizon fashion, where the proposed combination of methods is used to provide theoretical guarantees in terms of recursive feasibility, worst-case objective function value and convergence to the terminal state. The proposed motion planning framework is successfully applied to several problems in challenging unstructured environments for tractor-trailer vehicles. The framework is also applied and tailored for maritime navigation for vessels in archipelagos and harbors, where it is able to compute energy-efficient trajectories which complies with the international regulations for preventing collisions at sea.
|
|
| 6. |
- Bergman, Kristoffer, 1990-
(författare)
-
On Motion Planning Using Numerical Optimal Control
- 2019
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- During the last decades, motion planning for autonomous systems has become an important area of research. The high interest is not the least due to the development of systems such as self-driving cars, unmanned aerial vehicles and robotic manipulators. In this thesis, the objective is not only to find feasible solutions to a motion planning problem, but solutions that also optimize some kind of performance measure. From a control perspective, the resulting problem is an instance of an optimal control problem. In this thesis, the focus is to further develop optimal control algorithms such that they be can used to obtain improved solutions to motion planning problems. This is achieved by combining ideas from automatic control, numerical optimization and robotics.First, a systematic approach for computing local solutions to motion planning problems in challenging environments is presented. The solutions are computed by combining homotopy methods and numerical optimal control techniques. The general principle is to define a homotopy that transforms, or preferably relaxes, the original problem to an easily solved problem. The approach is demonstrated in motion planning problems in 2D and 3D environments, where the presented method outperforms both a state-of-the-art numerical optimal control method based on standard initialization strategies and a state-of-the-art optimizing sampling-based planner based on random sampling.Second, a framework for automatically generating motion primitives for lattice-based motion planners is proposed. Given a family of systems, the user only needs to specify which principle types of motions that are relevant for the considered system family. Based on the selected principle motions and a selected system instance, the algorithm not only automatically optimizes the motions connecting pre-defined boundary conditions, but also simultaneously optimizes the terminal state constraints as well. In addition to handling static a priori known system parameters such as platform dimensions, the framework also allows for fast automatic re-optimization of motion primitives if the system parameters change while the system is in use. Furthermore, the proposed framework is extended to also allow for an optimization of discretization parameters, that are are used by the lattice-based motion planner to define a state-space discretization. This enables an optimized selection of these parameters for a specific system instance.Finally, a unified optimization-based path planning approach to efficiently compute locally optimal solutions to advanced path planning problems is presented. The main idea is to combine the strengths of sampling-based path planners and numerical optimal control. The lattice-based path planner is applied to the problem in a first step using a discretized search space, where system dynamics and objective function are chosen to coincide with those used in a second numerical optimal control step. This novel tight combination of a sampling-based path planner and numerical optimal control makes, in a structured way, benefit of the former method’s ability to solve combinatorial parts of the problem and the latter method’s ability to obtain locally optimal solutions not constrained to a discretized search space. The proposed approach is shown in several practically relevant path planning problems to provide improvements in terms of computation time, numerical reliability, and objective function value.
|
|
| 7. |
- Hellander, Anja, 1996-, et al.
(författare)
-
On Integrated Optimal Task and Motion Planning for a Tractor-Trailer Rearrangement Problem
- 2024
-
Ingår i: 2023 62nd IEEE Conference on Decision and Control (CDC). - : IEEE. - 9798350301243 ; , s. 6116-6123
-
Konferensbidrag (refereegranskat)abstract
- In this work, a combined task and motion planner for a tractor and a set of trailers is proposed and it is shown that it is resolution complete and resolution optimal. The proposed planner consists of a task planner and a motion planner that are both based on heuristically guided graph-search. As a step towards tighter integration of task and motion planning, we use the same heuristic that is used by the motion planner in the task planner as well. We further propose to use the motion planner heuristic to give an initial underestimate of the motion costs that are used as costs during the task planning search, and increase this estimate gradually by using the motion planner to verify the cost and feasibility of actions along paths of interest. To limit the time spent in the motion planner, the use of time and cost limits to pause or prematurely abort the motion planner is proposed, which does not affect the resolution completeness or resolution optimality. The planner is evaluated on numerical examples and the results show that the proposed planner can significantly reduce the execution time compared to a baseline resolution optimal task and motion planner.
|
|
| 8. |
- Hellander, Anja, 1996-
(författare)
-
On Optimal Integrated Task and Motion Planning with Applications to Tractor-Trailers
- 2023
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- An important aspect in autonomous systems is the ability of a system to plan before acting. This includes both high-level task planning to determine what sequence of actions to take in order for the system to reach a goal state, as well as low-level motion planning to detail how to perform the actions required.While it is sometimes possible to plan hierarchically, i.e., to first compute a task plan and then compute motion plans for each action in the task plan, there are also many problem instances where this approach fails to find a feasible plan as not all task plans lead to motion-planning problems that have feasible solutions. For this reason, it is desirable to solve the two problems jointly rather than sequentially. Additionally, it is often desirable to find plans that optimize a performance measure, such as the energy used, the length of the path travelled by the system or the time required. This thesis focuses on the problem of finding joint task and motion plans that optimize a performance measure.The first contribution is a method for solving a joint task and motion planning problem, that can be formulated as a traveling salesman problem with dynamic obstacles and motion constraints, to resolution optimality. The proposed method uses a planner comprising two nested graph-search planners. Several different heuristics are considered and evaluated.The second contribution is a method for solving a joint task and motion planning problem, in the form of a rearrangement problem for a tractor-trailer system, to resolution optimality. The proposed method combines a task planner with motion planners, all based on heuristically guided graph search, and uses branch-and-bound techniques in order to improve the efficiency of the search algorithm.The final contribution is a method for improving task and motion plans for rearrangement problems using optimal control. The proposed method takes inspiration from finite-horizon optimal control and decomposes the optimization problem into several smaller optimization problems rather than solving one larger optimization problem. Compared to solving the original larger optimization problem, it is demonstrated that this can lead to reduced computation time without any significant decrease in solution quality.
|
|
