Search

In this article, we present an optimization-based framework for multicopter trajectory planning subject to geometrical configuration constraints and user-defined dynamic constraints. The basis of the framework is a novel trajectory representation built upon our novel optimality conditions for unconstrained control effort minimization. We design linear-complexity operations on this representation to conduct spatial–temporal deformation under various planning requirements. Smooth maps are utilized to exactly eliminate geometrical constraints in a lightweight fashion. A variety of state-input constraints are supported by the decoupling of dense constraint evaluation from sparse parameterization and the backward differentiation of flatness map. As a result, this framework transforms a generally constrained multicopter planning problem into an unconstrained optimization that can be solved reliably and efficiently. Our framework bridges the gaps among solution quality, planning efficiency, and constraint fidelity for a multicopter with limited resources and maneuvering capability. Its generality and robustness are both demonstrated by applications to different flight tasks. Extensive simulations and benchmarks are also conducted to show its capability of generating high-quality solutions while retaining the computation speed against other specialized methods by orders of magnitude. [ABSTRACT FROM AUTHOR]

Placing robotsoutside controlled conditions requires versatile movement representations that allow robots to learn new tasks and adapt them to environmental changes. The introduction of obstacles or the placement of additional robots in the workspace and the modification of the joint range due to faults or range-of-motion constraints are typical cases, where the adaptation capabilities play a key role for safely performing the robot’s task. Probabilistic movement primitives (ProMPs) have been proposed for representing adaptable movement skills, which are modeled as Gaussian distributions over trajectories. These are analytically tractable and can be learned from a small number of demonstrations. However, both the original ProMP formulation and the subsequent approaches only provide solutions to specific movement adaptation problems, e.g., obstacle avoidance, and a generic, unifying, probabilistic approach to adaptation is missing. In this article, we develop a generic probabilistic framework for adapting ProMPs. We unify previous adaptation techniques, for example, various types of obstacle avoidance, via-points, and mutual avoidance, in one single framework and combine them to solve complex robotic problems. Additionally, we derive novel adaptation techniques such as temporally unbound via-points and mutual avoidance. We formulate adaptation as a constrained optimization problem, where we minimize the Kullback–Leibler divergence between the adapted distribution and the distribution of the original primitive,while we constrain the probability mass associated with undesired trajectories to be low. We demonstrate our approach on several adaptation problems on simulated planar robot arms and seven-degree-of-freedom Franka Emika robots in a dual-robot-arm setting. [ABSTRACT FROM AUTHOR]

Planning high-speed trajectories for UAVs in unknown environments requires algorithmic techniques that enable fast reaction times to guarantee safety as more information about the environment becomes available. The standard approaches that ensure safety by enforcing a “stop” condition in the free-known space can severely limit the speed of the vehicle, especially in situations where much of the world is unknown. Moreover, the ad-hoc time and interval allocation scheme usually imposed on the trajectory also leads to conservative and slower trajectories. This work proposes FASTER (Fast and Safe Trajectory Planner) to ensure safety without sacrificing speed. FASTER obtains high-speed trajectories by enabling the local planner to optimize in both the free-known and unknown spaces. Safety is ensured by always having a safe back-up trajectory in the free-known space. The MIQP formulation proposed also allows the solver to choose the trajectory interval allocation. FASTER is tested extensively in simulation and in real hardware, showing flights in unknown cluttered environments with velocities up to 7.8 m/s, and experiments at the maximum speed of a skid-steer ground robot (2 m/s). [ABSTRACT FROM AUTHOR]

This article describes a topological approach to generating families of open- and closed-loop walking gaits for underactuated 2-D and 3-D biped walkers subject to configuration inequality constraints, physical holonomic constraints (e.g., closed-loop linkages), and virtual holonomic constraints (user-defined constraints enforced through feedback control). Our method constructs implicitly defined manifolds of feasible periodic gaits within a state-time-control space that parameterizes the biped’s hybrid trajectories. Since equilibrium configurations of the biped often belong to such manifolds, we use equilibria as “templates” from which to grow the gait families. Equilibria are reliable seeds for the construction of gait families, eliminating the need for random, intuited, or bio-inspired initial guesses at feasible trajectories in an optimization framework. We demonstrate the approach on several 2-D and 3-D biped walkers. [ABSTRACT FROM AUTHOR]

