AIob Lab

We formalize the Steiner Traveling Salesman Problem (Steiner-TSP) on Graphs of Convex Sets (GCS), which seeks a minimum-cost closed trajectory through required convex sets while allowing optional transit vertices and revisits. To explore the resulting infinite solution space, we propose a unified branch-and-bound search over rooted walk prefixes. Additive lower-bound-graph costs bound committed prefixes, while a cut-separated connected-flow relaxation lower-bounds the residual cost of visiting every remaining target and returning to the root. Under a uniform positive-cost assumption, best-first traversal terminates after finitely many expansions on every feasible instance without an initial incumbent, whereas depth-first traversal does so once a finite incumbent is available. For a user-specified factor ϵ≥1, a global lower bound certifies that either strategy’s incumbent cost is at most ϵ times the global optimum. We further demonstrate joint sensing-mode, visitation-order, and continuous-trajectory selection for a mobile-manipulator inspection task, including action precedences expressed in linear temporal logic over finite traces (LTLf). Both traversal strategies find feasible solutions on all benchmark instances within 30\,\mathrms with mean certified optimality gaps of 28.1% and 29.7%, respectively, whereas two recent baselines succeed on only about half of the instances.

Spatiotemporal motion planning, especially in multi-robot settings, requires robots to reason about collision-free regions that change over time, which is challenging in continuous spaces when feasible regions are transient and geometrically constrained. We present an algorithmic framework based on graphs of space-time convex sets (ST-GCSs), where collision-free regions are represented as convex sets in space-time and trajectories correspond to paths on the graph together with continuous motions within the selected sets. We formulate time-optimal planning on ST-GCSs as a graph-search problem over path-indexed states and develop a best-first search solver that evaluates partial paths via continuous trajectory optimization, guided by admissible heuristics and dominance checks. We further present an Exact Convex Decomposition (ECD) scheme to reserve trajectory occupancies in space-time, enabling unified handling of dynamic obstacles and multi-robot interactions. For multi-robot motion planning, we integrate ST-GCS planning and ECD into prioritized planning methods and introduce a windowed coordination scheme to improve efficiency. Extensive experiments on single-robot and multi-robot problems demonstrate substantial speedups over various planners while maintaining high solution quality, particularly in environments with narrow and transient feasible regions. Large-scale demonstrations further show that the proposed multi-robot motion planner can solve instances with up to 100 robots within only a few minutes. Project homepage: https://sites.google.com/view/stgcs.

Combinatorial Route Optimization (CRO) problems, such as the Vehicle Routing Problem (VRP) or the Travelling Salesman Problem (TSP), are commonly seen in scheduling, logistics, and transportation. While current machine learning (ML) methods can overcome certain limitations of traditional approaches, including exact and heuristic algorithms, they typically require substantial computational resources, large training datasets, and carefully designed models, thereby limiting their scalability and practical deployment. In this paper, we develop a method to address such concerns in a data-efficient and near-training-free manner using foundation models. We select TSP, one of the most well-known combinatorial optimization problems, to solve in our experiments and employ the Tabular Prior-Data Fitted Network (TabPFN), one of the newly designed foundation models. Specifically, we develop a node-based formulation that converts TSP into a sequence of localized prediction tasks and constructs a complete route through in-context learning provided by TabPFN. The proposed method enables TabPFN, a model developed for regression and classification, to be applied to CRO problems with only one TSP sample for fine-tuning. We evaluate the proposed method across varying TSP instance sizes and demonstrate that our approach generalizes effectively without retraining, maintains competitive solution quality, and exhibits promising scalability. These findings suggest that CRO problems can be approached through foundation models, enabling scalability as well as generating rapidly deployable solutions with near-training-free adaptation.

Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD) models the multi-robot shelf rearrangement problem in automated warehouses. MAPF-DECOMP is a recent framework that first computes collision-free shelf trajectories with a MAPF solver and then assigns agents to execute them. While efficient, it enforces strict trajectory dependencies, often leading to poor execution quality due to idle agents and unnecessary shelf switching. We introduce CREST, a new execution framework that achieves more continuous shelf carrying by proactively releasing trajectory constraints during execution. Experiments on diverse warehouse layouts show that CREST consistently outperforms MAPF-DECOMP, reducing metrics related to agent travel, makespan, and shelf switching by up to 40.5%, 33.3%, and 44.4%, respectively, with even greater benefits under lift/place overhead. These results underscore the importance of execution-aware constraint release for scalable warehouse rearrangement. Code and data are available at https://github.com/ChristinaTan0704/CREST.