T. K. Satish Kumar

AIJ Journal 2026 Journal Article

Approximate multi-objective search

• Han Zhang
• Oren Salzman
• T. K. Satish Kumar
• Ariel Felner
• Carlos Hernández Ulloa
• Sven Koenig

AAMAS Conference 2025 Conference Paper

Empirical Hardness in Multi-Agent Pathfinding: Research Challenges and Opportunities

• Jingyao Ren
• Eric Ewing
• T. K. Satish Kumar
• Sven Koenig
• Nora Ayanian

Multi-agent pathfinding (MAPF) is the problem of finding collisionfree paths for a team of agents on a map. Although MAPF is NPhard, the hardness of solving individual instances varies significantly, revealing a gap between theoretical complexity and actual hardness. This paper outlines three key research challenges in MAPF empirical hardness to understand such phenomena. The first challenge, known as algorithm selection, is determining the bestperforming algorithms for a given instance. The second challenge is understanding the key instance features that affect MAPF empirical hardness, such as structural properties like phase transition and backbone/backdoor. The third challenge is how to leverage our knowledge of MAPF empirical hardness to effectively generate hard MAPF instances or diverse benchmark datasets. This work establishes a foundation for future empirical hardness research and encourages deeper investigation into these promising and underexplored areas.

ICAPS Conference 2024 Conference Paper

Bounded-Suboptimal Weight-Constrained Shortest-Path Search via Efficient Representation of Paths

• Han Zhang 0018
• Oren Salzman
• Ariel Felner
• T. K. Satish Kumar
• Sven Koenig

In the Weight-Constrained Shortest-Path (WCSP) problem, given a graph in which each edge is annotated with a cost and a weight, a start state, and a goal state, the task is to compute a minimum-cost path from the start state to the goal state with weight no larger than a given weight limit. While most existing works have focused on solving the WCSP problem optimally, many real-world situations admit a trade-off between efficiency and a suboptimality bound for the path cost. In this paper, we propose the bounded-suboptimal WCSP algorithm WC-A*pex, which is built on the state-of-the-art approximate bi-objective search algorithm A*pex. WC-A*pex uses an approximate representation of paths with similar costs and weights to compute a (1+ε)-suboptimal path, for a given ε. During its search, WC-A*pex avoids storing all paths explicitly and thereby reduces the search effort while still retaining its (1 + ε)-suboptimality bound. On benchmark road networks, our experimental results show that WC-A*pex with ε = 0. 01 (i. e. , with a guaranteed suboptimality of at most 1%) achieves a speed-up of up to an order of magnitude over WC-A*, a state-of-the-art WCSP algorithm, and its bounded-suboptimal variant.

ICAPS Conference 2024 Conference Paper

Map Connectivity and Empirical Hardness of Grid-based Multi-Agent Pathfinding Problem

• Jingyao Ren
• Eric Ewing
• T. K. Satish Kumar
• Sven Koenig
• Nora Ayanian

We present an empirical study of the relationship between map connectivity and the empirical hardness of the multi-agent pathfinding (MAPF) problem. By analyzing the second smallest eigenvalue (commonly known as lambda2) of the normalized Laplacian matrix of different maps, our initial study indicates that maps with smaller lambda2 tend to create more challenging instances when agents are generated uniformly randomly. Additionally, we introduce a map generator based on Quality Diversity (QD) that is capable of producing maps with specified lambda2 ranges, offering a possible way for generating challenging MAPF instances. Despite the absence of a strict monotonic correlation with lambda2 and the empirical hardness of MAPF, this study serves as a valuable initial investigation for gaining a deeper understanding of what makes a MAPF instance hard to solve.

SoCS Conference 2024 Conference Paper

Solving Facility Location Problems via FastMap and Locality Sensitive Hashing

• Ang Li
• Peter J. Stuckey
• Sven Koenig
• T. K. Satish Kumar

Facility Location Problems (FLPs) arise while serving multiple customers in a shared environment, minimizing transportation and other costs. Hence, they involve the optimal placement of facilities. They are defined on graphs as well as in Euclidean spaces with or without obstacles; and they are typically NP-hard to solve optimally. There are many heuristic algorithms tailored to different kinds of FLPs. However, FLPs defined in Euclidean spaces without obstacles are the most amenable to efficient and effective heuristic algorithms. This motivates the idea of quickly reformulating FLPs on graphs and in Euclidean spaces with obstacles to FLPs in Euclidean spaces without obstacles. Towards this end, we propose a new approach that uses FastMap and Locality Sensitive Hashing. FastMap is a near-linear-time algorithm that embeds the vertices of a graph in a Euclidean space while approximately preserving graph-based distances as Euclidean distances for all pairs of vertices. Through extensive experiments, we show that our approach significantly outperforms other state-of-the-art competing algorithms on a variety of FLPs: the Multi-Agent Meeting, Vertex K-Median (VKM), Weighted VKM, and the Capacitated VKM problems.

SoCS Conference 2024 Conference Paper

Speeding Up Dominance Checks in Multi-Objective Search: New Techniques and Data Structures

• Han Zhang 0018
• Oren Salzman
• Ariel Felner
• T. K. Satish Kumar
• Carlos Hernández Ulloa
• Sven Koenig

In multi-objective search, given a directed graph where each edge is annotated with multiple cost metrics, a start state, and a goal state. We are interested in computing the Pareto frontier, i. e. , the set of all undominated paths from the start state to the goal state. Almost all multi-objective search algorithms use dominance checks to determine if a search node can be pruned. Since dominance checks are performed in the inner loop of the multi-objective search, they are the most time-consuming part of it. In this paper, we propose (1) two novel techniques to reduce duplicate dominance checks and (2) a simple data structure that enables more efficient dominance checks. Our experimental results show that combining our proposed techniques and data structure speeds up LTMOA*, a state-of-the-art multi-objective search algorithm, by up to an order of magnitude on road network instances.

ICAPS Conference 2023 Conference Paper

Efficient Multi-Query Bi-Objective Search via Contraction Hierarchies

• Han Zhang 0018
• Oren Salzman
• Ariel Felner
• T. K. Satish Kumar
• Carlos Hernández Ulloa
• Sven Koenig

Contraction Hierarchies (CHs) have been successfully used as a preprocessing technique in single-objective graph search for finding shortest paths. However, only a few existing works on utilizing CHs for bi-objective search exist, and none of them uses CHs to compute Pareto frontiers. This paper proposes an CH-based approach capable of efficiently computing Pareto frontiers for bi-objective search along with several speedup techniques. Specifically, we propose a new preprocessing approach that computes CHs with fewer edges than the existing preprocessing approach, which reduces both the preprocessing times (up to 3x in our experiments) and the query times. Furthermore, we propose a partial-expansion technique, which dramatically speeds up the query times. We demonstrate the advantages of our approach on road networks with 1 to 14 million states. The longest preprocessing time is less than 6 hours, and the average speedup in query times is roughly two orders of magnitude compared to BOA*, a state-of-the-art single-query bi-objective search algorithm.

