PaperlayerView exact revision on arXiv

Source-linked AI summary

Search-based Motion Planning for Quadrotors using Linear Quadratic Minimum Time Control

Sikang Liu, Nikolay Atanasov, Kartik Mohta, Vijay Kumar

arXiv:1709.05401v1cs.RO

TL;DR

The paper addresses quadrotor planning in cluttered environments by seeking smooth, minimum-time, dynamically feasible trajectories without relying on a prior geometric path. It uses optimal-control motion primitives and graph search with a Linear Quadratic Minimum-Time heuristic. The resulting method supports safe, resolution-complete planning and online replanning, while refinement can produce unsafe or infeasible trajectories.

  • Problem

    The paper addresses planning smooth, collision-free, dynamically feasible, minimum-time quadrotor trajectories in obstacle-cluttered environments.

  • Method

    The method generates short-duration optimal-control motion primitives, searches their finite state-space lattice, and accelerates search using a Linear Quadratic Minimum-Time heuristic.

  • Results

    The approach generates resolution-complete, safe, dynamically feasible trajectories efficiently and supports online replanning during fast quadrotor navigation.

  • Takeaways & Limitations

    The method provides a foundation for safe and fast quadrotor navigation, with deterministic trajectories that can reduce state-estimation and control errors and save energy.

  • Takeaways & Limitations

    The refinement step can produce trajectories that are unsafe and infeasible despite improving smoothness.

Abstract

from arXiv · show

In this work, we propose a search-based planning method to compute dynamically feasible trajectories for a quadrotor flying in an obstacle-cluttered environment. Our approach searches for smooth, minimum-time trajectories by exploring the map using a set of short-duration motion primitives. The primitives are generated by solving an optimal control problem and induce a finite lattice discretization on the state space which can be explored using a graph-search algorithm. The proposed approach is able to generate resolution-complete (i.e., optimal in the discretized space), safe, dynamically feasibility trajectories efficiently by exploiting the explicit solution of a Linear Quadratic Minimum Time problem. It does not assume a hovering initial condition and, hence, is suitable for fast online re-planning while the robot is moving. Quadrotor navigation with online re-planning is demonstrated using the proposed approach in simulation and physical experiments and comparisons with trajectory generation based on state-of-art quadratic programming are presented.

I. INTRODUCTION

The paper formulates quadrotor trajectory planning as finding collision-free, dynamically feasible, smooth trajectories that balance duration and control effort. It converts the constrained Linear Quadratic Minimum-Time problem into graph search over motion primitives, enabling globally optimized planning without a prior shortest path.

  • Motivation: Quadrotor dynamics produce smoother trajectories than shortest-path methods that ignore dynamics, especially when the vehicle approaches a goal at non-zero velocity.The comparison contrasts the proposed dynamics-aware trajectory with a trajectory generated from a shortest path.
  • Approach: The approach explores trajectories using short-duration motion primitives generated from an optimal control problem rather than relying on a geometric shortest path.The primitives induce a finite lattice discretization that can be explored with graph search.
  • Problem formulation: The planning objective seeks collision-free, dynamically feasible, minimum-time, smooth trajectories while penalizing control effort.The trajectory smoothness or effort is defined as the squared L2-norm of the control input, and ρ sets the relative importance of duration versus smoothness.
  • Objective trade-off: The objective favors trajectories that prioritize fast arrival while retaining finite concern for low control effort.The trajectory comparison shows that sufficiently large but finite ρ prefers the low-effort fast trajectory over alternatives optimized only for time or effort.
  • Approach: Safety constraints on states and inputs are handled by converting the optimal-control problem into a deterministic shortest-path problem in a 3n-dimensional state space with 3-dimensional controls.The resulting A* search is resolution-complete in the discretized space.

III. OPTIMAL TRAJECTORY PLANNING

Motion primitives are generated by applying constant controls from a finite discretization for a fixed short duration. Integrating the system dynamics yields polynomial trajectories that define candidate motions from each state.

  • Motion primitive construction: The control set is discretized into M = (2µ + 1)^3 constant-control motion primitives by sampling each control axis.The discretization step is d_u = u_max/µ.
  • Motion primitive construction: Each primitive applies a constant control u_m for duration τ from an initial state containing position and its derivatives.The initial state may include velocity, acceleration, and higher-order derivatives.
  • Motion primitive construction: Integrating the constant control with the initial condition produces the corresponding polynomial state trajectory.The resulting trajectory is the system response generated by the selected control and duration.
  • Motion primitive construction: The resulting trajectories form a set of candidate motions whose endpoint states depend on the initial state, selected control, and fixed duration.Figure 3 illustrates the resulting motion primitives for acceleration-controlled and jerk-controlled systems.

