PaperlayerView exact revision on arXiv

Source-linked AI summary

Funnel Libraries for Real-Time Robust Feedback Motion Planning

Anirudha Majumdar, Russ Tedrake

arXiv:1601.04037v3cs.ROcs.AIeess.SYmath.DSmath.OC

TL;DR

Agile robots operating near obstacles lack safety guarantees under environmental and dynamics uncertainty. This paper computes disturbance-bounded feedback funnels for runtime planning and demonstrates the approach in simulations and fixed-wing hardware obstacle avoidance at ∼12 mph.

  • Problem

    Agile robots operating close to obstacles lack safety guarantees and can fail under uncertainty in the environment and dynamics.

    Source: §1 · p. 1

  • Method

    The approach computes funnels that bound forward uncertainty from given initial conditions and minimizes their volume using semidefinite programming.

    Source: §4 · p. 9, §4.1 · p. 10

  • Results

    Demonstrations cover ground-vehicle and quadrotor simulations plus fixed-wing obstacle avoidance at ∼12 mph, among the first provably safe, robust real-time controls for complex nonlinear robots.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    Accounting for disturbance vulnerability can change primitive choice, and the planner can abort when neither maneuver is guaranteed to succeed.

    Source: §1.1 · pp. 2–3

    The time-sampled approximation can reduce computation but does not provide an exact funnel certificate.

    Source: §4.2 · p. 12

Abstract

from arXiv · show

We consider the problem of generating motion plans for a robot that are guaranteed to succeed despite uncertainty in the environment, parametric model uncertainty, and disturbances. Furthermore, we consider scenarios where these plans must be generated in real-time, because constraints such as obstacles in the environment may not be known until they are perceived (with a noisy sensor) at runtime. Our approach is to pre-compute a library of "funnels" along different maneuvers of the system that the state is guaranteed to remain within (despite bounded disturbances) when the feedback controller corresponding to the maneuver is executed. We leverage powerful computational machinery from convex optimization (sums-of-squares programming in particular) to compute these funnels. The resulting funnel library is then used to sequentially compose motion plans at runtime while ensuring the safety of the robot. A major advantage of the work presented here is that by explicitly taking into account the effect of uncertainty, the robot can evaluate motion plans based on how vulnerable they are to disturbances. We demonstrate and validate our method using extensive hardware experiments on a small fixed-wing airplane avoiding obstacles at high speed (~12 mph), along with thorough simulation experiments of ground vehicle and quadrotor models navigating through cluttered environments. To our knowledge, these demonstrations constitute one of the first examples of provably safe and robust control for robotic systems with complex nonlinear dynamics that need to plan in real-time in environments with complex geometric constraints.

1 Introduction

The paper combines feedback control, motion planning, Lyapunov theory, and convex optimization to plan safely in real time under dynamics uncertainty and unknown environments. Its funnel library supports runtime choices that account for vulnerability to disturbances.

1 Introduction

  • Agile robots operating near obstacles face nonlinear, underactuated, input-constrained dynamics, disturbances and modeling error, and environments unknown until runtime.The paper motivates these challenges with UAVs, legged robots, and mobile manipulators, noting that uncertainty can lead to dramatic failures.Source: §1 · p. 1

1.1 Contributions

  • Offline, the authors use SOS optimization to create trajectory-specific controllers and bound worst-case reachable sets as funnels, then compose these plans online in unseen environments.The closed-loop system is guaranteed to remain within each funnel despite modeled uncertainty and bounded external disturbances.Source: §1.1 · p. 2
  • The funnel library lets robots choose motion primitives by accounting for uncertainty, or abort and transition to hover when neither maneuver is guaranteed to succeed.A dynamic roll may avoid obstacles by a larger margin yet be more vulnerable to wind gusts and initial-state perturbations than a straighter maneuver.Source: §1.1 · pp. 2–3
  • The authors validate the approach in ground-vehicle and quadrotor simulations and fixed-wing airplane hardware experiments avoiding obstacles at ∼12 miles per hour.They describe these demonstrations as among the first examples of provably safe, robust control for complex nonlinear robots that plan in real time in cluttered environments.Source: §1.1 · p. 3