This article presents MADER, a 3-D decentralized and asynchronous trajectory planner for UAVs that generates collision-free trajectories in environments with static obstacles, dynamic obstacles, and other planning agents. Real-time collision avoidance with other dynamic obstacles or agents is done by performing outer polyhedral representations of every interval of the trajectories and then including the plane that separates each pair of polyhedra as a decision variable in the optimization problem. MADER uses our recently developed MINVO basis to obtain outer polyhedral representations with volumes 2.36 and 254.9 times, respectively, smaller than the Bernstein or B-Spline bases used extensively in the planning literature. Our decentralized and asynchronous algorithm guarantees safety with respect to other agents by including their committed trajectories as constraints in the optimization and then executing a collision check-recheck scheme. Finally, extensive simulations in challenging cluttered environments show up to a 33.9% reduction in the flight time, and a 88.8% reduction in the number of stops compared to the Bernstein and B-Spline bases, shorter flight distances than centralized approaches, and shorter total times on average than synchronous decentralized approaches. [ABSTRACT FROM AUTHOR]

In the article, we present an efficient optimization framework that solves trajectory optimization problems by decoupling state variables from timing variables, thereby decomposing a challenging nonlinear programming (NLP) problem into two easier subproblems. With timing fixed, the state variables can be optimized efficiently using convex optimization, and the timing variables can be optimized in a separate NLP, which forms a bilevel optimization problem. The challenge of obtaining the gradient of the timing variables is solved by sensitivity analysis of parametric NLPs. The exact analytic gradient is computed from the dual solution as a by-product, whereas existing finite-difference techniques require additional optimization. The bilevel optimization framework efficiently optimizes both timing and state variables which is demonstrated on generating trajectories for an UAV. Numerical experiments demonstrate that bilevel optimization converges significantly more reliably than a standard NLP solver, and analytical gradients outperform finite differences in terms of computation speed and accuracy. Physical experiments demonstrate its real-time applicability for reactive target tracking tasks. [ABSTRACT FROM AUTHOR]

Recent advances in trajectory replanning have enabled quadrotor to navigate autonomously in unknown environments. However, high-speed navigation still remains a significant challenge. Given very limited time, existing methods have no strong guarantee on the feasibility or quality of the solutions. Moreover, most methods do not consider environment perception, which is the key bottleneck to fast flight. In this article, we present RAPTOR, a robust and perception-aware replanning framework to support fast and safe flight, which addresses these issues systematically. A path-guided optimization approach that incorporates multiple topological paths is devised, to ensure finding feasible and high-quality trajectories in very limited time. We also introduce two perception-aware planning approaches to actively observe and avoid unknown obstacles. A risk-aware trajectory refinement ensures that unknown obstacles which may endanger the quadrotor can be observed earlier and avoid in time. The motion of yaw angle is planned to actively explore the surrounding space that is relevant for safe navigation. The proposed methods are tested extensively through benchmark comparisons and challenging indoor and outdoor aggressive flights. We release our implementation as an open-source package1 for the community. [ABSTRACT FROM AUTHOR]

This article presents a novel recursive smooth trajectory (RST) generation algorithm for application in robotics and in particular for unmanned aerial vehicles (UAVs). RST builds the trajectory recursively as a smooth polynomial path, thus a closed form trajectory satisfying any arbitrary dynamic limitation that translates into kinematic constraints (e.g., position, velocity, acceleration, etc.). Uncertainties and perturbations in the constraints are also discussed, modeled, and finally included in the calculation of the polynomial trajectory coefficients. Moreover, due to its recursive formulation, RST enables an immediate extension toward the solution of a trajectory optimization problem. In particular, it is shown that the minimum-snap piecewise polynomial trajectory can be interpreted as a special case of RST. The effectiveness of the proposed algorithm is demonstrated numerically via two illustrative scenarios. Its application to a UAV structure is also discussed to highlight the advantage of a smooth path over a piecewise one. Finally, the computational complexity and memory requirements are analyzed. [ABSTRACT FROM AUTHOR]

