A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets

• URL: http://arxiv.org/abs/2403.04917v3
• Date: Mon, 13 Jan 2025 20:28:04 GMT
• Title: A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets
• Abstract summary: This paper introduces a new formulation that finds the optimum for the Moving-Target Traveling Salesman Problem (MT-TSP)<n>The problem seeks to find a shortest path for an agent, that starts at a depot, visits a set of moving targets exactly once within their assigned time-windows, and returns to the depot.<n>We compare our formulation with the current state-of-the-art Mixed Conic Program (MICP) solver for the MT-TSP.
• Score: 27.63278352602436
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces a new formulation that finds the optimum for the Moving-Target Traveling Salesman Problem (MT-TSP), which seeks to find a shortest path for an agent, that starts at a depot, visits a set of moving targets exactly once within their assigned time-windows, and returns to the depot. The formulation relies on the key idea that when the targets move along lines, their trajectories become convex sets within the space-time coordinate system. The problem then reduces to finding the shortest path within a graph of convex sets, subject to some speed constraints. We compare our formulation with the current state-of-the-art Mixed Integer Conic Program (MICP) solver for the MT-TSP. The experimental results show that our formulation outperforms the MICP for instances with up to 20 targets, with up to two orders of magnitude reduction in runtime, and up to a 60\% tighter optimality gap. We also show that the solution cost from the convex relaxation of our formulation provides significantly tighter lower bounds for the MT-TSP than the ones from the MICP.

Related papers

• Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles [49.315843050082925]
  We present a bi approach for minimum-time motion planning convex obstacles that is guaranteed to converge.<n>We find that the proposed method produces high-quality trajectories with times to produce state-of-the-art decomposition of variables.
  arXiv  Detail & Related papers  (2026-08-03T19:48:24Z)
• Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles [20.81107528768337]
  We study the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO)<n>We present a Mixed-Integer Conic Programming (MICP) formulation that can be solved using off-the-shelf solvers, as well as a fast and scalable Two-Phase Bilevel Search (TPBS) algorithm.<n>We evaluate our approaches against an existing baseline algorithm on a broad range of problem instances with up to 40 targets and 40 obstacles.
  arXiv  Detail & Related papers  (2026-06-17T06:17:12Z)
• Semidefinite Relaxations for Collision-Free Motion Planning [53.160637667144876]
  We focus on a point robot moving from start to goal through inmathbbRn constraints in terms of $C4 trajectories.<n>We demonstrate its effectiveness as a planner for minimum-snap continuous planning with $C4 trajectories.
  arXiv  Detail & Related papers  (2026-06-12T03:18:03Z)
• Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity [24.447439182269974]
  The Moving Target Vehicle Routing Problem (MT-VRP) seeks trajectories for several agents that intercept a set of moving targets.<n>We introduce an exact algorithm, Branch-and-Price with Relaxed Continuity (BPRC), for the MT-VRP.<n>We show that our algorithm finds optimal solutions more than an order of magnitude faster than a baseline based on previous work.
  arXiv  Detail & Related papers  (2026-02-28T14:09:54Z)
• Assignment-Routing Optimization: Solvers for Problems Under Constraints [0.0]
  We study the Joint Routing-Assignment (JRA) problem in which items must be assigned one-to-one to placeholders.<n>We develop a solver tailored for practical packaging-planning scenarios with richer constraints.<n>Results highlight the practical applicability of MIP-based JRA optimization for robotic packaging, motion planning, and complex logistics.
  arXiv  Detail & Related papers  (2025-12-21T06:32:31Z)
• FraPPE: Fast and Efficient Preference-based Pure Exploration [17.53646399595373]
  We propose an efficient algorithm to optimally track the existing lower bound for arbitrary preference cones.<n>We prove that our proposed PrePEx algorithm, FraPPE, achieves the optimal sample complexity.
  arXiv  Detail & Related papers  (2025-08-22T16:02:06Z)
• Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning [2.3416394753138037]
  Multi-Robot Motion Planning (MRMP) is a problem of computing problem of collision-free trajectories for multiple robots in continuous environments. We propose Space-Time Graphs of Convex Sets (ST-GCS), a novel planner that systematically covers the collision-free space-time domain with convex sets instead of relying on random sampling. We also propose Convex Decomposition (ECD) to "reserve" trajectories astemporal obstacles, addressing maintaining a collision-free space-time graph sets for subsequent planning.
  arXiv  Detail & Related papers  (2025-03-01T18:28:57Z)
• Dataless Quadratic Neural Networks for the Maximum Independent Set Problem [23.643727259409744]
  We show that pCQO-MIS scales with only the number of nodes in the graph not the number of edges. Our method avoids out-of-distribution, sampling, and data-centric approaches.
  arXiv  Detail & Related papers  (2024-06-27T21:12:48Z)
• SPARE: Symmetrized Point-to-Plane Distance for Robust Non-Rigid Registration [76.40993825836222]
  We propose SPARE, a novel formulation that utilizes a symmetrized point-to-plane distance for robust non-rigid registration. The proposed method greatly improves the accuracy of non-rigid registration problems and maintains relatively high solution efficiency.
  arXiv  Detail & Related papers  (2024-05-30T15:55:04Z)
• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  We prove an $mathcalO(t-1)$ lower bound rate for the OT map, using the similarity between Laguerre cells estimation and density support estimation. To nearly achieve the desired fast rate, we design an entropic regularization scheme decreasing with the number of samples.
  arXiv  Detail & Related papers  (2024-05-23T11:46:03Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• The Parameterized Complexity of Coordinated Motion Planning [28.39902924923273]
  In Coordinated Motion Planning (CMP), $k$ robots occupy $k$ distinct starting gridpoints and need to reach $k$ distinct destination gridpoints. The goal is to compute a schedule for moving the $k$ robots to their destinations which minimizes a certain objective target. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters.
  arXiv  Detail & Related papers  (2023-12-12T10:26:01Z)
• Vanishing Point Estimation in Uncalibrated Images with Prior Gravity Direction [82.72686460985297]
  We tackle the problem of estimating a Manhattan frame. We derive two new 2-line solvers, one of which does not suffer from singularities affecting existing solvers. We also design a new non-minimal method, running on an arbitrary number of lines, to boost the performance in local optimization.
  arXiv  Detail & Related papers  (2023-08-21T13:03:25Z)
• Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning [4.521119623956821]
  We propose a methodology to accelerate the solution of mixed-integer linear two-stage programs. We aim at solving problems where the second stage is highly demanding. Our core idea is to gain large reductions in online solution time while incurring small reductions in first-stage solution accuracy.
  arXiv  Detail & Related papers  (2022-05-02T13:15:32Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  We resolve the min-max complexity of distributed convex optimization (up to a log factor) in the intermittent communication setting. We present a novel lower bound with a matching upper bound that establishes an optimal algorithm.
  arXiv  Detail & Related papers  (2021-02-02T16:18:29Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error. Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
  arXiv  Detail & Related papers  (2020-07-02T16:02:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.