We consider the problem of coordinating a collection of robots at an intersection area taking into account dynamical constraints due to actuator limitations. We adopt the coordination space approach, which is standard in multiple robot motion planning. Assuming the priorities between robots are assigned in advance and the existence of a collision-free trajectory respecting those priorities, we propose a provably safe trajectory planner satisfying kinodynamic constraints. The algorithm is shown to run in real time and to return safe (collision-free) trajectories. Simulation results on synthetic data illustrate the benefits of the approach.
It is now clear that the combinatorial problem of assigning efficient priorities is inherently difficult, as noticed in @cite_7 and developed in the priority-based framework in @cite_8 . As a result, we will only consider in the present paper the issue of planning "good" trajectories for already assigned priorities. When the robots can start and stop instantaneously, it is relatively easy to define an optimal trajectory for fixed priorities. This trajectory is referred to as the left-greedy trajectory @cite_7 @cite_8 . However, taking into account acceleration (and higher derivatives) constraints turns the optimization problem into a "highly non-trivial" problem (as suggested in the conclusion of the paper @cite_7 ). In the present paper, we address the challenging problem of finding safe trajectories that respect this type of constraints. In @cite_10 , the problem is formulated as a mixed integer nonlinear programming problem, and the solution proposed is suitable only for a "reasonable" and fixed number of robots. Moreover, priority assignment and trajectory planning are not decoupled. In the present paper, we focus on a low complexity solution to the trajectory planning problem with assigned priorities which is applicable for a large and potentially varying number of robots.
@cite_10 @cite_7 @cite_8
2045726379 2774807875 2138693458 1495441213
This contribution presents a novel approach for efficient online planning of topologically distinctive mobile robot trajectories. Trajectory optimization deforms an initial coarse path drafted by a global planner with respect to robot motion related objectives and constraints. The primary objective is to reach a goal state in minimal time on a collision free path that adheres to the kinematic and dynamic constraints of the mobile robot. Conventional local planners get often stuck in a local optimal trajectory as they are unable to transit across obstacles. Our approach seeks the globally optimal trajectory as it maintains and optimizes a subset of admissible candidate trajectories of distinctive topologies in parallel. In case of dynamic environments the planner switches to the current globally optimal trajectory among the candidate set. The online trajectory planning with timed elastic bands is tightly integrated with the robot motion feedback control. The comparative analysis with conventional local planners confirms the advantages of maintaining distinctive topologies to circumnavigate dynamic obstacles. Consider a setting where robots must visit sites represented as nodes in a graph, but each robot may fail when traversing an edge. The goal is to find a set of paths for a team of robots which maximizes the expected number of nodes collectively visited, while guaranteeing that the paths satisfy a notion of “independence” formalized by a matroid (e.g. limits on team size, number of visits to regions), and that the probabilities that each robot survives to its destination are above a given threshold. We call this problem the Matroid Team Surviving Orienteers (MTSO) problem, which has broad applications such as environmental monitoring in risky regions and search and rescue in dangerous conditions. We present the MTSO formally and detail numerous examples of matroids in a path planning context. We then propose an approximate greedy algorithm for selecting a feasible set of paths and prove that the value of the output is within a factor p s p s + λ of the optimum, where p s is the per-robot survival probability threshold and 1 λ ≤ 1 is the approximation factor of an oracle routine for the well known orienteering problem. We demonstrate the efficiency of our approach by applying it to a scenario where a team of robots must gather information while avoiding pirates in the Coral Triangle. When controlling dynamic systems, such as mobile robots in uncertain environments, there is a trade off between risk and reward. For example, a race car can turn a corner faster by taking a more challenging path. This paper proposes a new approach to planning a control sequence with a guaranteed risk bound. Given a stochastic dynamic model, the problem is to find a control sequence that optimizes a performance metric, while satisfying chance constraints i.e. constraints on the upper bound of the probability of failure. We propose a two-stage optimization approach, with the upper stage optimizing the risk allocation and the lower stage calculating the optimal control sequence that maximizes reward. In general, the upper-stage is a non-convex optimization problem, which is hard to solve. We develop a new iterative algorithm for this stage that efficiently computes the risk allocation with a small penalty to optimality. The algorithm is implemented and tested on the autonomous underwater vehicle (AUV) depth planning problem, and demonstrates a substantial improvement in computation cost and suboptimality, compared to the prior arts. Minimum time and minimum energy point-to-point trajectories for an industrial robot of the type Manutec r3 are computed subject to state constraints on the angular velocities. The numerical solutions of these optimal control problems are obtained in an efficient way by a combination of a direct collocation and an indirect multiple shooting method. This combination links the benefits of both approaches: A large domain of convergence and a highly accurate solution. The numerical results show that the constraints on the angular velocities become active during large parts of the time optimal motion. But the resulting stress on the links can be significantly reduced by a minimum energy trajectory that is only about ten percent slower than the minimum time trajectory. As a by-product, the reliability of the direct collocation method in estimating adjoint variables and the efficiency of the combination of direct collocation and multiple shooting is demonstrated. The highly accurate solutions reported in this paper may also serve as benchmark problems for other methods.