ICAPS Conference 2023 Conference Paper

Priority-Based Search for the Virtual Network Embedding Problem

• Yi Zheng 0010
• Hang Ma 0001
• Sven Koenig
• Erik Kline
• T. K. Satish Kumar

The Virtual Network Embedding (VNE) problem is a constrained optimization problem. It arises in the context of allocating resources on heterogeneous physical networks to provide end-to-end computing services. In this paper, we introduce a new solver, called VNE-PBS, that uses priority-based search (PBS) for solving the VNE problem. VNE-PBS uses a prioritized heuristic search algorithm that explores the space of all possible priority orderings using a systematic depth-first search. The solver is inspired by the success of PBS for the Multi-Agent Path Finding (MAPF) problem and the similarities between the VNE and MAPF problems. We show that VNE-PBS significantly outperforms competing methods on various benchmark instances for both the offline and online versions of the VNE problem.

SoCS Conference 2023 Conference Paper

Towards Effective Multi-Valued Heuristics for Bi-objective Shortest-Path Algorithms via Differential Heuristics

• Han Zhang 0018
• Oren Salzman
• Ariel Felner
• T. K. Satish Kumar
• Shawn Skyler
• Carlos Hernández Ulloa
• Sven Koenig

In bi-objective graph search, each edge is annotated with a cost pair, where each cost corresponds to an objective to optimize. We are interested in finding all undominated paths from a given start state to a given goal state (called the Pareto front). Almost all existing works of bi-objective search use single-valued heuristics, which use one number for each objective, to estimate the cost between any given state and the goal state. However, single-valued heuristics cannot reflect the trade-offs between the two costs. On the other hand, multi-valued heuristics use a set of pairs to estimate the Pareto front between any given state and the goal state and are more informed than single-valued heuristics. However, they are rarely studied and have yet to be investigated in explicit state spaces by any existing work. In this paper, we are interested in using multi-valued heuristics to improve bi-objective search algorithms in explicit state spaces. More specifically, we generalize Differential Heuristics (DHs), a class of memory-based heuristics for single-objective search, to bi-objective search, resulting in Bi-objective Differential Heuristics (BO-DHs). We propose several techniques to reduce the memory usage and computational overhead of BO-DHs significantly. Our experimental results show that, with suggested improvement and tuned parameters, BO-DHs can reduce the node expansion and runtime of a bi-objective search algorithm by up to an order of magnitude, paving the way for more effective multi-valued heuristics.

ICAPS Conference 2022 Conference Paper

A*pex: Efficient Approximate Multi-Objective Search on Graphs

• Han Zhang 0018
• Oren Salzman
• T. K. Satish Kumar
• Ariel Felner
• Carlos Hernández Ulloa
• Sven Koenig

In multi-objective search, edges are annotated with cost vectors consisting of multiple cost components. A path dominates another path with the same start and goal vertices iff the component-wise sum of the cost vectors of the edges of the former path is ``less than'' the component-wise sum of the cost vectors of the edges of the latter path. The Pareto-optimal solution set is the set of all undominated paths from a given start vertex to a given goal vertex. Its size can be exponential in the size of the graph being searched, which makes multi-objective search time-consuming. In this paper, we therefore study how to find an approximate Pareto-optimal solution set for a user-provided vector of approximation factors. The size of such a solution set can be significantly smaller than the size of the Pareto-optimal solution set, which enables the design of approximate multi-objective search algorithms that are efficient and produce small solution sets. We present such an algorithm in this paper which we call A*pex and which builds on PP-A*, a state-of-the-art approximate bi-objective search algorithm (where there are only two cost components) but (1) makes PP-A* more efficient for bi-objective search and (2) generalizes it to multi-objective search for any number of cost components. We first analyze the correctness of A*pex and then experimentally demonstrate its efficiency advantage over existing approximate algorithms for bi- and tri-objective search.

SoCS Conference 2022 Conference Paper

Anytime Approximate Bi-Objective Search

• Han Zhang 0018
• Oren Salzman
• T. K. Satish Kumar
• Ariel Felner
• Carlos Hernández Ulloa
• Sven Koenig

The Pareto-optimal frontier for a bi-objective search problem instance consists of all solutions that are not worse than any other solution in both objectives. The size of the Pareto-optimal frontier can be exponential in the size of the input graph, and hence finding it can be hard. Some existing works leverage a user-specified approximation factor epsilon to compute an approximate Pareto-optimal frontier that can be significantly smaller than the Pareto-optimal frontier. In this paper, we propose an anytime approximate bi-objective search algorithm, called Anytime Bi-Objective A*-epsilon (A-BOA*). A-BOA* is useful when deliberation time is limited. It first finds an approximate Pareto-optimal frontier quickly, iteratively improves it while time allows, and eventually finds the Pareto-optimal frontier. It efficiently reuses the search effort from previous iterations and makes use of a novel pruning technique. Our experimental results show that A-BOA* substantially outperforms baseline algorithms that do not reuse previous search effort, both in terms of runtime and number of node expansions. In fact, the most advanced variant of A-BOA* even slightly outperforms BOA*, a state-of-the-art bi-objective search algorithm, for finding the Pareto-optimal frontier. Moreover, given only a limited amount of deliberation time, A-BOA* finds solutions that collectively approximate the Pareto-optimal frontier much better than the solutions found by BOA*.

ICAPS Conference 2022 Conference Paper

Conflict-Based Search for the Virtual Network Embedding Problem

• Yi Zheng 0010
• Srivatsan Ravi
• Erik Kline
• Sven Koenig
• T. K. Satish Kumar

In emerging network virtualization architectures, service providers will be able to create many heterogeneous virtual networks and offer customized end-to-end services by leasing shared resources from infrastructure providers. The Virtual Network Embedding (VNE) problem is central to such technology. It involves the proper allocation of CPU and bandwidth resources available in a physical substrate network to meet the demands of multiple virtual networks. Combinatorially, the VNE problem is a problem in resource management that is NP-hard to solve. In this paper, we present a novel version of the Conflict-Based Search (CBS) algorithm for solving the VNE problem. Our approach, called VNE-CBS, is inspired by the success of the CBS framework in the Multi-Agent Path Finding domain. We successfully address the unique challenges in applying the CBS framework to the VNE problem, and, in doing so, we pave the way for overcoming a crucial issue in Internet ossification via heuristic search methods. On the theoretical front, we show that, unlike many existing algorithms, our algorithm is complete and optimal. On the experimental front, we show that our algorithm significantly outperforms other state-of-the-art methods on various benchmark instances for both the offline and online versions of the VNE problem.

