Author name cluster

T. K. Kumar

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.

2 papers

1 author row

AAAI Conference 2016 Conference Paper

Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem

Hang Ma
Craig Tovey
Guni Sharon
T. K. Kumar
Sven Koenig

We study transportation problems where robots have to deliver packages and can transfer the packages among each other. Speciﬁcally, we study the package-exchange robotrouting problem (PERR), where each robot carries one package, any two robots in adjacent locations can exchange their packages, and each package needs to be delivered to a given destination. We prove that exchange operations make all PERR instances solvable. Yet, we also show that PERR is NP-hard to approximate within any factor less than 4/3 for makespan minimization and is NP-hard to solve for ﬂowtime minimization, even when there are only two types of packages. Our proof techniques also generate new insights into other transportation problems, for example, into the hardness of approximating optimal solutions to the standard multiagent path-ﬁnding problem (MAPF). Finally, we present optimal and suboptimal PERR solvers that are inspired by MAPF solvers, namely a ﬂow-based ILP formulation and an adaptation of conﬂict-based search. Our empirical results demonstrate that these solvers scale well and that PERR instances often have smaller makespans and ﬂowtimes than the corresponding MAPF instances.

PDF Details

AAAI Conference 2013 Conference Paper

Simple Temporal Problems with Taboo Regions

T. K. Kumar
Marcello Cirillo
Sven Koenig

In this paper, we define and study the general framework of Simple Temporal Problems with Taboo regions (STPTs) and show how these problems capture metric temporal reasoning aspects which are common to many real-world applications. STPTs encode simple temporal constraints between events and user-defined taboo regions on the timeline, during which no event is allowed to take place. We discuss two different variants of STPTs. The first one deals with (instantaneous) events, while the second one allows for (durative) processes. We also provide polynomial-time algorithms for solving them. If all events or processes cannot be scheduled outside of the taboo regions, one needs to define and reason about “soft” STPTs. We show that even “soft” STPTs can be solved in polynomial time, using reductions to max-flow problems. The resulting algorithms allow for incremental computations, which is important for the successful application of our approach in realtime domains.

PDF Details