2 Relevant Work

This section reviews motion-planning, uncertainty, reachability, and Lyapunov/SOS approaches, highlighting the need for real-time planning with explicit robustness guarantees for nonlinear systems and runtime constraints.

2.1 Motion Planning

  • Trajectory libraries serve diverse robotic applications, and Maneuver Automata formalize them as hybrid automata.Related work also studies real-time planning with static and dynamic obstacles, sparse offline trajectory generation, sub-modular sequence optimization [Dey et al., 2011, Dey, 2015], and skill trees learned from demonstrations.Source: §2.1 · pp. 3–4

2.2 Planning under Uncertainty

  • Chance-constrained and belief-space planning reason about uncertainty but typically assume linear dynamics and Gaussian beliefs; this work instead bounds disturbances and reachable sets.Gaussian belief approximations generally do not track the true belief state, so they do not provide robustness guarantees in general.Source: §2.2 · p. 4
  • POMDPs model uncertainty in state and dynamics, but their literature typically emphasizes discretized state and action spaces rather than this work’s continuous spaces.The cited framework is relevant to the problem, while this paper focuses on continuous-state, continuous-action dynamical systems.Source: §2.2 · p. 4

2.3 Reachable Sets

  • Linear reachability methods approximate nonlinear dynamics conservatively, while HJB methods assume unsafe sets are known beforehand and historically struggle beyond roughly 5–6 dimensions.This work computes outer reachable-set approximations without linearizing the system and emphasizes safe real-time planning when obstacles are revealed at runtime.Source: §2.3 · p. 5
  • A randomized planner with composable disturbance-aware tubes is closest; this work emphasizes real-time planning and SOS-computed tubes whose size is explicitly minimized.The cited planner assumes obstacle positions are known a priori, while this work addresses obstacles revealed at runtime.Source: §2.3 · p. 5

2.4 Lyapunov Theory and SOS programming

  • SOS programming checks Lyapunov conditions through polynomial nonnegativity and supports synthesizing feedback to minimize funnel size under bounded disturbances and model uncertainty.If the system starts in the specified initial set, it remains in the computed funnel despite those uncertainties and disturbances.Source: §2.4 · pp. 5–6
  • LQR-Trees and SOS barrier certificates depend on offline assumptions: the former cannot handle runtime-unknown constraints, and the latter require known obstacle geometry and are infeasible to compute in real time.LQR-Trees precompute locally stabilizing controllers; barrier certificates guarantee trajectories avoid specified unsafe regions.Source: §2.4 · p. 6

3 Background

The background introduces semidefinite programming as a tractable convex optimization framework and sums-of-squares programming as a way to certify polynomial nonnegativity. SOS multipliers extend these certificates to semialgebraic sets, enabling funnel computation.

3.1 Semidefinite Programming (SDP)

  • SDPs minimize a linear cost over positive semidefinite matrices subject to linear constraints and admit efficient interior-point solutions.Linear programming, quadratic programming, and second-order cone programming are special cases.Source: §3.1 · pp. 6–7

3.2 Sums-of-Squares (SOS) Programming

  • Polynomial nonnegativity is NP-hard, but SOS status provides a sufficient certificate expressible through a positive semidefinite matrix and coefficient-matching constraints.Allowing polynomial coefficients to be decision variables yields SOS programs that can be solved as SDPs.Source: §3.2 · p. 7
  • For semialgebraic sets, SOS multiplier constraints provide sufficient certificates of nonnegativity; this generalized S-procedure is used in Section 4 to compute funnels.The multiplier polynomials act analogously to Lagrange multipliers, and the certificate follows because their terms are non-positive on the set.Source: §3.2 · pp. 7–8

4 Computing Funnels

Section 4 constructs funnels as time-varying outer bounds on reachable states and develops SOS-based methods to compute them, including extensions for disturbances and feedback synthesis.