SoCS Conference 2022 Conference Paper

Mutex Propagation in Multi-Agent Path Finding for Large Agents

• Han Zhang 0018
• Yutong Li
• Jiaoyang Li 0001
• T. K. Satish Kumar
• Sven Koenig

Mutex propagation and its concomitant symmetry-breaking techniques have proven useful in Multi-Agent Path Finding (MAPF) with point agents. In this paper, we show that they can be easily generalized to richer MAPF problems. In particular, we demonstrate their application to MAPF with ``Large

SoCS Conference 2021 Conference Paper

A Hierarchical Approach to Multi-Agent Path Finding

• Han Zhang 0018
• Mingze Yao
• Ziang Liu 0002
• Jiaoyang Li 0001
• Lucas Terr
• Shao-Hung Chan
• T. K. Satish Kumar
• Sven Koenig

Solving Multi-Agent Path Finding (MAPF) instances optimally is NP-hard, and existing optimal and bounded suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multiple regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP is able to solve as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps.

ICAPS Conference 2021 Conference Paper

Conflict-Based Increasing Cost Search

• Thayne T. Walker
• Nathan R. Sturtevant
• Ariel Felner
• Han Zhang 0018
• Jiaoyang Li 0001
• T. K. Satish Kumar

Two popular optimal search-based solvers for the multi-agent pathfinding (MAPF) problem, Conflict-Based Search (CBS) and Increasing Cost Tree Search (ICTS), have been extended separately for continuous time domains and symmetry breaking. However, an approach to symmetry breaking in continuous time domains remained elusive. In this work, we introduce a new algorithm, Conflict-Based Increasing Cost Search (CBICS), which is capable of symmetry breaking in continuous time domains by combining the strengths of CBS and ICTS. Our experiments show that CBICS often finds solutions faster than CBS and ICTS in both unit time and continuous time domains.

AAAI Conference 2021 Conference Paper

Lifelong Multi-Agent Path Finding in Large-Scale Warehouses

• Jiaoyang Li
• Andrew Tinka
• Scott Kiesel
• Joseph W. Durham
• T. K. Satish Kumar
• Sven Koenig

Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to their goal locations without collisions. In this paper, we study the lifelong variant of MAPF, where agents are constantly engaged with new goal locations, such as in large-scale automated warehouses. We propose a new framework Rolling-Horizon Collision Resolution (RHCR) for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of the agents only within a bounded time horizon and ignores collisions beyond it. RHCR is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We empirically evaluate RHCR with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1, 000 agents (= 38. 9% of the empty cells on the map) for simulated warehouse instances, significantly outperforming existing work.

ICAPS Conference 2021 Conference Paper

Temporal Reasoning with Kinodynamic Networks

• Han Zhang 0018
• Neelesh Tiruviluamala
• Sven Koenig
• T. K. Satish Kumar

Temporal reasoning is central to Artificial Intelligence (AI) and many of its applications. However, the existing algorithmic frameworks for temporal reasoning are not expressive enough to be applicable to robots with complex kinodynamic constraints typically described using differential equations. For example, while minimum and maximum velocity constraints can be encoded in Simple Temporal Networks (STNs), higher-order kinodynamic constraints cannot be represented in existing frameworks. In this paper, we present a novel framework for temporal reasoning called Kinodynamic Networks (KDNs). KDNs combine elements of existing temporal reasoning frameworks with the idea of Bernstein polynomials. The velocity profiles of robots are represented using Bernstein polynomials; and dynamic constraints on these velocity profiles can be converted to linear constraints on the to-be-determined coefficients of their Bernstein polynomials. We study KDNs for their attractive theoretical properties and apply them to the Multi-Agent Path Finding (MAPF) problem with higher-order kinodynamic constraints. We show that our approach is not only scalable but also yields smooth velocity profiles for all robots that can be executed by their controllers.

SoCS Conference 2020 Conference Paper

Decision Tree Learning-Inspired Dynamic Variable Ordering for the Weighted CSP

• Hong Xu 0003
• Kexuan Sun 0002
• Sven Koenig
• T. K. Satish Kumar

The weighted constraint satisfaction problem (WCSP) is a powerful mathematical framework for combinatorial optimization. The branch and bound search paradigm is very successful in solving the WCSP but critically depends on the ordering in which variables are instantiated. In this paper, we introduce a new framework for dynamic variable ordering for solving the WCSP. This framework is inspired by regression decision tree learning. Variables are ordered dynamically based on samples of random assignments of values to variables as well as their corresponding total weights. Within this framework, we propose four variable ordering heuristics (sdr, inv-sdr, rr and inv-rr). We compare them with many other state-of-the-art dynamic variable ordering heuristics, and show that sdr and rr outperform them on many real-world and random benchmark instances.

SoCS Conference 2020 Conference Paper

Embedding Directed Graphs in Potential Fields Using FastMap-D

• Sriram Gopalakrishnan
• Liron Cohen 0002
• Sven Koenig
• T. K. Satish Kumar

Embedding undirected graphs in a Euclidean space has many computational benefits. FastMap is an efficient embedding algorithm that facilitates a geometric interpretation of problems posed on undirected graphs. However, Euclidean distances are inherently symmetric and, thus, Euclidean embeddings cannot be used for directed graphs. In this paper, we present FastMap-D, an efficient generalization of FastMap to directed graphs. FastMap-D embeds vertices using a potential field to capture the asymmetry between the to-and-fro pairwise distances in directed graphs. FastMap-D learns a potential function to define the potential field using a machine learning module. In experiments on various kinds of directed graphs, we demonstrate the advantage of FastMap-D over other approaches.

AAAI Conference 2020 Conference Paper

Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers

• Ngai Meng Kou
• Cheng Peng
• Hang Ma
• T. K. Satish Kumar
• Sven Koenig

In this paper, we study the one-shot and lifelong versions of the Target Assignment and Path Finding problem in automated sortation centers, where each agent needs to constantly assign itself a sorting station, move to its assigned station without colliding with obstacles or other agents, wait in the queue of that station to obtain a parcel for delivery, and then deliver the parcel to a sorting bin. The throughput of such centers is largely determined by the total idle time of all stations since their queues can frequently become empty. To address this problem, we first formalize and study the oneshot version that assigns stations to a set of agents and finds collision-free paths for the agents to their assigned stations. We present efficient algorithms for this task based on a novel min-cost max-flow formulation that minimizes the total idle time of all stations in a fixed time window. We then demonstrate how our algorithms for solving the one-shot problem can be applied to solving the lifelong problem as well. Experimentally, we believe to be the first researchers to consider real-world automated sortation centers using an industrial simulator with realistic data and a kinodynamic model of real robots. On this simulator, we showcase the benefits of our algorithms by demonstrating their efficiency and effectiveness for up to 350 agents.

