pith. sign in

arxiv: 2606.00842 · v1 · pith:OKGCT6TVnew · submitted 2026-05-30 · 📡 eess.SY · cs.SY

A Framework for Motion Planning with Temporal Logic Precedence Specifications via Augmented Graphs of Convex Sets

Shilin You , Gael Luna , Tyler H. Summers This is my paper

Pith reviewed 2026-06-28 18:12 UTC · model grok-4.3

classification 📡 eess.SY cs.SY
keywords motion planningsignal temporal logicgraph of convex setsprecedence constraintskey-door problemstrajectory optimizationconvex partitioning
0
0 comments X

The pith

An augmented graph of convex sets encodes key-door precedence logic so one shortest path yields both the optimal collection sequence and the continuous trajectory.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a planning method for trajectories that must avoid obstacles while obeying precedence rules such as collecting a key before its door can be used. It begins with an exact convex partitioning of free space that records all connectivity among free regions, keys, and doors. From this partition the authors build an augmented graph of convex sets whose layers mirror the logical ordering constraints. A single shortest-path search over the graph then chooses the best sequence of keys and simultaneously produces the corresponding optimal continuous trajectory, exact except for a finite Bézier parameterization. This matters because it folds the combinatorial choice of sequence directly into the continuous optimization rather than solving the two problems separately.

Core claim

By constructing an augmented graph of convex sets whose layered structure exactly encodes the key-door precedence logic, a shortest path in the graph simultaneously selects an optimal key collection sequence and computes an optimal continuous trajectory, providing an exact solution up to a finite Bézier curve parameterization.

What carries the argument

The augmented graph of convex sets with a layered structure that encodes the key-door precedence logic; the layers turn discrete ordering constraints into graph edges so that shortest-path search solves both sequence selection and trajectory optimization at once.

If this is right

  • The planner returns trajectories that satisfy the STL precedence constraints by construction of the graph layers.
  • Sequence selection and continuous optimization are performed jointly rather than by enumerating key orders separately.
  • The computed trajectory is optimal within the chosen Bézier curve family and the given convex partition.
  • The method applies to any environment that can be partitioned into convex sets encoding the required connectivity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The layering technique could be reused for other fragments of temporal logic that involve ordering or unlocking constraints.
  • If an automated convex-partitioning routine becomes reliable, the framework could be embedded in existing robotics pipelines for environments with conditional access regions.
  • Dynamic or uncertain door states would require the graph layers to be rebuilt or updated during execution.

Load-bearing premise

The free space admits an exact convex partitioning that fully captures connectivity among free regions, key locations, and door locations.

What would settle it

An environment whose shortest path in the augmented graph produces a trajectory that collides with an obstacle or opens a door without first collecting its key, or a feasible trajectory that the graph representation misses entirely.

Figures

Figures reproduced from arXiv: 2606.00842 by Gael Luna, Shilin You, Tyler H. Summers.