4 Computing Funnels

  • A funnel is a time-indexed set containing states reachable from the initial conditions, certified by requiring its boundary function to grow more slowly than its threshold.The sets are parameterized as sub-level sets of a nonnegative time-varying function V.Source: §4 · pp. 8–9
  • For a given initial set, the method minimizes funnel volume to bound forward uncertainty, unlike prior approaches that maximize funnels to enlarge the set of initial conditions stabilized to a goal [Tedrake et al., 2010, Burridge et al., 1999, Conner et al., 2011].Bounding uncertainty is intended to help prevent collisions with obstacles in previously unseen environments.Source: §4 · p. 9

4.1 Numerical implementation using SOS programming

  • SOS programming converts the polynomial funnel constraints into finite-dimensional SDPs; alternating between decision-variable groups monotonically improves cost and converges, though not necessarily to an optimum.For quadratic V, the funnels are ellipsoids whose volume can be minimized directly by maximizing the determinant of their defining matrices.Source: §4.1 · pp. 9–11

4.2 Approximation via time-sampling

  • Time-sampling removes algebraic dependence on time and can speed computation, but does not provide an exact funnel certificate; prior results report small accuracy loss in numerical examples [Tobenkin et al., 2011].The approximation checks the funnel condition at finitely many time points.Source: §4.2 · pp. 11–12

4.3.1 Uncertainty in the dynamics

  • With bounded disturbances or parametric uncertainty, the funnel condition must hold for every valid disturbance, and SOS multipliers encode the disturbance-set constraints.The method assumes polynomial dependence of the closed-loop dynamics on the disturbance and a semi-algebraic disturbance set.Source: §4.3.1 · p. 13

4.3.2 Feedback control synthesis

  • For control-affine systems, a polynomial feedback controller can be optimized with the funnel variables; an added alternation step searches for the controller and threshold together, and the objective sequence converges.The extensions overview also lists handling input saturation and generalizing the cost function.Source: §4.3 · p. 13, §4.3.2 · p. 14

A. Approach 1

The approach incorporates actuator limits into funnel verification by saturating control inputs and checking Lyapunov conditions across saturation regimes. Feedback synthesis minimizes funnel volume through alternating optimization steps.

A. Approach 1

  • Actuator limits are incorporated into verification for the single-input case, with the framework described as extendable to multiple inputs.Source: A. Approach 1 · p. 14
  • The control input is saturated at the bounds umin and umax, while values between them pass through unchanged.Source: A. Approach 1 · p. 14
  • Feedback synthesis minimizes the sum of funnel volumes in three alternating steps, updating the controller and selected funnel variables while fixing others.The steps successively search over the controller with V and ρ fixed, over the controller and ρ with V and other terms fixed, and over V, ρ, and related terms with the controller fixed.Source: A. Approach 1 · p. 15
  • Lyapunov conditions are checked piecewise for inputs below, above, or within the saturation bounds, and enforced by adding multipliers to the optimization program.The boundary conditions require the corresponding derivative of V to remain below the derivative of ρ when V(t, x̄) = ρ(t).Source: A. Approach 1 · p. 15

B. Approach 2

The section describes a less conservative-cost tradeoff for handling bounded control inputs, a projected-volume funnel objective, and practical choices for trajectory generation and initialization. These choices support computing funnels while addressing optimization size and initialization sensitivity.

B. Approach 2

  • For many-input systems, a conservative in-funnel control-bound condition adds one constraint per input, avoiding exponentially many saturation cases and yielding smaller optimization problems.The condition requires the control input to remain within its specified bounds throughout the verified funnel.Source: B. Approach 2 · pp. 15–16

4.3.4 A more general cost function

  • To minimize projected funnel volume, each iteration maximizes a linearization of the projected ellipsoid determinant because that determinant is nonlinear in the original ellipsoid matrix.The linearization is taken at the matrix solution from the previous iteration.Source: §4.3.4 · p. 16