SoCS Conference 2020 Conference Paper

Moving Agents in Formation in Congested Environments

• Jiaoyang Li 0001
• Kexuan Sun 0002
• Hang Ma 0001
• Ariel Felner
• T. K. Satish Kumar
• Sven Koenig

In this paper, we formalize and study the Moving Agents in Formation (MAiF) problem, that combines the tasks of finding short collision-free paths for multiple agents and keeping them in close adherence to a desired formation. Previous work includes controller-based algorithms, swarm-based algorithms, and potential-field-based algorithms. They usually focus on only one or the other of these tasks, solve the problem greedily without systematic search, and thus generate costly solutions or even fail to find solutions in congested environment. In this paper, we develop a two-phase search algorithm, called SWARM-MAPF, whose first phase is inspired by swarm-based algorithms (in open regions) and whose second phase is inspired by multi-agent path-finding (MAPF) algorithms (in congested regions). In the first phase, SWARM-MAPF selects a leader among the agents and finds a path for it that is sufficiently far away from the obstacles so that the other agents can preserve the desired formation around it. It also identifies the critical segments of the leader

ICAPS Conference 2020 Conference Paper

Multi-Agent Path Finding with Mutex Propagation

• Han Zhang 0018
• Jiaoyang Li 0001
• Pavel Surynek
• Sven Koenig
• T. K. Satish Kumar

Mutex propagation is a form of efficient constraint propagation popularly used in AI planning to tightly approximate the reachable states from a given state. We utilize this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF, mutex propagation provides stronger constraints for conflict resolution in Conflict-Based Search (CBS), a popular optimal MAPF algorithm, and provides it with the ability to identify and reason with symmetries in MAPF. While existing work identifies a limited form of symmetries using rectangle reasoning and requires the manual design of symmetry-breaking constraints, mutex propagation is more general and allows for the automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH with rectangle reasoning, a state-of-the-art variant of CBS, with respect to runtime and success rate.

AAMAS Conference 2019 Conference Paper

A New Constraint Satisfaction Perspective on Multi-Agent Path Finding: Preliminary Results

• Jiangxing Wang
• Jiaoyang Li
• Hang Ma
• Sven Koenig
• T. K. Satish Kumar

In this paper, we adopt a new perspective on the Multi-Agent Path Finding (MAPF) problem and view it as a Constraint Satisfaction Problem (CSP). A variable corresponds to an agent, its domain is the set of all paths from the start vertex to the goal vertex of the agent, and the constraints allow only conflict-free paths for each pair of agents. Although the domains and constraints are only implicitly defined, this new CSP perspective allows us to use successful techniques from CSP search. With the concomitant idea of using matrix computations for calculating the size of the reduced domain of an uninstantiated variable, we apply Dynamic Variable Ordering and Rapid Random Restarts to the MAPF problem. In our experiments, the resulting simple polynomial-time MAPF solver, called Matrix MAPF solver, either outperforms or matches the performance of many state-of-the-art solvers for the MAPF problem and its variants.

SoCS Conference 2019 Conference Paper

Extended Abstract: Lifelong Path Planning with Kinematic Constraintsfor Multi-Agent Pickup and Delivery

• Hang Ma 0001
• Wolfgang Hönig
• T. K. Satish Kumar
• Nora Ayanian
• Sven Koenig

The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for well-formed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities. This paper was published at AAAI 2019.

AAAI Conference 2019 Conference Paper

Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery

• Hang Ma
• Wolfgang Hönig
• T. K. Satish Kumar
• Nora Ayanian
• Sven Koenig

The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for wellformed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities.

AAAI Conference 2019 Conference Paper

Multi-Agent Path Finding for Large Agents