In this article, we propose a nonlinear receding horizon game-theoretic planner for autonomous cars in competitive scenarios with other cars. The online planner is specifically formulated for a multiple-car autonomous racing game, in which each car tries to advance along a given track as far as possible with respect to the other cars. The algorithm extends previous work on game-theoretic planning for single-integrator agents to be suitable for autonomous cars in the following ways: 1) by representing the trajectory as a piecewise polynomial; 2) incorporating bicycle kinematics into the trajectory; and 3) enforcing constraints on path curvature and acceleration. The game-theoretic planner iteratively plans a trajectory for the ego vehicle and then the other vehicles in sequence until convergence. Crucially, the trajectory optimization includes a sensitivity term that allows the ego vehicle to reason about how much the other vehicles will yield to the ego vehicle to avoid collisions. The resulting trajectories for the ego vehicle exhibit rich game strategies such as blocking, faking, and opportunistic overtaking. The game-theoretic planner is shown to significantly outperform a baseline planner using model-predictive control, which does not take interaction into account. The performance is validated in high-fidelity numerical simulations with three cars, in experiments with two small-scale autonomous cars, and in experiments with a full-scale autonomous car racing against a simulated vehicle (video is available at https://youtube.com/playlist?list=PLmIcLEh8KMje4rYBqRANDuKvqFvj7LCRp). [ABSTRACT FROM AUTHOR]

The time-optimal trajectory planning problem involves minimizing the time required to follow a path defined in space, subject to kinematic and dynamic constraints. Here, we introduce a novel technique, called the bisection algorithm (BA), which is fully implemented in C++ and extends dynamic programming approaches to the problem. These approaches, which rely on dividing the global problem into a series of simpler subproblems, become increasingly advantageous compared to direct transcription methods as the number of problem constraints increases. In contrast to nearly all other dynamic programming approaches, BA does not rely on finding a maximum-velocity curve or explicitly finding acceleration switching points during the trajectory planning process. Additionally, only one forward and one backward integration are used, during which all constraints are imposed. This approach is made feasible through careful control of the numerical integration process and the use of a bisection algorithm to resolve constraint violations during integration. BA is shown to be significantly simpler, faster, and more robust than recently proposed algorithms: a direct comparison is made for a series of paths to be followed by a serial manipulator, subject to kinematic constraints. The wide applicability of BA is then established by solving the time-optimal problem for a parallel manipulator following a complex path, subject to both kinematic and dynamic constraints. [ABSTRACT FROM AUTHOR]

The wheeled inverted pendulum (WIP) is an underactuated, nonholonomic mechatronic system, and has been popularized commercially as the Segway. Designing a control law for motion planning, that incorporates the state and control constraints, while respecting the configuration manifold, is a challenging problem. In this article, we derive a discrete-time model of the WIP system using discrete mechanics and generate optimal trajectories for the WIP system by solving a discrete-time constrained optimal control problem. Furthermore, we describe a nonlinear continuous-time model with parameters for designing a closed-loop linear–quadratic regulator (LQR). A dual control architecture is implemented in which the designed optimal trajectory is, then, provided as a reference to the robot with the optimal control trajectory as a feedforward control action, and an LQR in the feedback mode is employed to mitigate noise and disturbances for ensuing stable motion of the WIP system. While performing experiments on the WIP system involving aggressive maneuvers with fairly sharp turns, we found a high degree of congruence in the designed optimal trajectories and the path traced by the robot while tracking these trajectories. This corroborates the validity of the nonlinear model and the control scheme. Finally, these experiments demonstrate the highly nonlinear nature of the WIP system and robustness of the control scheme. [ABSTRACT FROM AUTHOR]

In this paper, we investigate energy-optimal control of robots with ultracapacitor-based regenerative drive systems. Based on a previously introduced framework, a fairly generic model is considered for the robot and the drive system. An optimal control problem is formulated to find point-to point trajectories maximizing the amount of energy regenerated and stored in the capacitor. The optimization problem, its numerical solution, and an experimental evaluation are demonstrated using a PUMA manipulator with custom regenerative drives. Power flows, stored regenerative energy, and efficiency are evaluated. Tracking of optimal trajectories is enforced on the robot using a standard robust passivity based control approach. Experimental results show that when following optimal trajectories, a reduction of about $\text{10}\text{--}\text{22}\%$ in energy consumption can be achieved for the conditions of the study, relative to the nonregenerative case. [ABSTRACT FROM AUTHOR]

Trajectory replanning for quadrotors is essential to enable fully autonomous flight in unknown environments. Hierarchical motion planning frameworks, which combine path planning with path parameterization, are popular due to their time efficiency. However, the path planning cannot properly deal with nonstatic initial states of the quadrotor, which may result in nonsmooth or even dynamically infeasible trajectories. In this article, we present an efficient kinodynamic replanning framework by exploiting the advantageous properties of the B-spline, which facilitates dealing with the nonstatic state and guarantees safety and dynamical feasibility. Our framework starts with an efficient B-spline-based kinodynamic (EBK) search algorithm, which finds a feasible trajectory with minimum control effort and time. To compensate for the discretization induced by the EBK search, an elastic optimization approach is proposed to refine the control point placement to the optimal location. Systematic comparisons against the state-of-the-art are conducted to validate the performance. Comprehensive onboard experiments using two different vision-based quadrotors are carried out showing the general applicability of the framework. [ABSTRACT FROM AUTHOR]

This paper presents an equivalence between feasible kinodynamic planning and optimal kinodynamic planning, in that any optimal planning problem can be transformed into a series of feasible planning problems in a state–cost space, whose solutions approach the optimum. This transformation yields a meta-algorithm that produces an asymptotically optimal planner, given any feasible kinodynamic planner as a subroutine. The meta-algorithm is proven to be asymptotically optimal and a formula is derived relating expected running time and solution suboptimality. It is directly applicable to a wide range of optimal planning problems because it does not resort to the use of steering functions or numerical boundary-value problem solvers. On a set of benchmark problems, it is demonstrated to perform, using the expansive space tree (EST) and rapidly-exploring random tree (RRT) algorithms as subroutines, at a level that is superior or comparable to related planners. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of robust take-off of a quadrotor unmanned aerial vehicle (UAV) in critical scenarios, such as in the presence of sloped terrains and surrounding obstacles. Throughout the maneuver, the vehicle is modeled as a hybrid automaton whose states reflect the different dynamic behaviors exhibited by the UAV. The original take-off problem is then addressed as the problem of tracking suitable reference signals in order to achieve the desired transitions between different hybrid states of the automaton. Reference trajectories and feedback control laws are derived to explicitly account for uncertainties in both the environment and the vehicle dynamics. Simulation results demonstrate the effectiveness of the proposed solution and highlight the advantages with respect to more standard open-loop strategies, especially for cases in which the slope of the terrain renders the take-off maneuver more critical to achieve. [ABSTRACT FROM AUTHOR]

Visually guided robotic capturing of a moving object often requires long-term prediction of the object motion not only for a smooth capture but because visual feedback may not be continually available, e.g., due to vision obstruction by the robotic arm, as well. This paper presents a combined prediction and motion-planning scheme for robotic capturing of a drifting and tumbling object with unknown dynamics using visual feedback. A Kalman filter estimates the states and a set of dynamics parameters of the object needed for long-term prediction of the motion from noisy measurements of a vision system. Subsequently, the estimated states, parameters, and predicted motion trajectories are used to plan the trajectory of the robot’s end-effector to intercept a grapple fixture on the object with zero relative velocity (to avoid impact) in an optimal way. The optimal trajectory minimizes a cost function, which is a weighted linear sum of travel time, distance, cosine of a line-of-sight angle (object alignment for robotic grasping), and a penalty function acting as a constraint on acceleration magnitude. Experiments are presented to demonstrate the robot-motion planning scheme for autonomous grasping of a tumbling satellite. Two robotics manipulators are employed: One arm drifts and tumbles the mockup of a satellite, and the other arm that is equipped with a robotic hand tries to capture a grapple fixture on the satellite using the visual guidance system. [ABSTRACT FROM AUTHOR]

The subject of this paper is the patrolling of an environment with the aid of a team of autonomous agents. We consider both the design of open-loop trajectories with optimal properties and of distributed control laws converging to optimal trajectories. As performance criteria, the refresh time and the latency are considered, i.e., respectively, time gap between any two visits of the same region and the time necessary to inform every agent about an event occurred in the environment. We associate a graph with the environment, and we study separately the case of a chain, tree, and cyclic graph. For the case of chain graph, we first describe a minimum refresh time and latency team trajectory and propose a polynomial time algorithm for its computation. Then, we describe a distributed procedure that steers the robots toward an optimal trajectory. For the case of tree graph, a polynomial time algorithm is developed for the minimum refresh time problem, under the technical assumption of a constant number of robots involved in the patrolling task. Finally, we show that the design of a minimum refresh time trajectory for a cyclic graph is NP-hard, and we develop a constant factor approximation algorithm. [ABSTRACT FROM AUTHOR]

An important motivation for work on legged robots has always been their potential for high-performance locomotion on rough terrain. Nevertheless, most existing control algorithms for such robots either make rigid assumptions about their environments or rely on kinematic planning at low speeds. Moreover, the traditional separation of planning from control often has negative impact on the robustness of the system. In this paper, we introduce a new method for dynamic, fully reactive footstep planning for a planar spring–mass hopper, based on a careful characterization of the model dynamics and the design of an associated deadbeat controller, used within a sequential composition framework. This yields a purely reactive controller with a large domain of attraction that requires no explicit replanning during execution. We show in simulation that plans constructed for a simplified dynamic model can successfully control locomotion of a more complete model across rough terrain. We also characterize the performance of the planner over rough terrain and show that it is robust against both model uncertainty and measurement noise without replanning. [ABSTRACT FROM AUTHOR]

Singularity is a major problem for parallel robots as in these configurations the robot cannot be controlled, and there may be infinite forces/torques in its joints, possibly leading to its breakdown. Hence, such a configuration must usually be avoided, and certifying the absence of singularity within a prescribed workspace or on a given trajectory is essential for a practical use of this type of robots. Singularity conditions are usually quite complex, and therefore a purely analytical analysis is difficult. We present here an algorithm that combines formal and numerical calculations for detecting singularity or closeness to a singularity within an arbitrary workspace or trajectory. This algorithm has the very important advantage of being able to deal with any robot mechanical structure and to manage uncertainties in the robot control and in the robot modeling. [ABSTRACT FROM PUBLISHER]

An introduction is presented in which the editor discusses articles in the issue on topics including recent advances in aerial swarm robotics, trajectory optimization for aerial robots or unmanned aerial vehicles (UAVs) and a distributed formation control algorithm for a group of aerial robots.