4.4.1 Trajectory generation

  • Direct collocation trajectory optimization generates the dynamically feasible nominal control and trajectory used in the results and works well in practice at high dimensions; RRT and RRT⋆ are alternatives.The method requires a feasible open-loop input and corresponding nominal trajectory.Source: §4.4.1 · p. 16

4.4.2 Initializing V and ρ

  • A time-varying LQR Lyapunov candidate initializes V; exponential ρ often suffices for feasibility, while multiple starts or neighboring-maneuver solutions can address sensitivity to local solutions.Algorithms 1 and 2 are not guaranteed to converge globally, so initialization can affect solution quality.Source: §4.4.2 · pp. 16–17

5 Funnel Libraries · 5.1 Sequential composition

The section frames funnels as robust motion primitives and motivates sequencing them into composite robust plans. It defines sequential composability by containment between consecutive funnels’ outlet and inlet.

5 Funnel Libraries

  • Funnels are robust motion primitives, providing robustness to initial conditions and uncertainty in the dynamics.Source: §5.1 · p. 17
  • A funnel library can be a collection of funnels and associated feedback controllers, with added structure describing how to sequence them into composite plans.Source: §5.1 · p. 17

5.1 Sequential composition

  • The finite-horizon funnel definition differs from Burridge et al. (1999), which considers infinite-horizon policies, and is akin to conditional invariance [Kantor and Rizzi, 2003, Conner et al., 2011].Source: §5.1 · p. 17
  • Two funnels are sequentially composable when the first funnel’s terminal set is contained in the second funnel’s initial set.Formally, F1(T1) ⊂ F2(0).Source: §5.1 · p. 17
  • Sequential composition requires the outlet of one funnel to lie within the inlet of the next.Source: §5.1 · p. 17
  • The sequential composition of two composable funnels is itself a funnel.Source: §5.1 · p. 17

5.2 Exploiting invariances in the dynamics

The section uses cyclic-coordinate invariance to extend funnel reuse and define sequential composition modulo invariances (MI). A valid funnel can be shifted along cyclic coordinates, allowing its inlet to be aligned with a preceding funnel’s outlet.

5.2 Exploiting invariances in the dynamics

  • Dynamics depending only on non-cyclic coordinates admit cyclic coordinates; quadrotor and fixed-wing airplane dynamics can be independent of position and yaw.For Lagrangian systems, cyclic coordinates are coordinates on which the Lagrangian does not depend.Source: §5.2 · pp. 17–18
  • Shifting a funnel along cyclic coordinates yields another valid funnel, creating an infinite family of funnels from one funnel.The associated feedback controller is also shifted by modifying the tracked reference trajectory.Source: §5.2 · p. 18
  • MI composition holds when some cyclic-coordinate shift of the second funnel makes its entire inlet contain the first funnel’s outlet.The shift applies to the funnel, not just its cyclic-coordinate projection.Source: §5.2 · p. 19, Figure 3 · p. 19
  • MI compatibility concerns the funnels themselves, unlike the nominal-trajectory compatibility used to sequence Maneuver Automaton trajectories.Nominal-trajectory compatibility is neither necessary nor sufficient for MI composability.Source: §5.2 · pp. 19–20

5.3 Runtime composability

Runtime composability lets a second funnel follow the first by shifting it along cyclic coordinates so its inlet contains the first funnel’s outlet state. The required shift may depend on the state reached at runtime, enabling reuse of robust motion plans.

5.3 Runtime composability

  • For every outlet state of F1, runtime composability requires a cyclic-coordinate shift of F2 whose inlet contains that state.This guarantees F2 can execute after F1, although the required shift is not known until runtime.Source: §5.3 · p. 20
  • Runtime shifts exploit dynamic invariances to reuse robust motion plans in different scenarios, such as shifting a UAV funnel to contain its current state.The example describes reusing a funnel computed for a different starting position while flying through a cluttered environment.Source: §5.3 · p. 20
  • Figure 4 shows two funnels that are not sequentially composable MI because F2’s inlet is not large enough in the xc dimension, yet are runtime composable because πnc(F1(T1)) ⊂ πnc(F2(0)).Source: Figure 4 · p. 21

