PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometric Motion Planning for Affine Control Systems with Indefinite Boundary Conditions and Free Terminal Time

Shenyu Liu, Yinai Fan, Mohamed-Ali Belabbas

arXiv:2001.04540v1eess.SYcs.SY

TL;DR

Motion planning for affine systems with drift is difficult when endpoint constraints are partial and terminal time is free, since reachable states depend on time. The paper extends a geometric algorithm using variational conditions and time augmentation. In the unicycle example, its planned path has lower time and energy than the heuristic path, though the method provides an approximation rather than a true minimal-cost solution.

  • Problem

    With drift, reachable states depend on terminal time, while practical motion-planning problems may leave some boundary states unspecified and cannot fix the time in advance.

    Source: §I · p. 1

  • Method

    The paper extends its geometric motion-planning algorithm using variational conditions for free boundary states and an augmented true-time state for free terminal time.

    Source: §I · p. 1, A. Augmenting the true time · p. 3

  • Results

    In the unicycle example, the algorithm gives T = 1.4072 and E = 21.1022, both lower than for the compared heuristic path.

    Source: §V · p. 5

  • Takeaways & Limitations

    The method offers a systematic way to approximate motion-planning solutions with indefinite boundary conditions and free terminal time.

    Source: C. Cost minimizing · p. 5, §VI · p. 6

    The method trades the true minimal cost and exact optimal-solution expression for a systematic approximation, and the parallel-parking example has no globally minimal energy cost.

    Source: §V · p. 6

Abstract

from arXiv · show

The problem of motion planning for affine control systems consists of designing control inputs that drive a system from a well-defined initial to final states in a desired amount of time. For control systems with drift, however, understanding which final states are reachable in a given time, or reciprocally the amount of time needed to reach a final state, is often the most difficult part of the problem. We address this issue in this paper and introduce a new method to solve motion planning problems for affine control systems, where the motion desired can have indefinite boundary conditions and the time required to perform the motion is free. The method extends on our earlier work on motion planning for systems without drift. A canonical example of parallel parking of a unicycle with constant linear velocity is provided in this paper to demonstrate our algorithm.

I. INTRODUCTION

Motion planning with drift remains challenging when boundary conditions are partial and terminal time is free, because reachable states depend on time. The paper extends a geometric planning method to these settings and formulates the search for an admissible path as an optimization problem.

I. INTRODUCTION

  • With indefinite boundary conditions, only a subset of state components at the endpoints need be fixed, and free endpoint states can be selected to satisfy the motion-planning objective.The paper motivates this with tasks where some final-state components are unconstrained or feasible initial states must be found.Source: §I · p. 1
  • Free terminal time matters for systems with drift because the reachable space depends on the time allowed for the motion.Unlike driftless systems, input scaling cannot generally adjust the time span when drift or control constraints are present.Source: §I · p. 1
  • The method modifies an earlier geometric algorithm to handle indefinite boundary conditions and free terminal time using calculus of variations and state augmentation.The paper examines the algorithm on a unicycle case study.Source: §I · p. 1

II. PROBLEM FORMULATION AND PRELIMINARIES

  • The affine geometric heat flow treats the Euler–Lagrange condition for a local optimizer as a steady state of a PDE evolving the candidate curve.The evolution adds a parameter s while each fixed-s curve remains in the state-curve space.Source: §II · p. 2
  • The formulation distinguishes curves satisfying the boundary conditions from admissible paths, which must also satisfy the affine system dynamics.Finding a boundary-compatible curve is straightforward, while finding an admissible path is difficult; the algorithm approximates one when the problem is feasible.Source: §II · p. 2

III. INDEFINITE BOUNDARY CONDITIONS

For partial endpoint constraints, the method supplements the fixed boundary conditions with variational conditions at free endpoint states. Under this flow, the action decreases and is stationary exactly when the Euler–Lagrange condition holds.

III. INDEFINITE BOUNDARY CONDITIONS

  • Free endpoint states supply additional variational boundary conditions that complete the underdetermined Euler–Lagrange system.These conditions are imposed together with the specified boundary constraints when solving the affine geometric heat flow.Source: §III · p. 2

A. Decreasing action functional

  • Under indefinite boundary conditions, the action is nonincreasing along the affine geometric heat flow and is constant only when the Euler–Lagrange condition holds.The result is stated for solutions with the specified initial curve and boundary conditions.Source: A. Decreasing action functional · p. 2
  • The same variational argument can accommodate boundary states restricted to subsets, provided suitable transversality conditions hold.The paper notes that the proof is similar and omits it.Source: A. Decreasing action functional · p. 2

