Author name cluster

Sivakumar Rathinam

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

2 author rows

ICRA Conference 2025 Conference Paper

A Complete and Bounded-Suboptimal Algorithm for a Moving Target Traveling Salesman Problem with Obstacles in 3D

Anoop Bhat
Geordan Gutow
Bhaskar Vundurthy
Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

The moving target traveling salesman problem with obstacles (MT-TSP-O) seeks an obstacle-free trajectory for an agent that intercepts a given set of moving targets, each within specified time windows, and returns to the agent's starting position. Each target moves with a constant velocity within its time windows, and the agent has a speed limit no smaller than any target's speed. We present FMC*-TSP, the first complete and bounded-suboptimal algorithm for the MT-TSP-O, and results for an agent whose configuration space is $\mathbb{R}^{3}$. Our algorithm interleaves a high-level search and a lowlevel search, where the high-level search solves a generalized traveling salesman problem with time windows (GTSP-TW) to find a sequence of targets and corresponding time windows for the agent to visit. Given such a sequence, the low-level search then finds an associated agent trajectory. To solve the low-level planning problem, we develop a new algorithm called FMC*, which finds a shortest path on a graph of convex sets (GCS) via implicit graph search and pruning techniques specialized for problems with moving targets. We test FMC*-TSP on 280 problem instances with up to 40 targets and demonstrate its smaller median runtime than a baseline based on prior work.

Details

AIJ Journal 2025 Journal Article

EMOA*: A framework for search-based multi-objective path planning

Zhongqiang Ren
Carlos Hernández
Maxim Likhachev
Ariel Felner
Sven Koenig
Oren Salzman
Sivakumar Rathinam
Howie Choset

In the Multi-Objective Shortest Path Problem (MO-SPP), one has to find paths on a graph that simultaneously minimize multiple objectives. It is not guaranteed that there exists a path that minimizes all objectives, and the problem thus aims to find the set of Pareto-optimal paths from the start to the goal vertex. A variety of multi-objective A*-based search approaches have been developed for this purpose. Typically, these approaches maintain a front set at each vertex during the search process to keep track of the Pareto-optimal paths that reach that vertex. Maintaining these front sets becomes burdensome and often slows down the search when there are many Pareto-optimal paths. In this article, we first introduce a framework for MO-SPP with the key procedures related to the front sets abstracted and highlighted, which provides a novel perspective for understanding the existing multi-objective A*-based search algorithms. Within this framework, we develop two different, yet closely related approaches to maintain these front sets efficiently during the search. We show that our approaches can find all cost-unique Pareto-optimal paths, and analyze their runtime complexity. We implement the approaches and compare them against baselines using instances with three, four and five objectives. Our experimental results show that our approaches run up to an order of magnitude faster than the baselines.

Details DOI

IROS Conference 2024 Conference Paper

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

Allen George Philip
Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

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) formulation 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.

Details

ICAPS Conference 2023 Conference Paper

Binary Branching Multi-Objective Conflict-Based Search for Multi-Agent Path Finding

Zhongqiang Ren
Jiaoyang Li 0001
Han Zhang 0018
Sven Koenig
Sivakumar Rathinam
Howie Choset

This paper considers a multi-agent multi-objective path-finding problem that requires not only finding collision-free paths for multiple agents from their respective start locations to their respective goal locations but also optimizing multiple objectives simultaneously. In general, there is no single solution that optimizes all the objectives simultaneously, and the problem is thus to find the so-called Pareto-optimal frontier. To solve this problem, an algorithm called Multi-Objective Conflict-Based Search (MO-CBS) was recently developed and is guaranteed to find the exact Pareto-optimal frontier. However, MO-CBS does not scale well with the number of agents due to the large branching factor of the search, which leads to a lot of duplicated effort in agent-agent collision resolution. This paper therefore develops a new algorithm called Binary Branching MO-CBS (BB-MO-CBS) that reduces the branching factor as well as the duplicated collision resolution during the search, which expedites the search as a result. Our experimental results show that BB-MO-CBS reduces the number of conflicts by up to two orders of magnitude and often doubles or triples the success rates of MO-CBS on various maps given a runtime limit.

Details

ICRA Conference 2023 Conference Paper

Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding

Zhongqiang Ren
Chaoran Zhang
Sivakumar Rathinam
Howie Choset

Multi-Agent Path Finding (MA-PF) computes a set of collision-free paths for multiple agents from their respective starting locations to destinations. This paper considers a generalization of MA-PF called Multi-Agent Teamwise Cooperative Path Finding (MA-TC-PF), where agents are grouped as multiple teams and each team has its own objective to be minimized. For example, an objective can be the sum or max of individual arrival times of the agents. In general, there is more than one team, and MA-TC-PF is thus a multi-objective planning problem with the goal of finding the entire Pareto-optimal front that represents all possible trade-offs among the objectives of the teams. To solve MA-TC-PF, we propose two algorithms TC-CBS and TC-M*, which leverage the existing CBS and M* for conventional MA-PF. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front. We present numerical results for several types of MA-TC-PF problems.

Details

SoCS Conference 2023 Conference Paper

Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding [Extended Abstract]

Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

Multi-Agent Path Finding (MA-PF) finds collision-free paths for multiple agents from their respective start to goal locations. This paper investigates a generalization of MA-PF called Multi-Agent Teamwise Cooperative Path Finding (MA-TC-PF), where agents are grouped as multiple teams and each team has its own objective to minimize. In general, there is more than one team, and MA-TC-PF is thus a multi-objective planning problem with the goal of finding the entire Pareto-optimal front that represents all possible trade-offs among the objectives of the teams. We show that the existing CBS and M* for MA-PF can be modified to solve MA-TC-PF, which is verified with tests. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front for MA-TC-PF.