Figure 1
Figure 1. Figure 1: Overview of the proposed approach. The environment i [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A key-door environment with 2 keys and 2 doors. The [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The augmented GCS for a simple 2-key environment. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Augmented GCS layer structure for base graphs with [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (a) key-door maze, (b) graph of maze. B. Numerical Experiments on Key-Door Mazes To further evaluate the augmented GCS framework, we developed a maze benchmark generator (described in Ap￾pendix C) that produces key-door maze environments of controllable size and width [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: Log-log plot showing singly exponential growth of [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Optimal wayset solution for nK = 11. that non-zero optimality gap is typically due to the relaxation, not the rounding. Although the singly exponential scaling of our approach is far better than the doubly exponential scaling of top-down approaches for arbitrary STL formulas, these results strongly motivate the use of heuristics and pruning strategies that trade solution quality for speed. The BHK correspo… view at source ↗
Figure 9
Figure 9. Figure 9: The Legend of Zelda Eagle Dungeon (Nintendo, 1986). TABLE IV: Zelda Dungeon Experiments Rounded Trials Solve (s) δrelax (%) δ (%) 10 10.26 24.2 15.1 100 73.61 17.9 9.53 1000 713.2 11.9 3.67 substantial effort calibrating precedence structures to be non￾trivial but tractable, a regime where algorithmic methods should demonstrate clear value. Environment description: The Eagle Dungeon, shown in [PITH_FULL_I… view at source ↗
Figure 11
Figure 11. Figure 11: Augmented GCS of the Eagle Dungeon. K1 K2 K3 K4 K5 K6 t D1 D2 D3 D4 D5 D6 [PITH_FULL_IMAGE:figures/full_fig_p015_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The solid blue line shows the global optimal solutio [PITH_FULL_IMAGE:figures/full_fig_p015_12.png] view at source ↗
read the original abstract

We present a framework for planning trajectories that avoid obstacles and satisfy logical precedence constraints expressed with a fragment of signal temporal logic (STL). Our approach models environments containing obstacles, keys, and doors, where collecting a key unlocks its associated door and potentially opens shorter paths to a goal. Based on an exact convex partitioning of the free space that encodes connectivity among convex free space, key, and door regions, we construct an augmented graph of convex sets (GCS) whose layered structure exactly encodes the key-door precedence logic. A shortest path in the augmented GCS simultaneously selects an optimal key collection sequence and computes an optimal continuous trajectory, providing an exact solution up to a finite B\'ezier curve parameterization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper presents a framework for motion planning that avoids obstacles while satisfying a fragment of signal temporal logic (STL) precedence constraints in environments with keys and doors. It relies on an exact convex partitioning of free space to construct an augmented graph of convex sets (GCS) whose layered structure encodes the key-door logic; a shortest path through this graph is claimed to jointly select an optimal key-collection sequence and produce an optimal continuous trajectory, exact up to a finite Bézier parameterization.

Significance. If the exactness claims hold, the work would extend the GCS paradigm to handle logical precedence constraints exactly within a single shortest-path computation, offering a principled alternative to sampling-based or MILP-based methods for STL-constrained planning. The combination of discrete sequence selection and continuous optimization in one graph search would be a meaningful technical contribution for robotics applications involving unlockable regions.

major comments (2)
  1. [Abstract] Abstract: the central claim that 'a shortest path in the augmented GCS simultaneously selects an optimal key collection sequence and computes an optimal continuous trajectory, providing an exact solution' rests on the unproven assertion of an 'exact convex partitioning of the free space that encodes connectivity among convex free space, key, and door regions' together with an augmentation that 'exactly encodes the key-door precedence logic.' No construction procedure, completeness argument, or proof that such a partitioning exists and can be computed for arbitrary obstacle/key/door geometries is supplied, rendering the optimality guarantee unverifiable from the manuscript.
  2. [Abstract] Abstract: the manuscript supplies no validation data, numerical experiments, proofs, or implementation details to support the claimed exactness or to demonstrate that the layered augmentation embeds every feasible logical combination without over- or under-constraining the GCS edges. This absence directly undermines assessment of the soundness of the joint sequence-and-trajectory optimality result.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed review and for highlighting the need for explicit construction details and validation to support the exactness claims. We address each major comment below and will revise the manuscript accordingly to strengthen the presentation of the framework.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that 'a shortest path in the augmented GCS simultaneously selects an optimal key collection sequence and computes an optimal continuous trajectory, providing an exact solution' rests on the unproven assertion of an 'exact convex partitioning of the free space that encodes connectivity among convex free space, key, and door regions' together with an augmentation that 'exactly encodes the key-door precedence logic.' No construction procedure, completeness argument, or proof that such a partitioning exists and can be computed for arbitrary obstacle/key/door geometries is supplied, rendering the optimality guarantee unverifiable from the manuscript.

    Authors: We acknowledge that the submitted manuscript presents the partitioning as a foundational assumption without supplying an explicit construction algorithm or completeness proof in the main text. The framework is developed under the premise that environments with keys and doors admit an exact convex decomposition that preserves connectivity (consistent with prior GCS work on polyhedral decompositions). In revision we will add a dedicated section providing a constructive procedure based on visibility-graph augmentation of the free-space obstacles, key regions, and door regions, together with a proof that the resulting layered graph encodes all feasible precedence sequences without introducing spurious constraints or omitting valid ones. This will make the optimality claim directly verifiable. revision: yes

  2. Referee: [Abstract] Abstract: the manuscript supplies no validation data, numerical experiments, proofs, or implementation details to support the claimed exactness or to demonstrate that the layered augmentation embeds every feasible logical combination without over- or under-constraining the GCS edges. This absence directly undermines assessment of the soundness of the joint sequence-and-trajectory optimality result.

    Authors: The current manuscript is primarily theoretical and indeed omits numerical validation and implementation specifics. We will revise by adding a results section containing simulation experiments on multiple environments (varying numbers of keys/doors and obstacle configurations) that compare the obtained sequences and trajectories against exhaustive enumeration of feasible logical combinations. An appendix will supply the formal proof of exact encoding and details on the Bézier parameterization and shortest-path solver used. These additions will directly address the soundness assessment. revision: yes

Circularity Check

0 steps flagged

No significant circularity; framework is self-contained given external partitioning assumption

full rationale

The derivation begins from an explicitly stated external assumption (exact convex partitioning of free space encoding key-door connectivity) and then constructs an augmented GCS whose shortest-path property yields the claimed simultaneous sequence and trajectory selection. No equations or steps reduce the output to a fitted parameter, self-defined quantity, or load-bearing self-citation; the Bézier parameterization caveat is standard and does not create circularity. The partitioning step is an input precondition rather than a derived result, so the central claim remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities; no details on partitioning method, Bézier parameterization, or optimization formulation are available.

pith-pipeline@v0.9.1-grok · 5648 in / 996 out tokens · 23649 ms · 2026-06-28T18:12:04.887960+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

55 extracted references · 6 canonical work pages · 1 internal anchor

  1. [1]

    arXiv preprint arXiv:2510.22015 , year=

    S. Y ou, G. Luna, J. Shaikh, D. Gostin, Y . Xiang, J. Koeln, a nd T. Sum- mers, “Motion planning with precedence specifications via a ugmented graphs of convex sets,” arXiv preprint arXiv:2510.22015 , 2025

    work page arXiv 2025

  2. [2]

    S. M. LaV alle, Planning algorithms. Cambridge University Press, 2006

    2006

  3. [3]

    Latombe, Robot motion planning

    J.-C. Latombe, Robot motion planning . Springer Science & Business Media, 2012

    2012

  4. [4]

    Shortest paths in graphs of convex sets,

    T. Marcucci, J. Umenberger, P . Parrilo, and R. Tedrake, “ Shortest paths in graphs of convex sets,” SIAM Journal on Optimization , vol. 34, no. 1, pp. 507–532, 2024

    2024

  5. [5]

    Motion planning around obstacles with convex optimization,

    T. Marcucci, M. Petersen, D. V on Wrangel, and R. Tedrake, “Motion planning around obstacles with convex optimization,” Science robotics, vol. 8, no. 84, p. eadf7843, 2023

    2023

  6. [6]

    A unified and scalable method for optimizat ion over graphs of convex sets,

    T. Marcucci, “A unified and scalable method for optimizat ion over graphs of convex sets,” arXiv preprint arXiv:2510.20184 , 2025

    work page arXiv 2025

  7. [7]

    Temporal logic motion planning with convex optimization via graphs of convex sets,

    V . Kurtz and H. Lin, “Temporal logic motion planning with convex optimization via graphs of convex sets,” IEEE Transactions on Robotics , vol. 39, no. 5, pp. 3791–3804, 2023

    2023

  8. [8]

    Dynamic programming treatment of the trave lling sales- man problem,

    R. Bellman, “Dynamic programming treatment of the trave lling sales- man problem,” Journal of the ACM (JACM) , vol. 9, no. 1, pp. 61–63, 1962

    1962

  9. [9]

    A dynamic programming approach to sequencing problems,

    M. Held and R. M. Karp, “A dynamic programming approach to sequencing problems,” Journal of the Society for Industrial and Applied mathematics, vol. 10, no. 1, pp. 196–210, 1962

    1962

  10. [10]

    Randomized kinodyna mic planning,

    S. M. LaV alle and J. J. Kuffner Jr, “Randomized kinodyna mic planning,” The international journal of robotics research , vol. 20, no. 5, pp. 378– 400, 2001

    2001

  11. [11]

    Sampling-based algorithm s for optimal motion planning,

    S. Karaman and E. Frazzoli, “Sampling-based algorithm s for optimal motion planning,” The international journal of robotics research, vol. 30, no. 7, pp. 846–894, 2011

    2011

  12. [12]

    Prob- abilistic roadmaps for path planning in high-dimensional c onfiguration spaces,

    L. E. Kavraki, P . Svestka, J.-C. Latombe, and M. H. Overm ars, “Prob- abilistic roadmaps for path planning in high-dimensional c onfiguration spaces,” IEEE transactions on Robotics and Automation , vol. 12, no. 4, pp. 566–580, 2002

    2002

  13. [13]

    Canny, The complexity of robot motion planning

    J. Canny, The complexity of robot motion planning . MIT press, 1988

    1988

  14. [14]

    Chomp: Gradient optimization techniques for efficient motion planning,

    N. Ratliff, M. Zucker, J. A. Bagnell, and S. Srinivasa, “ Chomp: Gradient optimization techniques for efficient motion planning,” in 2009 IEEE international conference on robotics and automation . IEEE, 2009, pp. 489–494

    2009

  15. [15]

    Chomp: Cova riant hamiltonian optimization for motion planning,

    M. Zucker, N. Ratliff, A. D. Dragan, M. Pivtoraiko, M. Kl ingensmith, C. M. Dellin, J. A. Bagnell, and S. S. Srinivasa, “Chomp: Cova riant hamiltonian optimization for motion planning,” The International jour- nal of robotics research , vol. 32, no. 9-10, pp. 1164–1193, 2013

    2013

  16. [16]

    Finding locally optimal, collision-free trajectories wi th sequential con- vex optimization

    J. Schulman, J. Ho, A. X. Lee, I. Awwal, H. Bradlow, and P . Abbeel, “Finding locally optimal, collision-free trajectories wi th sequential con- vex optimization.” in Robotics: science and systems , vol. 9, no. 1. Berlin, Germany, 2013, pp. 1–10

    2013

  17. [17]

    J. T. Betts, Practical methods for optimal control and estimation using nonlinear programming. SIAM, 2010

    2010

  18. [18]

    arXiv preprint arXiv:2409.19543 , year=

    S. Morozov, T. Marcucci, A. Amice, B. P . Graesdal, R. Bos worth, P . A. Parrilo, and R. Tedrake, “Multi-query shortest-path probl em in graphs of convex sets,” arXiv preprint arXiv:2409.19543 , 2024

    work page arXiv 2024

  19. [19]

    arXiv preprint arXiv:2402.10312 , year=

    B. P . Graesdal, S. Y . C. Chia, T. Marcucci, S. Morozov, A. Amice, P . A. Parrilo, and R. Tedrake, “Towards tight convex relaxations for contact- rich manipulation,” arXiv preprint arXiv:2402.10312 , 2024

    work page arXiv 2024

  20. [20]

    No n-euclidean motion planning with graphs of geodesically convex sets,

    T. Cohn, M. Petersen, M. Simchowitz, and R. Tedrake, “No n-euclidean motion planning with graphs of geodesically convex sets,” The Interna- tional Journal of Robotics Research , vol. 44, no. 10-11, pp. 1840–1862, 2025

    2025

  21. [21]

    Impl icit graph search for planning on graphs of convex sets,

    R. Natarajan, C. Liu, H. Choset, and M. Likhachev, “Impl icit graph search for planning on graphs of convex sets,” arXiv preprint arXiv:2410.08909, 2024

    work page arXiv 2024

  22. [22]

    Augmented Graphs of Convex Sets and the Traveling Salesman Problem

    G. Luna and T. Summers, “Augmented graphs of convex sets and the traveling salesman problem,” arXiv preprint arXiv:2604.06406 , 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  23. [23]

    A mixed -integer conic program for the moving-target traveling salesman pro blem based on a graph of convex sets,

    A. G. Philip, Z. Ren, S. Rathinam, and H. Choset, “A mixed -integer conic program for the moving-target traveling salesman pro blem based on a graph of convex sets,” in 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) . IEEE, 2024, pp. 8847–8853

    2024

  24. [24]

    Baier and J.-P

    C. Baier and J.-P . Katoen, Principles of model checking . MIT press, 2008

    2008

  25. [25]

    Temporal logic motion planning for dynamic robots,

    G. E. Fainekos, A. Girard, H. Kress-Gazit, and G. J. Papp as, “Temporal logic motion planning for dynamic robots,” Automatica, vol. 45, no. 2, pp. 343–352, 2009

    2009

  26. [26]

    Tempo ral-logic-based reactive mission and motion planning,

    H. Kress-Gazit, G. E. Fainekos, and G. J. Pappas, “Tempo ral-logic-based reactive mission and motion planning,” IEEE transactions on robotics , vol. 25, no. 6, pp. 1370–1381, 2009

    2009

  27. [27]

    Temporal logic motion planning and control with probabilistic satisfaction guar antees,

    M. Lahijanian, S. B. Andersson, and C. Belta, “Temporal logic motion planning and control with probabilistic satisfaction guar antees,” IEEE Transactions on Robotics , vol. 28, no. 2, pp. 396–409, 2011

    2011

  28. [28]

    Motion planning with temporal -logic spec- ifications: Progress and challenges,

    E. Plaku and S. Karaman, “Motion planning with temporal -logic spec- ifications: Progress and challenges,” AI communications, vol. 29, no. 1, pp. 151–162, 2015

    2015

  29. [29]

    Belta, B

    C. Belta, B. Y ordanov, and E. A. Gol, F ormal methods for discrete-time dynamical systems . Springer, 2017, vol. 89

    2017

  30. [30]

    Optimization-b ased trajec- tory generation with linear temporal logic specifications,

    E. M. Wolff, U. Topcu, and R. M. Murray, “Optimization-b ased trajec- tory generation with linear temporal logic specifications, ” in 2014 IEEE International Conference on Robotics and Automation (ICRA ). IEEE, 2014, pp. 5319–5325

    2014

  31. [31]

    Linear temporal l ogic motion planning for teams of underactuated robots using sat isfiability modulo convex programming,

    Y . Shoukry, P . Nuzzo, A. Balkan, I. Saha, A. L. Sangiovan ni-Vincentelli, S. A. Seshia, G. J. Pappas, and P . Tabuada, “Linear temporal l ogic motion planning for teams of underactuated robots using sat isfiability modulo convex programming,” in 2017 IEEE 56th annual conference on decision and control (CDC) . IEEE, 2017, pp. 1132–1137

    2017

  32. [32]

    Control barrier fu nctions for signal temporal logic tasks,

    L. Lindemann and D. V . Dimarogonas, “Control barrier fu nctions for signal temporal logic tasks,” IEEE control systems letters , vol. 3, no. 1, pp. 96–101, 2018

    2018

  33. [33]

    Barrier function based collaborative control of m ultiple robots under signal temporal logic tasks,

    ——, “Barrier function based collaborative control of m ultiple robots under signal temporal logic tasks,” IEEE Transactions on Control of Network Systems , vol. 7, no. 4, pp. 1916–1928, 2020

    1916

  34. [34]

    Monitoring temporal propert ies of con- tinuous signals,

    O. Maler and D. Nickovic, “Monitoring temporal propert ies of con- tinuous signals,” in International symposium on formal techniques in real-time and fault-tolerant systems . Springer, 2004, pp. 152–166

    2004

  35. [35]

    Robust satisfaction of tempora l logic over real-valued signals,

    A. Donz´ e and O. Maler, “Robust satisfaction of tempora l logic over real-valued signals,” in International conference on formal modeling and analysis of timed systems . Springer, 2010, pp. 92–106

    2010

  36. [36]

    Control design for risk-based signal temporal lo gic specifi- cations,

    S. Safaoui, L. Lindemann, D. V . Dimarogonas, I. Shames, and T. H. Summers, “Control design for risk-based signal temporal lo gic specifi- cations,” IEEE Control Systems Letters , vol. 4, no. 4, pp. 1000–1005, 2020

    2020

  37. [37]

    Integrated task and motion planning ,

    C. R. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver , L. P . Kaelbling, and T. Lozano-P´ erez, “Integrated task and motion planning ,” Annual review of control, robotics, and autonomous systems , vol. 4, no. 1, pp. 265–293, 2021

    2021

  38. [38]

    A hybrid approach to intricate motion, manipulation and task planning,

    S. Cambon, R. Alami, and F. Gravot, “A hybrid approach to intricate motion, manipulation and task planning,” The International Journal of Robotics Research, vol. 28, no. 1, pp. 104–126, 2009

    2009

  39. [39]

    Hierarchical ta sk and motion planning in the now,

    L. P . Kaelbling and T. Lozano-P´ erez, “Hierarchical ta sk and motion planning in the now,” in 2011 IEEE international conference on robotics and automation . IEEE, 2011, pp. 1470–1477

    2011

  40. [40]

    Integrated task and motion planning in belief spac e,

    ——, “Integrated task and motion planning in belief spac e,” The International Journal of Robotics Research , vol. 32, no. 9-10, pp. 1194– 1227, 2013. 18

    2013

  41. [41]

    Logic-geometric programming: An optim ization-based approach to combined task and motion planning

    M. Toussaint, “Logic-geometric programming: An optim ization-based approach to combined task and motion planning.” in IJCAI, 2015, pp. 1930–1936

    2015

  42. [42]

    The traveling salesman problem: a computational study,

    D. L. Applegate, R. E. Bixby, V . Chv´ atal, and W. J. Cook, “The traveling salesman problem: a computational study,” in The traveling salesman problem. Princeton university press, 2011

    2011

  43. [43]

    The vehicle routing problem: An overview o f exact and approximate algorithms,

    G. Laporte, “The vehicle routing problem: An overview o f exact and approximate algorithms,” European journal of operational research , vol. 59, no. 3, pp. 345–358, 1992

    1992

  44. [44]

    Approximation algor ithms for tsp with neighborhoods in the plane,

    A. Dumitrescu and J. S. Mitchell, “Approximation algor ithms for tsp with neighborhoods in the plane,” Journal of Algorithms , vol. 48, no. 1, pp. 135–159, 2003

    2003

  45. [45]

    On the dubins travelin g salesman problem,

    J. Ny, E. Feron, and E. Frazzoli, “On the dubins travelin g salesman problem,” IEEE Transactions on Automatic Control , vol. 57, no. 1, pp. 265–270, 2011

    2011

  46. [46]

    Traveling salespe rson problems for the dubins vehicle,

    K. Savla, E. Frazzoli, and F. Bullo, “Traveling salespe rson problems for the dubins vehicle,” IEEE Transactions on Automatic Control , vol. 53, no. 6, pp. 1378–1391, 2008

    2008

  47. [47]

    A survey on coverage path p lanning for robotics,

    E. Galceran and M. Carreras, “A survey on coverage path p lanning for robotics,” Robotics and Autonomous systems , vol. 61, no. 12, pp. 1258– 1276, 2013

    2013

  48. [48]

    Linear-time algorithms for visibility and shortest path p roblems inside triangulated simple polygons,

    L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan, “Linear-time algorithms for visibility and shortest path p roblems inside triangulated simple polygons,” Algorithmica, vol. 2, no. 1, pp. 209–233, 1987

    1987

  49. [49]

    Optimal complex ity reduction of polyhedral piecewise affine systems,

    T. Geyer, F. D. Torrisi, and M. Morari, “Optimal complex ity reduction of polyhedral piecewise affine systems,” Automatica, vol. 44, no. 7, pp. 1728–1740, 2008

    2008

  50. [50]

    Reverse search for enumeration,

    D. Avis and K. Fukuda, “Reverse search for enumeration, ” Discrete applied mathematics , vol. 65, no. 1-3, pp. 21–46, 1996

    1996

  51. [51]

    Partition of space,

    R. C. Buck, “Partition of space,” The American Mathematical Monthly , vol. 50, no. 9, pp. 541–544, 1943

    1943

  52. [52]

    Exact obstacle-f ree space repre- sentation using hybrid zonotopes,

    J. Shaikh, D. Gostin, and J. P . Koeln, “Exact obstacle-f ree space repre- sentation using hybrid zonotopes,” in 2025 American Control Conference (ACC). IEEE, 2025, pp. 2522–2529

    2025

  53. [53]

    V ersion 11.0

    MOSEK, The MOSEK Python Fusion API manual. V ersion 11.0. , 2025. [Online]. Available: https://docs.mosek.com/latest/py thonfusion/index.h tml

    2025

  54. [54]

    Drake: Mode l-based design and verification for robotics,

    R. Tedrake and the Drake Development Team, “Drake: Mode l-based design and verification for robotics,” 2019. [Online]. Avai lable: https://drake.mit.edu

    2019

  55. [55]

    Buck, Mazes for Programmers: Code Your Own Twisty Little Passages

    J. Buck, Mazes for Programmers: Code Your Own Twisty Little Passages. Pragmatic Bookshelf, 2015. APPENDIX A PROOFS OF OPTIMALITY LEMMAS Proof of Lemma 1 (Soundness) We show that any path ˆp in ˆG from start node s to the merged target node t satisfies ⋀nK i=1(KiR¬ Di)∧F (T ). T erminal condition. The target node t is the merge of all its copies across all ...

    2015