B. Algorithm

The algorithm solves the affine geometric heat flow with boundary conditions for fixed endpoint components and variational conditions for free ones, then extracts a control and integrates the system. Its guarantee is conditional on feasibility and a suitably chosen initial curve, and the output is approximate.

B. Algorithm

  • The algorithm solves the affine geometric heat flow with the prescribed and variational boundary conditions, extracts a control, and integrates the system to produce its path.The extracted control is computed from the evolved curve at a sufficiently large flow parameter.Source: B. Algorithm · p. 3
  • The integrated path is only approximately admissible, with endpoint accuracy depending on λ and the flow parameter; success also requires feasibility and an initial curve near an admissible path.That neighborhood is not known in advance.Source: B. Algorithm · p. 3
  • Theorem 1 guarantees boundary-constraint accuracy for feasible fixed-time problems when the initial curve lies in a suitable open set and the flow runs sufficiently long.The bound uses system Lipschitz constants and an upper bound on the constructed control-direction matrix.Source: B. Algorithm · p. 3

C. Comments on implementation in matlab

The MATLAB implementation uses symbolic processing for the first two algorithm steps and the pdepe solver for the affine geometric heat flow and its boundary conditions.

C. Comments on implementation in matlab

  • The first two algorithm steps are processed symbolically, while pdepe solves the heat-flow PDE in the solver's supported form.The implementation maps the PDE coefficients to the geometric-flow quantities.Source: C. Comments on implementation in matlab · p. 3
  • The implementation encodes fixed endpoint components through boundary residuals and free components through the corresponding derivative condition.The text gives separate boundary-function assignments for constrained and unconstrained endpoint components.Source: C. Comments on implementation in matlab · p. 3

IV. FREE TERMINAL TIME

With drift, input constraints, or free terminal time, reachability depends on the terminal time, so it cannot be fixed arbitrarily. The method handles free terminal time by augmenting the system with a state for true time.

IV. FREE TERMINAL TIME

  • Unlike the driftless case, an affine system with drift may have a reachable space that depends on terminal time, so fixing T arbitrarily can leave no solution.For a unicycle with unit linear velocity, reachable planar positions at time T lie within a ball of radius T.Source: §IV · p. 3

A. Augmenting the true time

  • The method augments the system with a true-time state τ, mapping the fixed domain [0, 1] to actual time from τ(0) = 0 to τ(1) = T.When τ is strictly increasing, its inverse recovers the control in true time as u†(t) = u(τ^-1(t)).Source: A. Augmenting the true time · p. 3
  • To enforce increasing true time, the method can set τ̇ = a² and ȧ = u₀, adding an auxiliary input u₀ to the twice-augmented system.The resulting state dynamics are ẋ = h(x)a² + F(x)a²u.Source: A. Augmenting the true time · p. 3
  • The augmentation defines new drift and control-direction terms, with one factor of a shifted into the control-direction matrix for a later energy argument.The augmented problem also retains the earlier boundary conditions and adds a boundary condition for τ at its start.Source: A. Augmenting the true time · p. 4

B. Algorithm for FTT problem

The FTT algorithm augments the states, constructs an invertible control-direction matrix, chooses an initial curve and guesses, solves the AGHF, then extracts a control and integrates the path.

B. Algorithm for FTT problem

  • The algorithm begins by augmenting the states and finding a bounded, differentiable x-dependent matrix F_c so the combined control-direction matrix is invertible.The augmented matrix uses the matrices defined for the augmented system.Source: B. Algorithm for FTT problem · p. 4
  • It chooses a terminal-time guess, endpoint guesses for a, and an initial curve matching the prescribed boundary data.The initial curve is defined on [0, 1] and satisfies the listed boundary values.Source: B. Algorithm for FTT problem · p. 4
  • The algorithm solves the AGHF with the specified boundary conditions and initial curve, then selects a sufficiently large evolution parameter s̄.It splits the resulting auxiliary control into components and defines the extracted control from them.Source: B. Algorithm for FTT problem · p. 4
  • It integrates the original system using the extracted control and an initial state taken from the evolved curve to obtain the planned path.The control is expressed in true time, and the integrated path is denoted x̃†.Source: B. Algorithm for FTT problem · p. 4

C. Cost minimizing