5.4 Checking composability

The section describes offline tests for sequential, cyclic-coordinate-shifted (MI), and runtime composability of two polynomially defined funnels. The tests use SOS programming or, for important ellipsoidal cases, semidefinite programming (SDP).

5.4.1 Sequential composability

  • Sequential composability is characterized by an equivalent condition and checked with a simple SOS program using the generalized S-procedure.The test applies to funnels defined by polynomial functions and their time-varying bounds.Source: §5.4.1 · pp. 21–22, §5.4 · p. 21

5.4.2 Sequential composition MI

  • For ellipsoidal endpoints, an SDP searches for a cyclic-coordinate shift, and is feasible if and only if the funnels are sequentially composable MI.The endpoint functions must be quadratic, but no degree restriction is imposed on the funnel functions at other times.Source: §5.4.2 · p. 22
  • For non-ellipsoidal MI funnels, fixing a shift reduces the check to sequential composability; an SOS test can verify containment, with local search suggested if the initial shift fails.A natural initial shift aligns the nominal trajectories’ cyclic coordinates at the first funnel’s end and the second funnel’s start.Source: §5.4.2 · p. 23

5.4.3 Runtime composability

  • For runtime composability, ellipsoidal endpoints permit exact non-cyclic projections and an SDP containment check; general polynomial cases can use quantifier elimination, whose worst-case complexity is poor.The paper’s examples use ellipsoidal inlets and outlets, avoiding the general-case complexity concern.Source: §5.4.3 · p. 23

5.5 Funnel library

A funnel library is the primary data structure for robust real-time planning, organizing funnels, their runtime composability, associated feedback controllers, and execution times.

5.5 Funnel library

  • Graph edges connect funnels that are runtime composable at a specified execution time; sequential composability can be checked at an intermediate time τ1 by testing F1(τ1) ⊂ F2(0).Each funnel may itself be constructed from simpler funnels that have been sequentially composed.Source: §5.5 · pp. 23–24
  • A funnel library is a tuple of funnels, their runtime-composability graph, associated feedback controllers, and execution times.The section introduces it as the primary data structure for robust real-time planning.Source: §5.5 · p. 23
  • Graph connectedness is not required, but continuous-operation tasks may call for strong connectivity; graph diameter or girth may relate to task efficiency, while choosing graph properties is left open.Without strong connectivity, some funnels may not be executable in the future.Source: §5.5 · p. 24

6 Real-time Planning with Funnels

The section describes how robots select and execute collision-free funnels using current state and obstacle observations, and outlines optimization methods for shifting funnels and alternatives for global planning. Replanning accounts for newly observed obstacles or leaving the current funnel, with a failsafe maneuver assumed if no safe funnel is found.

6 Real-time Planning with Funnels

  • A runtime planner selects a composable funnel shift whose inlet contains the current state and whose projection avoids obstacles, ensuring collision-free execution despite uncertainty and disturbances.The planner searches funnels in a preference order and can align the nominal trajectory with the robot’s current location before checking collisions.Source: §6 · pp. 24–25
  • If no collision-free funnel is found, the assumed failsafe maneuver keeps the robot safe; replanning also occurs when execution time expires, the state leaves the funnel, or new obstacles make it unsafe.Examples of failsafes include stopping a ground vehicle or transitioning a quadrotor or fixed-wing airplane to hover or propellor-hang mode.Source: §6 · p. 25

6.1 Shifting funnels at runtime

  • For runtime funnel shifting, the general optimization is non-convex but has only as many decision variables as cyclic coordinates, allowing gradient-based methods to search for feasible shifts.The shift must contain the current state in the funnel inlet and avoid obstacles.Source: §6.1 · p. 26
  • When cyclic coordinates are configuration variables, a restricted shift search uses convex QCQP constraints for inlet containment and obstacle avoidance.With an ellipsoidal inlet, containment is a convex quadratic constraint; collision normals and distances yield linear shift constraints for convex funnel segments and obstacles, which may be decomposed if non-convex.Source: §6.1 · pp. 26–27