• Jiaoyang Li
• Pavel Surynek
• Ariel Felner
• Hang Ma
• T. K. Satish Kumar
• Sven Koenig

Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conflict-Based Search (CBS) is a state-of-the-art MAPF algorithm based on a twolevel tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e. g. , a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. Geometric agents are referred to as “large” agents because they can occupy multiple points at the same time. In this paper, we formalize and study LA- MAPF, i. e. , MAPF for large agents. We first show how CBS can be adapted to solve LA-MAPF. We then present a generalized version of CBS, called Multi-Constraint CBS (MC- CBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. We introduce three different approaches to choose such constraints as well as an approach to compute admissible heuristics for the high-level search. Experimental results show that all MC-CBS variants outperform CBS by up to three orders of magnitude in terms of runtime. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases.

SoCS Conference 2019 Conference Paper

Multi-Agent Path Finding for Large Agents

• Jiaoyang Li 0001
• Pavel Surynek
• Ariel Felner
• Hang Ma 0001
• T. K. Satish Kumar
• Sven Koenig

Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conflict-Based Search (CBS) is a state-of-the-art MAPF algorithm based on a two-level tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e. g. , a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. Geometric agents are referred to as “large” agents because they can occupy multiple points at the same time. In this paper, we formalize and study LAMAPF, i. e. , MAPF for large agents. We first show how CBS can be adapted to solve LA-MAPF. We then present a generalized version of CBS, called Multi-Constraint CBS (MC-CBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. We introduce three different approaches to choose such constraints as well as an approach to compute admissible heuristics for the high-level search. Experimental results show that all MC-CBS variants outperform CBS by up to three orders of magnitude in terms of runtime. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases.

SoCS Conference 2019 Conference Paper

Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

• Roni Stern
• Nathan R. Sturtevant
• Ariel Felner
• Sven Koenig
• Hang Ma 0001
• Thayne T. Walker
• Jiaoyang Li 0001
• Dor Atzmon

The multi-agent pathfinding problem (MAPF) is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses, autonomous vehicles, and robotics. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers assume different sets of assumptions, e. g. , whether agents can traverse the same road at the same time, and have different objective functions, e. g. , minimize makespan or sum of agents

SoCS Conference 2019 Conference Paper

Optimal and Bounded-Suboptimal Multi-Agent Motion Planning

• Liron Cohen 0002
• Tansel Uras
• T. K. Satish Kumar
• Sven Koenig

Multi-Agent Motion Planning (MAMP) is the task of finding conflict-free kinodynamically feasible plans for agents from start to goal states. While MAMP is of significant practical importance, existing solvers are either incomplete, inefficient or rely on simplifying assumptions. For example, Multi-Agent Path Finding (MAPF) solvers conventionally assume discrete timesteps and rectilinear movement of agents between neighboring vertices of a graph. In this paper, we develop MAMP solvers that obviate these simplifying assumptions and yet generalize the core ideas of state-of-the-art MAPF solvers. Specifically, since different motions may take arbitrarily different durations, MAMP solvers need to efficiently reason with continuous time and arbitrary wait durations. To do so, we adapt (Enhanced) Conflict-Based Search to continuous time and develop a novel bounded-suboptimal extension of Safe Interval Path Planning, called Soft Conflict Interval Path Planning. On the theoretical side, we justify the completeness, optimality and bounded-suboptimality of our MAMP solvers. On the experimental side, we show that our MAMP solvers scale well with increasing suboptimality bounds.

ICAPS Conference 2019 Conference Paper

Using FastMap to Solve Graph Problems in a Euclidean Space

• Jiaoyang Li 0001
• Ariel Felner
• Sven Koenig
• T. K. Satish Kumar

It is well known that many graph problems, like the Traveling Salesman Problem, are easier to solve in a Euclidean space. This motivates the idea of quickly preprocessing a given graph by embedding it in a Euclidean space to solve graph problems efficiently. In this paper, we study a nearlinear time algorithm, called FastMap, that embeds a given non-negative edge-weighted undirected graph in a Euclidean space and approximately preserves the pairwise shortest path distances between vertices. The Euclidean space can then be used either for heuristic guidance of A* (as suggested previously) or for geometric interpretations that facilitate the application of techniques from analytical geometry. We present a new variant of FastMap and compare it with the original variant theoretically and empirically. We demonstrate its usefulness for solving a path-finding and a multi-agent meeting problem.

ICAPS Conference 2018 Conference Paper

Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding

• Ariel Felner
• Jiaoyang Li 0001
• Eli Boyarski
• Hang Ma 0001
• Liron Cohen 0002
• T. K. Satish Kumar
• Sven Koenig

Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for the multi-agent path-finding problem. However, existing variants of CBS do not use any heuristics that estimate future work. In this paper, we introduce different admissible heuristics for CBS by aggregating cardinal conflicts among agents. In our experiments, CBS with these heuristics outperforms previous state-of-the-art CBS variants by up to a factor of five.

IJCAI Conference 2018 Conference Paper

Anytime Focal Search with Applications

• Liron Cohen
• Matias Greco
• Hang Ma
• Carlos Hernandez
• Ariel Felner
• T. K. Satish Kumar
• Sven Koenig

Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*, it uses an open list whose states are sorted in increasing order of their f-values. Unlike A*, it also uses a focal list containing all states from the open list whose f-values are no larger than a suboptimality factor times the smallest f-value in the open list. In this paper, we develop an anytime version of FS, called anytime FS (AFS), that is useful when deliberation time is limited. AFS finds a "good" solution quickly and refines it to better and better solutions if time allows. It does this refinement efficiently by reusing previous search efforts. On the theoretical side, we show that AFS is bounded suboptimal and that anytime potential search (ATPS/ANA*), a state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special case of AFS. In doing so, we bridge the gap between anytime search algorithms based on BSS and BCS. We also identify different properties of priority functions, used to sort the focal list, that may allow for efficient reuse of previous search efforts. On the experimental side, we demonstrate the usefulness of AFS for solving hard combinatorial problems, such as the generalized covering traveling salesman problem and the multi-agent pathfinding problem.

AAAI Conference 2018 Conference Paper

Load Scheduling of Simple Temporal Networks Under Dynamic Resource Pricing

• T. K. Satish Kumar
• Zhi Wang
• Anoop Kumar
• Craig Rogers
• Craig Knoblock

We study load scheduling of simple temporal networks (STNs) under dynamic pricing of resources. We are given a set of processes and a set of simple temporal constraints between their execution times, i. e. , an STN. Each process uses a certain amount of resource for execution. The unit price of the resource is a function of time, f(t). The goal is to find a schedule of a given STN that trades off makespan minimization against cost minimization within a user-specified suboptimality bound. We provide a polynomial-time algorithm for solving the load scheduling problem when f(t) is piecewise constant. This has important applications in many real-world domains including the smart home and smart grid domains. We then study the dependency of the unit price of the resource on time as well as the total demand at that time. This leads to a further characterization of tractable, NP-hard, and conjectured tractable cases.

SoCS Conference 2018 Conference Paper

Message Passing Algorithms for Semiring-Based and Valued Constraint Satisfaction Problems

• Hong Xu 0003
• Cheng Cheng 0001
• Sven Koenig
• T. K. Satish Kumar

Local consistency algorithms, like arc consistency (AC) algorithms, are polynomial-time algorithms that prune the search space of constraint satisfaction problems (CSPs). In this paper, we present connections between message passing algorithms and AC for semiring-based CSPs (SCSPs) and valued CSPs (VCSPs), two well-established frameworks that generalize CSPs. Message passing algorithms are well known distributed search algorithms for solving many combinatorial problems in artificial intelligence, probabilistic reasoning, and information theory. However, the relationship between message passing algorithms and SCSPs or VCSPs still remains understudied. Towards this end, we propose the best-O message passing (BOMP) algorithm for SCSPs and VCSPs. We prove that, unlike other standard message passing algorithms which are in general not guaranteed to converge, the BOMP algorithm guarantees convergence for SCSPs and specific subclasses of VCSPs. We also theoretically study the relationship between the BOMP algorithm and AC on SCSPs, and empirically study the quality of the solutions produced by the BOMP algorithm for VCSPs.

IJCAI Conference 2018 Conference Paper

Multi-Agent Path Finding with Deadlines

• Hang Ma
• Glenn Wagner
• Ariel Felner
• Jiaoyang Li
• T. K. Satish Kumar
• Sven Koenig

We formalize Multi-Agent Path Finding with Deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within the deadline, without colliding with each other. We first show that MAPF-DL is NP-hard to solve optimally. We then present two classes of optimal algorithms, one based on a reduction of MAPF-DL to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network and the other one based on novel combinatorial search algorithms. Our empirical results demonstrate that these MAPF-DL solvers scale well and each one dominates the other ones in different scenarios.

AAMAS Conference 2018 Conference Paper

Multi-Agent Path Finding with Deadlines: Preliminary Results

• Hang Ma
• Glenn Wagner
• Ariel Felner
• Jiaoyang Li
• T. K. Satish Kumar
• Sven Koenig

We formalize the problem of multi-agent path finding with deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within a given deadline, without colliding with each other. We first show that the MAPF-DL problem is NP-hard to solve optimally. We then present an optimal MAPF-DL algorithm based on a reduction of the MAPF-DL problem to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network.

SoCS Conference 2018 Conference Paper

Rapid Randomized Restarts for Multi-Agent Path Finding Solvers

• Liron Cohen 0002
• Glenn Wagner
• David M. Chan
• Howie Choset
• Nathan R. Sturtevant
• Sven Koenig
• T. K. Satish Kumar

Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well studied in artificial intelligence and robotics. Recently, randomized MAPF solvers have been shown to exhibit heavy-tailed distributions of runtimes, which can be exploited to boost their success rate for a given runtime limit. In this paper, we discuss different ways of randomizing MAPF solvers and evaluate simple rapid randomized restart strategies for state-of-the-art MAPF solvers such as iECBS, M* with highways and CBS-CL.

AAMAS Conference 2018 Conference Paper

Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results

• Liron Cohen
• Sven Koenig
• T. K. Satish Kumar
• Glenn Wagner
• Howie Choset
• David Chan
• Nathan Sturtevant

Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world applications. However, existing MAPF solvers are deterministic and perform poorly on MAPF instances where many agents interfere with each other in a small region of space. In this paper, we enhance MAPF solvers with randomization and observe that their runtimes can exhibit heavy-tailed distributions. This insight leads us to develop simple Rapid Randomized Restart (RRR) strategies with the intuition that multiple short runs will have a better chance of solving such MAPF instances than one long run with the same runtime limit. Our contribution is to show experimentally that the same RRR strategy indeed boosts the performance of two state-of-the-art MAPF solvers, namely M* and ECBS.

ICAPS Conference 2018 Conference Paper

The Factored Shortest Path Problem and Its Applications in Robotics

• Zhi Wang 0013
• Liron Cohen 0002
• Sven Koenig
• T. K. Satish Kumar

Many real-world combinatorial problems exhibit structure in the way in which their variables interact. Such structure can be exploited in the form of "factors" for representational as well as computational benefits. Factored representations are extensively used in probabilistic reasoning, constraint satisfaction, planning, and decision theory. In this paper, we formulate the factored shortest path problem (FSPP) on a collection of constraints interpreted as factors of a high-dimensional map. We show that the FSPP is not only a generalization of the regular shortest path problem but also particularly relevant to robotics. We develop factored-space heuristics for A* and prove that they are admissible and consistent. We provide experimental results on both random and handcrafted instances as well as on an example robotics domain to show that A* with factored-space heuristics outperforms A* with the Manhattan Distance heuristic in many cases.

IJCAI Conference 2018 Conference Paper

The FastMap Algorithm for Shortest Path Computations

• Liron Cohen
• Tansel Uras
• Shiva Jahangiri
• Aliyah Arunasalam
• Sven Koenig
• T. K. Satish Kumar

We present a new preprocessing algorithm for embedding the nodes of a given edge-weighted undirected graph into a Euclidean space. The Euclidean distance between any two nodes in this space approximates the length of the shortest path between them in the given graph. Later, at runtime, a shortest path between any two nodes can be computed with an A* search using the Euclidean distances as heuristic. Our preprocessing algorithm, called FastMap, is inspired by the data-mining algorithm of the same name and runs in near-linear time. Hence, FastMap is orders of magnitude faster than competing approaches that produce a Euclidean embedding using Semidefinite Programming. FastMap also produces admissible and consistent heuristics and therefore guarantees the generation of shortest paths. Moreover, FastMap applies to general undirected graphs for which many traditional heuristics, such as the Manhattan Distance heuristic, are not well defined. Empirically, we demonstrate that A* search using the FastMap heuristic is competitive with A* search using other state-of-the-art heuristics, such as the Differential heuristic.

SoCS Conference 2017 Conference Paper

A Linear-Time and Linear-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs

• Hong Xu 0003
• T. K. Satish Kumar
• Sven Koenig

In this paper, we develop the message passing based linear-time and linear-space MVC algorithm (MVC-MPL) for solving the minimum vertex cover (MVC) problem. MVC-MPL is based on heuristics derived from a theoretical analysis of message passing algorithms in the context of belief propagation. We show that MVC-MPL produces smaller vertex covers than other linear-time and linear-space algorithms.

AAMAS Conference 2017 Conference Paper

Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks

• Hang Ma
• Jiaoyang Li
• T. K. Satish Kumar
• Sven Koenig

The multi-agent path-finding (MAPF) problem has recently received a lot of attention. However, it does not capture important characteristics of many real-world domains, such as automated warehouses, where agents are constantly engaged with new tasks. In this paper, we therefore study a lifelong version of the MAPF problem, called the multiagent pickup and delivery (MAPD) problem. In the MAPD problem, agents have to attend to a stream of delivery tasks in an online setting. One agent has to be assigned to each delivery task. This agent has to first move to a given pickup location and then to a given delivery location while avoiding collisions with other agents. We present two decoupled MAPD algorithms, Token Passing (TP) and Token Passing with Task Swaps (TPTS). Theoretically, we show that they solve all well-formed MAPD instances, a realistic subclass of MAPD instances. Experimentally, we compare them against a centralized strawman MAPD algorithm without this guarantee in a simulated warehouse system. TP can easily be extended to a fully distributed MAPD algorithm and is the best choice when real-time computation is of primary concern since it remains efficient for MAPD instances with hundreds of agents and tasks. TPTS requires limited communication among agents and balances well between TP and the centralized MAPD algorithm.

AAAI Conference 2017 Conference Paper

Multi-Agent Path Finding with Delay Probabilities

• Hang Ma
• T. K. Satish Kumar
• Sven Koenig

Several recently developed Multi-Agent Path Finding (MAPF) solvers scale to large MAPF instances by searching for MAPF plans on 2 levels: The high-level search resolves collisions between agents, and the low-level search plans paths for single agents under the constraints imposed by the high-level search. We make the following contributions to solve the MAPF problem with imperfect plan execution with small average makespans: First, we formalize the MAPF Problem with Delay Probabilities (MAPF-DP), define valid MAPF-DP plans and propose the use of robust plan-execution policies for valid MAPF-DP plans to control how each agent proceeds along its path. Second, we discuss 2 classes of decentralized robust plan-execution policies (called Fully Synchronized Policies and Minimal Communication Policies) that prevent collisions during plan execution for valid MAPF-DP plans. Third, we present a 2-level MAPF-DP solver (called Approximate Minimization in Expectation) that generates valid MAPF-DP plans.

IJCAI Conference 2017 Conference Paper

Summary: Multi-Agent Path Finding with Kinematic Constraints

• Wolfgang Hönig
• T. K. Satish Kumar
• Liron Cohen
• Hang Ma
• Hong Xu
• Nora Ayanian
• Sven Koenig

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, considers kinematic constraints, provides a guaranteed safety distance between robots, and exploits slack to avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.

SoCS Conference 2016 Conference Paper

Compliant Conditions for Polynomial Time Approximation of Operator Counts

• Tathagata Chakraborti
• Sarath Sreedharan
• Sailik Sengupta
• T. K. Satish Kumar
• Subbarao Kambhampati

In this brief abstract, we develop a computationally simpler version of the operator count heuristic for a particular class of domains. The contribution of this abstract is thus threefold, we (1) propose an efficient closed form approximation to the operator count heuristic; (2) leverage compressed sensing techniques to obtain an integer approximation in polynomial time; and (3) discuss the relationship of the proposed formulation to existing heuristics and investigate properties of domains where such approaches are useful.

IROS Conference 2016 Conference Paper

Formation change for robot groups in occluded environments

• Wolfgang Hönig
• T. K. Satish Kumar
• Hang Ma 0001
• Sven Koenig
• Nora Ayanian

We study formation change for robot groups in known environments. We are given a team of robots partitioned into groups, where robots in the same group are interchangeable with each other. A formation specifies the locations occupied by each group. The objective is to find collision-free paths that move all robots from a given start formation to a given goal formation. Our algorithm TAPF* has the following features: (a) it incorporates kinematic constraints of robots in form of velocity limits; (b) it maintains a user-specified safety distance between robots; (c) it attempts to minimize the makespan; and (d) it runs efficiently for hundreds of robots and dozens of groups even in dense 3D environments with narrow corridors and other occlusions. We demonstrate the efficiency and effectiveness of TAPF* in simulation and on robots.

IJCAI Conference 2016 Conference Paper

Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding

• Liron Cohen
• Tansel Uras
• T. K. Satish Kumar
• Hong Xu
• Nora Ayanian
• Sven Koenig

Multi-Agent Path Finding (MAPF) with the objective to minimize the sum of the travel times of the agents along their paths is a hard combinatorial problem. Recent work has shown that bounded-suboptimal MAPF solvers, such as Enhanced Conflict-Based Search or ECBS(w1) for short, run often faster than optimal MAPF solvers at the cost of incurring a suboptimality factor w1, that is due to using focal search. Other recent work has used experience graphs to guide the search of ECBS(w1) and speed it up, at the cost of incurring a separate suboptimality factor w2, that is due to inflating the heuristic values. Thus, the combination has suboptimality factor w1w2. In this first feasibility study, we develop a bounded-suboptimal MAPF solver, Improved-ECBS or iECBS(w1) for short, that has sub optimality factor w1 rather than w1w2 (because it uses experience graphs to guide its search without inflating the heuristic values) and can run faster than ECBS(w1). We also develop two first approaches for automatically generating experience graphs for a given MAPF instance. Finally, we observe heavy-tailed behavior in the runtimes of these MAPF solvers and develop a simple rapid randomized restart strategy that can increase the success rate of iECBS(w1) within a given runtime limit.

AAMAS Conference 2016 Conference Paper

Local Search on Trees and a Framework for Automated Construction Using Multiple Identical Robots (Extended Abstract)

• Trevor Cai
• David Y. Zhang
• T. K. Satish Kumar
• Sven Koenig
• Nora Ayanian

We present an algorithmic framework for automated construction using multiple identical robots. Our approach is based on the principle of tree-based dynamic programming and a concomitant idea of local search on trees to improve the quality of the generated plans. Inspired by the TER- MES project of Harvard University, robots in this domain are required to gather construction blocks from a reservoir and coordinate with each other in building user-specified structures much larger than themselves. While the robots are roughly of the same size as the blocks, they can scale greater heights by using temporarily constructed ramps in the substructures. Our algorithm employs an inner loop in which the planning problem is solved by performing dynamic programming on a tree that spans the footprint of the user-specified structure. The outer loop of the algorithm furnishes a good tree for the inner loop. We show how we can search for a good tree in the outer loop using local search methods that yield significant improvements in plan quality. Synchronization rules are then applied to parallelize the execution of the generated plan for multiple identical robots. General Terms Algorithms, Performance, Experimentation

ICAPS Conference 2016 Conference Paper

Multi-Agent Path Finding with Kinematic Constraints

• Wolfgang Hönig
• T. K. Satish Kumar
• Liron Cohen 0002
• Hang Ma 0001
• Hong Xu 0003
• Nora Ayanian
• Sven Koenig

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as finite maximum velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST, a novel approach that makes use of a simple temporal network to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, takes their maximum translational and rotational velocities into account, provides a guaranteed safety distance between them, and exploits slack to absorb imperfect plan executions and avoid time-intensive replanning in many cases. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.

AAAI Conference 2014 Conference Paper

A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints

• T. K. Satish Kumar
• Duc Thien Nguyen
• William Yeoh
• Sven Koenig

In this paper, we describe a simple randomized algorithm that runs in polynomial time and solves connected row convex (CRC) constraints in distributed settings. CRC constraints generalize many known tractable classes of constraints like 2- SAT and implicational constraints. They can model problems in many domains including temporal reasoning and geometric reasoning, and generally speaking, play the role of “Gaussians” in the logical world. Our simple randomized algorithm for solving them in distributed settings, therefore, has a number of important applications. We support our claims through a theoretical analysis and empirical results.

ICAPS Conference 2014 Conference Paper

A Tree-Based Algorithm for Construction Robots

• T. K. Satish Kumar
• Sangmook Johnny Jung
• Sven Koenig

In this paper, we present a tree-based algorithm for construction robots. Inspired by the TERMES project of Harvard University, robots in this domain are required to gather construction blocks from a reservoir and build user-specified structures much larger than themselves. While the robots are of roughly the same size as the blocks, they can scale greater heights by using temporarily constructed ramps in the substructures. In this paper, we consider the problem of minimizing the number of pickup and drop-off operations performed on blocks in order to build user-specified structures. Our polynomial-time algorithm heuristically solves this problem and is based on the idea of performing dynamic programming on a spanning tree in the inner loop and searching for a good tree to do so in the outer loop. Our algorithm performs very well in simulation and scales easily to large problem instances. For planning problems of this nature that are akin to construction domains, we believe that valuable lessons can be learned from comparing the success of our algorithm with the failure of off-the-shelf planning technologies.

ICAPS Conference 2008 Conference Paper

CircuitTSAT: A Solver for Large Instances of the Disjunctive Temporal Problem

• Blaine Nelson
• T. K. Satish Kumar

In this paper, we report on a new solver for large instances of the Disjunctive Temporal Problem (DTP). Our solver is based primarily on the idea of employing "compact" circuit-based representations of disjunctive temporal constraints (akin to ripple-carry adders used in computer arithmetic operations). These circuit-based representations are in turn converted to CNF clauses of a SAT instance, and a powerful SAT solver is subsequently employed to efficiently solve the resulting SAT instance. We refer to this efficient DTP solver as "CircuitTSAT. " A thorough empirical evaluation of CircuitTSAT shows that it significantly outperforms TSAT++ and Yices on a wide range of DTP instances. We also comment on the generality of our approach and its potential usefulness in dealing with more expressive constraints.

IJCAI Conference 2007 Conference Paper

• T. K. Satish Kumar

In this paper, we will provide a fast polynomial-time algorithm for solving simple temporal problems (STPs) with piecewise linear convex preference functions and a utilitarian objective function. Our algorithm is motivated by the study of the linear programming (LP)-dual of a given mincost circulation problem (MCCP). We will also show how this duality relationship between simple temporal problems with preferences (STPPs) and MCCPs leads to fast incremental algorithms for solving the former. Our algorithms bear important implications in planning, scheduling and execution monitoring scenarios where (partial) plans are subject to repeated changes, and the most preferred solutions to the underlying STPPs have to be computed and updated fast (incrementally).

ICAPS Conference 2006 Conference Paper

On Some Tractable Cases of Logical Filtering

• T. K. Satish Kumar
• Stuart Russell 0001

Filtering denotes any method whereby an agent updates its belief state---its knowledge of the state of the world---from a sequence of actions and observations. In logical filtering, the belief state is a logical formula describing the possible world states. Efficient algorithms for logical filtering bear important implications on reasoning tasks such as planning and diagnosis. In this paper, we will identify classes of transition constraints that are amenable to compact and indefinite filtering---presenting efficient algorithms wherever necessary. We will first show that connected row-convex (CRC) constraints are amenable to efficient filtering when path-consistency is enforced in appropriate steps. We will then extend this theory to provide a filtering algorithm based on repeatedly enforcing path-consistency and embedding the domain values of the related variables in tree structures to guarantee global consistency. Finally, we will identify and comment on the problem of multi-agent localization as a potential application of the theory developed in the paper (under some reasonable assumptions).

AAAI Conference 2006 Conference Paper

Simple Randomized Algorithms for Tractable Row and Tree Convex Constraints

• T. K. Satish Kumar

We identify tractable classes of constraints based on the following simple property of a constraint: “At every infeasible point, there exist two directions such that with respect to any other feasible point, moving along at least one of these two directions decreases a certain distance metric to it”. We show that connected row convex (CRC) constraints, arc-consistent consecutive tree convex (ACCTC) constraints, etc fit this characterization, and are therefore amenable to extremely simple polynomial-time randomized algorithms—the complexities of which are shown to be much less than that of the corresponding (known) deterministic algorithms and the (generic) lower bounds for establishing path-consistency. On a related note, we also provide a simple polynomial-time deterministic algorithm for finding tree embeddings of variable domains (if they exist) for establishing tree convexity in pathconsistent networks.

AAAI Conference 2006 Conference Paper

Tractable Classes of Metric Temporal Problems with Domain Rules

• T. K. Satish Kumar

In this paper, we will deal with some important kinds of metric temporal reasoning problems that arise in many real-life situations. In particular, events X0, X1. .. XN are modeled as time points, and a constraint between the execution times of two events Xi and Xj is either simple temporal (of the form Xi − Xj ∈ [a, b]), or has a connected feasible region that can be expressed using a finite set of domain rules each in turn of the form Xi ∈ [a, b] → Xj ∈ [c, d] (and conversely Xj ∈ [e, f] → Xi ∈ [g, h]). We argue that such rules are useful in capturing important kinds of non-monotonic relationships between the execution times of events when they are governed by potentially complex (external) factors. Our polynomial-time (deterministic and randomized) algorithms for solving such problems therefore enable us to efficiently deal with very expressive representations of time.

ICAPS Conference 2005 Conference Paper

On the Tractability of Restricted Disjunctive Temporal Problems

• T. K. Satish Kumar

In this paper, we provide a polynomial-time deterministic algorithm, and an even simpler randomized algorithm, for solving a restricted (but very expressive) class of disjunctive temporal problems (DTPs). The general form of a DTP is as follows. We are given a set of events X = (X0 is the "beginning of the world" node and is set to 0 by convention), and a set of constraints C. A constraint ci in C is a disjunction of the form s(i, 1) or s(i, 2)... s(i, Ti). Here, s(i, j) (1 ⇐ j ⇐ Ti) is a simple temporal constraint of the form L(i, j) ⇐ X{b(i, j)} – X{a(i, j)} ⇐ U(i, j) for 0 ⇐ a(i, j), b(i, j) ⇐ N. We will first provide a pseudo-polynomial-time randomized algorithm for solving the following restricted class of DTPs (which we will refer to as RDTPs (restricted DTPs)): Any ci in C is of one of the following types: (Type 1) (L ⇐ Xb – Xa ⇐ U), (Type 2) (L1 ⇐ Xa ⇐ U1) or (L2 ⇐ Xa ⇐ U2)... (L{Ti} ⇐ Xa ⇐ U{Ti}), (Type 3) (L1 ⇐ Xa ⇐ U1) or (L2 ⇐ Xb ⇐ U2). We will then provide a strongly polynomial-time deterministic algorithm for solving the same problem, and extend the ideas further to provide an even simpler randomized algorithm---the expected running time of which is much less than that of the deterministic algorithm. Our polynomial-time algorithms for solving RDTPs bear important implications on not only being able to handle limited (but very useful) forms of disjunctions in metric temporal reasoning (that would otherwise require an exponential search space), but also in pruning large parts of the search spaces associated with general DTPs.

AAAI Conference 2004 Conference Paper

A Polynomial-Time Algorithm for Simple Temporal Problems with Piecewise Constant Domain Preference Functions

• T. K. Satish Kumar

In this paper, we provide a polynomial-time algorithm for solving an important class of metric temporal problems that involve simple temporal constraints between various events (variables) and piecewise constant preference functions over variable domains. We are given a graph G = hX, Ei where X = {X0, X1. .. Xn} is a set of events (X0 is the “beginning of the world” node and is set to 0 by convention) and e = hXi, Xj i ∈ E, annotated with the bounds [LB(e), UB(e)], is a simple temporal constraint between Xi and Xj indicating that Xj must be scheduled between LB(e) and UB(e) seconds after Xi is scheduled (LB(e) ≤ UB(e)). A family of stepwise constant preference functions F = {fXi (t): R → R} specifies the preference attached with scheduling Xi at time t. The goal is to find a schedule for all the events such that all the temporal constraints are satisfied and the sum of the preferences is maximized. Our polynomial-time algorithm for solving such problems (which we refer to as extended simple temporal problems (ESTPs)) has important consequences in dealing with limited forms of disjunctions and preferences in metric temporal reasoning that would otherwise require an exponential search space.