B. Induced Space Discretization

The motion primitives induce a discrete reachable state space and graph. Because the bounded free space is discretized, the reachable state set is finite and can be searched through feasible primitive edges.

  • Induced space discretization: Motion primitives induce a discretization of the system state space.This proposition provides the basis for representing reachable states discretely.
  • Reachable states: Starting from x0, repeatedly applying all M primitives generates reachable states at successive multiples of τ.After two steps, the number of possible sequences is M^2 before accounting for state merging or feasibility.
  • Reachable states: The bounded, discretized free space makes the reachable state set S finite.This finiteness supports construction of a finite graph for search.
  • Graph representation: The graph G(S, E) contains discrete reachable states as nodes and motion primitives e = (u_m, τ) as connecting edges.Each edge connects consecutive states produced by one primitive.
  • Graph representation: A successor-generation procedure evaluates each finite-set control, checks primitive feasibility, computes the endpoint, and assigns an edge cost.Search continues by adding feasible successors and expanding until the goal region is reached.
  • Primitive optimality: Each motion primitive connecting consecutive states is optimal for the specified cost function.This proposition establishes optimality of individual primitive transitions under the paper’s cost.

C. Deterministic Shortest Trajectory

The continuous planning problem is restricted to piecewise-constant controls drawn from a finite primitive set, yielding a deterministic shortest-path problem. A* search solves this discretized problem while guaranteeing finite-time optimality in the discretized space.

  • Deterministic shortest trajectory: The reformulation constrains the control to be piecewise constant over N intervals of duration τ, with total duration T = Nτ.Each interval control u_k must belong to the finite primitive set U_M.
  • Deterministic shortest trajectory: The search chooses a sequence of N motion primitives that remains within the free state space and reaches the goal region.The discrete trajectory must satisfy the free-space constraint over every primitive interval.
  • Deterministic shortest trajectory: The optimal cost of the discretized problem is an upper bound on the original continuous problem because the discretized problem adds constraints.The discrete formulation is therefore computationally easier but more restricted.
  • Deterministic shortest trajectory: A* is used because search-based planning provides finite-time suboptimality or optimality guarantees, unlike sampling-based planners.The method focuses on an accurate consistent heuristic and guaranteed collision checking.

D. Heuristic Function Design

The heuristic design provides admissible and consistent lower bounds for graph search by relaxing state and input constraints. A Linear Quadratic Minimum-Time formulation yields a tighter cost estimate by incorporating control effort.

  • D. Heuristic Function Design: The heuristic approximates the optimal cost-to-go while remaining admissible, informative, and consistent for graph search.Admissibility requires underestimating optimal cost; consistency follows from the triangle inequality.
  • D. Heuristic Function Design: Velocity, acceleration, jerk, and higher-order derivative limits impose lower bounds on the minimum achievable travel time.The overall bound can use the maximum of individual bounds, although the implementation uses the simpler velocity-based bound.
  • D. Heuristic Function Design: The minimum-time heuristic relaxes state and input constraints by imposing only a lower bound on travel time.This relaxation produces a lower bound for the constrained planning problem.
  • D. Heuristic Function Design: The resulting heuristic is admissible for the discretized problem because each relaxation lower-bounds the preceding optimal cost.Consistency is inherited through the triangle inequality for distances.

2) Linear Quadratic Minimum Time:

The relaxed Linear Quadratic Minimum-Time problem supplies an explicit optimal-cost heuristic that accounts for control effort. Its optimal time is obtained from the lower bound or a positive root of the derivative of the polynomial cost.

  • 2) Linear Quadratic Minimum Time:: Removing state and input constraints converts the relaxed problem into the classical Linear Quadratic Minimum-Time problem.The constrained planning problem is therefore approximated through an analytically tractable relaxation.
  • 2) Linear Quadratic Minimum Time:: The optimal solution uses the final-state displacement and controllability Gramian to characterize the minimum-time trajectory.Proposition 3 defines δT and WT and determines the optimal time from the lower bound or a scalar equation.
  • 2) Linear Quadratic Minimum Time:: The optimal time is either the lower bound T̄ or the positive real root of C*(T)′ = 0.The optimal cost is then evaluated at T*.
  • 2) Linear Quadratic Minimum Time:: The optimal cost h2 is a better heuristic than h1 because it incorporates control effort while remaining admissible.This ordering follows from the relaxed problem’s lower-bound relationship to the constrained problem.

E. Collision Checking

