TL;DR: Logic Network Flow (LNF) is a novel formulation for temporal logic specifications with provably tighter convex relaxations and fewer constraints than standard Logic Tree approaches, achieved by projecting Graph-of-Convex-Sets onto lower-dimensional spaces using Fourier-Motzkin elimination.
This paper proposes an optimization-based task and motion planning framework, named ``Logic Network Flow" (LNF), to integrate temporal logic specifications into efficient mixed-integer programs. Inspired by the Graph-of-Convex-Sets (GCS) formulation, temporal predicates are encoded as polyhedron constraints on each edge of a network flow model, instead of as constraints between nodes as in traditional Logic Tree formulations. We further propose a network-flow-based Fourier-Motzkin elimination procedure that removes continuous flow variables while preserving convex relaxation tightness, effectively projecting the GCS formulation onto a lower-dimensional space with fewer variables and constraints. For our temporal logic motion planning formulation, this projection leads to provably tighter convex relaxations and fewer constraints than Logic Tree approaches, when synthesized with various piecewise-affine (PWA) dynamic system formulations. Comprehensive experiments across vehicle routing, multi-robot coordination, and temporal logic control on dynamical systems using point mass and linear inverted pendulum models demonstrate up to orders of magnitude computational speedups, due to more efficient branch-and-bound processes. Hardware demonstrations with quadrupedal robots validate real-time replanning capabilities under dynamic environmental conditions.
Three bipedal robots coordinate to execute search and rescue operations, equipment retrieval, and fire extinguishing tasks in a disaster zone.
Optimized footstep planning for bipedal walking robots using temporal logic specifications with safe contact regions.
Three robots follow conflict-free trajectories to complete tasks across multiple rooms, demonstrating efficient path planning and scheduling.
A quadruped robot is physically dragged off course and encounters a new obstacle. It dynamically replans under temporal logic to reach an alternative feasible target.
@article{}