6.2 Global Planning

  • Global planning can search collision-free funnel sequences with grid-based methods, extend maneuver-automaton planning subject to collision constraints, or grow a backward RRT-like funnel tree from a goal.The grid-based approach can minimize a criterion such as nominal distance traversed; maneuver automata rely on trims and transition maneuvers. Backward search is analogous to preimage backchaining and resembles LQR-Trees, but uses a precomputed funnel library and accounts for collisions.Source: §6.2 · p. 28

7 Examples

Section 7 presents two simulation examples: a ground vehicle navigating randomly placed obstacles and a quadrotor navigating a polygonal-obstacle environment. The examples illustrate funnel-library planning and, for the quadrotor, geometric conditions intended to guarantee collision-free flight.

7.1 Ground Vehicle Model

  • The ground-vehicle library contains 20 trajectories generated by direct collocation with v(t) = 10 m/s; controllers and funnels account for parametric uncertainty and input saturation.A time-varying degree-3 Taylor expansion and time-sampled linear feedback with 15 samples were used; each funnel took approximately 5–10 minutes to compute, and the composability graph was fully connected.Source: §7.1 · pp. 29–30
  • The funnel-library planner significantly outperformed the trajectory-library planner in simulations across 100 randomly generated obstacle environments.The comparison recorded the distance traveled before collision; the trajectory-based planner selected maneuvers by nominal Euclidean obstacle clearance.Source: Figure 9 · p. 32, §7.1 · pp. 32–33

7.2 Quadrotor Model

  • The quadrotor example uses a 12-dimensional model with bounded crosswind acceleration uncertainty and a library of 20 maneuvers plus a straight-flight trim trajectory.Its funnel library is fully connected, and the trim maneuver is sequentially composable with other maneuvers modulo invariances.Source: §7.2 · pp. 34–35
  • Under the derived obstacle-geometry conditions, a collision-free funnel exists from the quadrotor’s starting position, provided its full state lies within every funnel inlet.The conditions ensure obstacles are not too close or too large and that gaps between them are wide enough and reachable by a library funnel.Source: §7.2 · pp. 35, 36, 38
  • For continuous receding-horizon flight, the analysis assumes sufficient sensor range and uses the trim maneuver to pad distance from obstacles before replanning.The sensor horizon must exceed ∆y forward and ∆x/2 sideways; trim is applied until the quadrotor is ∆y from an obstacle.Source: §7.2 · pp. 38–39
  • The quadrotor geometry analysis is a starting point: it assumes 2.5D obstacles and single-funnel planning, with extensions to 3D, funnel sequences, and stochastic obstacle locations left for future work.The paper notes that these assumptions may be varied or tightened.Source: §7.2 · pp. 35, 39

8 Hardware experiments on a fixed-wing airplane

Hardware experiments used an SBach airplane to validate funnel models and demonstrate real-time planning through obstacle environments whose geometry was revealed only after launch. The planner negotiated most tested environments, while the trials also exposed a limitation from unmodeled actuator saturation.

8.1 Hardware platform

  • The experiments used a 76.6 g SBach RC airplane, whose ailerons, rudder, elevator, and throttle were commanded at 50 Hz.The lightweight, maneuverable aircraft supported obstacle-avoidance maneuvers in a tight space.Source: §8.1 · p. 39

8.2 Task and experimental setup

  • Launched at approximately 4–5 m/s, the airplane traversed a room with obstacles revealed to the planner only after it cleared the launcher.Vicon tracked the airplane and obstacles at 120 Hz; online computation ran on an off-board computer.Source: §8.2 · p. 41

8.3 Modeling and system identification

  • The airplane model has 12 states and four control inputs, combining measured thrust and propwash with aerodynamic-force models and experimentally fitted parameters.System-identification fitting used data from 15–20 flights, each lasting approximately 0.5–0.7 seconds.Source: §8.3 · pp. 41–42

8.4 Funnel validation

  • All 30 experimental trajectories remained inside the computed 12-dimensional funnel throughout the maneuver, supporting its validity on the airplane.The funnel was computed without accounting for model uncertainty or actuator saturation; its computation took approximately one hour.Source: §8.4 · pp. 43–44