Collision checking and dynamic feasibility are enforced separately for each motion-primitive edge. Polynomial extrema provide closed-form checks for derivative bounds, while sampled occupancy-grid positions approximate collision avoidance.

  • E. Collision Checking: An edge is valid only when its geometric trajectory lies in Pfree and all derivatives satisfy Dfree.The dynamic constraints include bounds on velocity, acceleration, and higher derivatives.
  • E. Collision Checking: Because velocity, acceleration, and higher derivatives are polynomials, their extrema can be computed over the edge duration.For n ≤ 3, these polynomials have order below 5 and their extrema are available in closed form.
  • E. Collision Checking: The method represents the environment with an occupancy grid and samples positions along each polynomial trajectory.A trajectory is accepted when every sampled position lies in free space.
  • E. Collision Checking: Sampling is an approximation that can miss cells traversed briefly, although the spacing condition prevents the trajectory from hitting obstacles under the stated resolution criterion.R denotes the occupancy-grid resolution.

IV. TRAJECTORY REFINEMENT

Trajectory refinement uses the collision-free, dynamically feasible prior trajectory—including waypoint timing—to generate a smoother higher-dimensional trajectory. However, refinement can compromise safety and feasibility.

  • IV. TRAJECTORY REFINEMENT: Trapezoid velocity time allocation treats the robot as a particle tracking a path, but the resulting trajectory can deform because it ignores expected dynamics.This motivates trajectory generation methods that account for system dynamics.
  • IV. TRAJECTORY REFINEMENT: The prior trajectory provides both collision-free waypoints and segment times for refining a smoother trajectory executable by the quadrotor.The refined trajectory is obtained by an unconstrained quadratic program with specified initial, final, and intermediate states.
  • IV. TRAJECTORY REFINEMENT: Figure 4 compares shortest-path, acceleration-controlled, jerk-controlled, and refined minimum-jerk trajectories from a start with initial velocity 4m/s.The refined minimum-jerk trajectories have continuous and smooth acceleration, unlike the unrefined acceleration- or jerk-controlled cases.
  • IV. TRAJECTORY REFINEMENT: The refinement step produces smoother trajectories but might make them unsafe and infeasible.The prior trajectory’s validity does not automatically transfer through unconstrained refinement.

V. EXPERIMENTAL RESULTS

The experiments compare heuristic quality, trajectory-generation runtime, and autonomous replanning. The proposed method uses dynamics-aware search to reduce expansions and produces smoother trajectories during navigation.

  • A. Heuristic Function: The minimum-cost heuristic h2 expands fewer nodes and accelerates search without loss of optimality.Unlike h1, h2 incorporates system dynamics, although computing it becomes harder in higher-dimensional systems.
  • A. Heuristic Function: When maximum velocity is low, the simpler maximum-speed heuristic h1 is efficient enough for any dynamic system.
  • B. Run Time Analysis: Planning in 3-D takes more time than in 2-D, while jerk-controlled planning is 10 times slower than acceleration-controlled planning.
  • C. Re-planning and Comparisons: In simulation, replanning at 3Hz in an obstacle-cluttered corridor produced smoother trajectories that avoided sharp turns compared with the traditional method.The maximum speed was set to 3m/s.
  • VI. CONCLUSION: The conclusion reports that deterministic optimal trajectories support safe, fast quadrotor navigation while reducing state-estimation and control errors.

APPENDIX A

The appendix shows how motion primitives generate discretized states and how trajectory-generation pipelines behave during non-static replanning. The proposed pipeline yields a smoother final trajectory than the traditional path-based alternative.

  • APPENDIX A: In the Pelican experiment, replanning begins from a non-static state while the robot moves at 2m/s vertically toward a goal.
  • APPENDIX A: The traditional path-based pipeline converts shortest path segments into a final trajectory, whereas the proposed pipeline converts a shortest trajectory into a smoother final trajectory.
  • APPENDIX A: In simulation, the traditional and proposed pipelines generate different overall replanning trajectories, with the proposed result described as smoother.
  • APPENDIX A: Applying a sequence of discretized inputs makes each state term an integer multiple of a constant, producing a discretized state space.

APPENDIX B

The appendix establishes that collision-free graph connections yield controls prescribed by the optimal-control construction. For the stated system structure, the resulting optimal control is constant along each connection.

  • APPENDIX B: Because graph edges are collision-free by construction, the optimal control connecting two states follows the control form prescribed by Proposition 3.
  • APPENDIX B: The system matrices’ block structure implies that the optimal control for a connection is constant, u*(t) ≡ uij.
Loading 1709.05401v1…