Details

SoCS Conference 2022 Conference Paper

Enhanced Multi-Objective A* Using Balanced Binary Search Trees

Zhongqiang Ren
Richard Zhan
Sivakumar Rathinam
Maxim Likhachev
Howie Choset

This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a graph where the goal is to find a set of Pareto-optimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MO-SPP in the literature. Typically, these approaches maintain a "frontier" set at each node during the search process to keep track of the non-dominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Pareto-optimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Pareto-optimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude.

Details

SoCS Conference 2022 Conference Paper

Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions (Extended Abstract)

Nikhil Chandak
Kenny Chour
Sivakumar Rathinam
R. Ravi 0001

We interleave sampling based motion planning methods with pruning ideas from minimum spanning tree algorithms to develop a new approach for solving a Multi-Goal Path Finding (MGPF) problem in high dimensional spaces. The approach alternates between sampling points from selected regions in the search space and de-emphasizing regions that may not lead to good solutions for MGPF. Our approach provides an asymptotic, 2-approximation guarantee for MGPF. We also present extensive numerical results to illustrate the advantages of our proposed approach over uniform sampling in terms of the quality of the solutions found and computation speed.

Details

ICRA Conference 2021 Conference Paper

An Approximation Algorithm for an Assisted Shortest Path Problem

Christopher Montez
Sivakumar Rathinam
Swaroop Darbha
David W. Casbeer
Satyanarayana G. Manyam

In this article, we introduce a cooperative path planning algorithm for a cardinal and a support robot where the cardinal robot is unable to traverse a subset of edges in a network until the support robot has first traversed them. This subset of edges represent paths in an environment that are initially unavailable to the cardinal robot and require the assistance of the support robot. A (2 + α)-approximation algorithm (where α is the supremum of the ratio of the travel time of the support robot versus the travel time of the cardinal robot) is presented for this problem and is applied to various types of networks in order to examine the quality of the solutions it produces. We then conclude by discussing some potential future work concerning variations of this problem.

Details

IROS Conference 2021 Conference Paper

Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions

Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

Multi-agent path finding (MAPF) determines an ensemble of collision-free paths for multiple agents between their respective start and goal locations. Among the available MAPF planners for workspace modeled as a graph, A*-based approaches have been widely investigated due to their guarantees on completeness and solution optimality, and have demonstrated their efficiency in many scenarios. However, almost all of these A*-based methods assume that each agent executes an action concurrently in that all agents start and stop together. This article presents a natural generalization of MAPF with asynchronous actions (MAPF-AA) where agents do not necessarily start and stop concurrently. The main contribution of the work is a proposed approach called Loosely Synchronized Search (LSS) that extends A*-based MAPF planners to handle asynchronous actions. We show LSS is complete and finds an optimal solution if one exists. We also combine LSS with other existing MAPF methods that aims to trade-off optimality for computational efficiency. Numerical results are presented to corroborate the performance of LSS and the applicability of the proposed method is verified in the Robotarium, a remotely accessible swarm robotics research platform.

Details

ICRA Conference 2021 Conference Paper

MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding

Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

In multi-agent applications such as surveillance and logistics, fleets of mobile agents are often expected to coordinate and safely visit a large number of goal locations as efficiently as possible. The multi-agent planning problem in these applications involves allocating and sequencing goals for each agent while simultaneously producing conflict-free paths for the agents. In this article, we introduce a new algorithm called MS* which computes an optimal solution for this multi-agent problem by fusing and advancing state of the art solvers for multi-agent path finding (MAPF) and multiple travelling salesman problem (mTSP). MS* leverages our prior subdimensional expansion approach for MAPF and embeds the mTSP solvers to optimally allocate and sequence goals for agents. Numerical results show that our new algorithm can solve the multi-agent problem with 20 agents and 50 goals in a minute of CPU time on a standard laptop.

Details

ICRA Conference 2021 Conference Paper

Multi-objective Conflict-based Search for Multi-agent Path Finding

Zhongqiang Ren
Sivakumar Rathinam
Howie Choset

Conventional multi-agent path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. However, many applications may require multiple objectives, say fuel consumption and completion time, to be simultaneously optimized during planning and these criteria may not be readily compared and sometimes lie in competition with each other. Naively applying existing multi-objective search algorithms to multi-agent path finding may prove to be inefficient as the size of the space of possible solutions, i. e. , the Pareto-optimal set, can grow exponentially with the number of agents (the dimension of the search space). This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality by leveraging prior Conflict-based Search (CBS), a well-known algorithm for single-objective multi-agent path finding, and principles of dominance from multi-objective optimization literature. We prove that MO-CBS is able to compute the entire Pareto-optimal set. Our results show that MO-CBS can solve problem instances with hundreds of Pareto-optimal solutions which the standard multi-objective A* algorithms could not find within a bounded time.

Details

ICAPS Conference 2021 Conference Paper

S*: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding

Kenny Chour
Sivakumar Rathinam
Ramamoorthi Ravi

We combine ideas from uni-directional and bi-directional heuristic search, and approximation algorithms for the Traveling Salesman Problem, to develop a novel framework for a Multi-Goal Path Finding (MGPF) problem that provides a 2-approximation guarantee. MGPF aims to find a least-cost path from an origin to a destination such that each node in a given set of goals is visited at least once along the path. We present numerical results to illustrate the advantages of our framework over conventional alternates in terms of the number of expanded nodes and run time.

Details