8.5 Obstacle avoidance experiments

  • The airplane successfully negotiated 14 of 15 environments; five additional flights on the bottom-right environment were all successful, demonstrating the real-time planner’s efficacy and robustness to initial conditions.Source: §8.5 · pp. 45, 48
  • QCQP-based funnel shifting enabled collision-free plans, whereas the best unshifted funnel in a comparison collided with obstacles.The ability to adjust funnels was especially important for the hoop, where a collision-free passage required a funnel nearly centered on it.Source: §8.5 · p. 48, Figure 24 · p. 50

8.6 Implementation details

  • The system filtered finite-difference motion estimates with a Luenberger observer and compensated for 55 ms of delay by simulating the model forward before computing control.The forward simulation used the estimated current state to predict the state 55 ms ahead.Source: §8.6 · p. 50

9 Discussion and Conclusion

The paper presents real-time planning in a priori unknown environments by composing precomputed funnels that bound closed-loop reachable sets under bounded model uncertainty and disturbances. It also discusses implementation challenges and directions for extending the approach.

9 Discussion and Conclusion

  • Simulations, quadrotor results, and fixed-wing hardware experiments demonstrate the method across nonlinear robotic systems and high-speed cluttered environments.The quadrotor results include conditions guaranteeing collision-free flight forever; the airplane performs aggressive maneuvers while remaining robust. The authors describe these results as among the first examples of provably safe, robust real-time control with complex nonlinear dynamics and geometric constraints.Source: §9 · pp. 50–51

9.1.1 Numerical difficulties

  • Numerical issues in semidefinite-programming solvers, including data-scaling problems, require ad hoc remedies despite recent speed improvements.The authors point to SOS/SDP preprocessing as an active research area and expect solver technology to improve as SDPs see wider adoption.Source: §9.1.1 · p. 51

9.1.2 Robots with complex geometries

  • For complex robot geometries, real-time configuration-space obstacle construction is difficult, while offline funnel inflation in x-y-z space may be more promising.The paper's examples approximated robot geometry with spheres, enabling projected funnels to be inflated by sphere radius for collision checking; extending this operation to complex shapes is not straightforward.Source: §9.1.2 · p. 51

9.1.3 Designing funnel libraries

  • Funnel-library richness trades off against online search cost, motivating faster collision-check ordering and principled ways to design sufficiently rich libraries.Submodular optimization used for trajectory-library search [Dey et al., 2012, Dey, 2015] may generalize to funnels; library design could use sampled environments, adding funnels when existing ones fail, or extend ergodic-forest analysis [Karaman and Frazzoli, 2012]. Tree locations in forests can be modeled by spatial Poisson processes.Source: §9.1.3 · pp. 51–52

9.1.4 Probabilistic guarantees

  • Because bounded uncertainty assumptions may be invalid or overly conservative, the authors propose future probabilistic guarantees for stochastic systems.They identify combining robust online planning with probabilistic finite-time invariance certificates from super-martingale theory and SOS programming as future work.Source: §9.1.4 · p. 52

9.1.5 Reasoning about perception systems

  • When perception can miss obstacles, probability-one collision avoidance is unreasonable, making probabilistic reasoning about occupancy-map uncertainty an open problem.The paper assumes runtime perception reports regions guaranteed to contain obstacles; it suggests associating occupancy probabilities with each voxel to model perceptual uncertainty.Source: §9.1.5 · p. 53

9.1.6 Real-time computation of funnels

  • More scalable DSOS/SDSOS alternatives to SOS may enable real-time funnel and controller computation, potentially eliminating offline preprocessing for low-dimensional systems.These approaches use linear and second-order cone programming and offer scalability and runtime gains over SOS [Ahmadi and Majumdar, 2016, Ahmadi and Majumdar, 2014, Majumdar et al., 2014].Source: §9.1.6 · p. 53

Related papers

Loading 1601.04037v3…