Under solvability and suitable initialization, the paper states a theorem for the FTT problem and argues that the planned path has relatively small energy. The energy claim follows from the chosen augmented dynamics, which make the action’s control norm equal the actual input energy.

C. Cost minimizing

  • The FTT theorem assumes the planning problem is solvable and requires a properly chosen initial curve and sufficiently large s̄ for its stated properties.The theorem statement also specifies a constant K for a further property, but the supplied passage does not give that property.Source: C. Cost minimizing · p. 4
  • The action is minimized through the AGHF, and the resulting L2 norm of u equals the energy of the actual input.The equality follows from the change of variable between the algorithm parameter and true time.Source: C. Cost minimizing · p. 4
  • The algorithm’s planned path is an approximation satisfying the IBCs with FTT, and its energy consumption is relatively small.The paper attributes this energy property to the particular design of F′, which shifts one factor a into the input.Source: C. Cost minimizing · p. 5

V. CASE STUDY: UNICYCLE WITH UNIT LINEAR

The unicycle case study applies the algorithm to parallel parking with unit linear velocity, comparing its free-terminal-time (FTT) solution with a heuristic path and fixed-time results. It also examines how energy varies with terminal time and why the global minimum is not attained.

V. CASE STUDY: UNICYCLE WITH UNIT LINEAR

  • The FTT algorithm gives T = 1.4072 and E = 21.1022, both below the heuristic path’s travel time and energy cost of approximately 25.13.The heuristic has travel time π/2 and energy cost 42 × π/2 ≈ 25.13.Source: §V · p. 5, Figure 2 · p. 5, Figure 3 · p. 6
  • The FTT algorithm extracts a control and integrated path from the AGHF solution once the coordinates barely change with respect to s.The solver stops at s̄ = 1, and the resulting control and path are shown in Figures 2 and 3.Source: §V · p. 5, Figure 2 · p. 5, Figure 3 · p. 6
  • The energy infimum is not attained: S-shaped paths with arbitrarily large turning radius require increasingly long travel times while their energy decreases.The control magnitude is approximately O(1/r), while total time is approximately O(r).Source: §V · p. 6, Figure 3 · p. 6, Figure 4 · p. 6
  • The FTT solution’s T and energy cost coincide with the local optimum produced by iterations of the fixed-terminal-time algorithm.The paper distinguishes this local result from the unattained global energy minimum.Source: §V · p. 6
  • Finding the exact optimal path through the maximum principle is difficult to generalize, while the proposed algorithm trades true minimal cost and exact expression for a systematic approximation.The maximum-principle approach leads to a second-order nonlinear ODE with no general solution stated for IBCs and FTT.Source: §V · p. 6

VI. CONCLUSION

The paper extends an earlier motion-planning method from fixed boundary conditions and terminal time to indefinite boundary conditions and free terminal time. It completes deficient boundary conditions through Lagrangian constraints and handles free time with time scaling and state augmentation.

VI. CONCLUSION

  • The method extends earlier affine-system motion planning from fixed boundary conditions and terminal time to indefinite boundary conditions and free terminal time.Source: §VI · p. 6
  • Deficient boundary conditions are completed by constraints on the Lagrangian with respect to derivatives of the corresponding states, verified by a perturbation argument.Source: §VI · p. 6
  • Time scaling yields an augmented affine system with drift and indefinite boundary conditions, allowing the authors to apply their earlier techniques.Source: §VI · p. 6
  • The authors demonstrate the algorithm on parallel parking by a unicycle with constant linear velocity.Source: §VI · p. 6

APPENDIX

The appendix proves a variational claim by expanding the Lagrangian to first order, integrating by parts, and applying the AGHF. The argument identifies when equality holds.

A. Proof of Lemma 1

  • The proof begins with a first-order approximation and substitutes it into the first variation of the Lagrangian.Source: A. Proof of Lemma 1 · pp. 6–7
  • Integration by parts produces an integrated term that vanishes under the stated endpoint condition for both t = 0 and t = T.Source: A. Proof of Lemma 1 · p. 7
  • After substituting the AGHF, equality holds if and only if x_s(t,s) = 0 almost everywhere on t ∈ [0, T].Source: A. Proof of Lemma 1 · p. 7

B. Proof of Theorem 2

The proof compares the FTT algorithm’s time-scaled step with the earlier fixed-time procedure. It relates the resulting integrated paths by a time reparameterization and invokes the earlier bounds.

B. Proof of Theorem 2

Loading 2001.04540v1…