Author name cluster

Xing Tan

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.

4 papers

1 author row

AAAI Conference 2026 Conference Paper

Inapproximability of STRIPS Planning

Xing Tan
Alban Grastien

Automated planning involves finding a sequence of actions that changes the world from an initial state to a final state with goals satisfied. The general problem is PSPACE-hard. Nevertheless, many restricted variants are NP-complete or even in P. Existing complexity work focuses mostly on plan existence, or plan with minimal plan length. Little is known about optimization variants that aim to satisfy as many goal conditions as possible. In this paper, we aim to fill this gap by providing a first inapproximability study of goal-maximization using the classical STRIPS formalism. For MAXPLANSAT and its length-bounded counterpart MAXPLANSAT(K), we prove tight constant-factor lower bounds. More specifically, through performing L-reductions from MAXE3SAT and MAX3DM, we show several of these problems are inapproximable by a constant factor, unless P=NP.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Inapproximability of Optimal Multi-Agent Pathfinding Problems

Xing Tan
Alban Grastien

Multi-agent pathfinding MAPF is a problem where multiple autonomous agents must find paths to their respective destinations without colliding. Decisional MAPF on undirected graphs can be solved in polynomial time; Several optimization MAPF variants however are NP-complete. The directed graph variant (diMAPF) is more complex, with its decisional version already being NP-complete. This paper examines the computational approximability of optimal MAPF problems (i.e., minimizing makespan for agent travel distance and maximizing the total number of agents reaching their goals), providing a first set of several inapproximability results for these problems. The results reveal an inherent limitation in approximating optimal solutions for MAPFs, provide a deeper understanding regarding their computational intractability, thus offer foundational references for future research.

PDF Details DOI

AAAI Conference 2021 Conference Paper

A Complexity-theoretic Analysis of Green Pickup-and-Delivery Problems

Xing Tan
Jimmy Xiangji Huang

In a Green Pickup-and-Delivery problem (GPD), vehicles traveling in a transport network achieving pickup-anddelivery tasks are in particular subject to the two green constraints: limited vehicle fuel capacity thus short vehicle traveling range, and limited availability of refueling infrastructure for the vehicles. GPD adds additional but probably insignificant computational complexity to the classic and already NP-hard Pickup-and-Delivery problem and Vehicle Routing Problem. Nevertheless, we demonstrate in this paper an inherent intractability of these green components themselves. More precisely, we show that GPD problems whose total constraints are reduced to almost the green ones only, remain to be NP-complete in the strong sense. We figure out a specifically constrained variant of GPD that, however, is weakly NP-complete – a practical pseudo-polynomial time algorithm solving the variant problem is identified. Insight obtained from this complexity-theoretic analysis would shed light for a deeper understanding of GPDs, and on better development of heuristics for solving these problems, leading to promisingly many real-world applications.

PDF Details

IJCAI Conference 2019 Conference Paper

On Computational Complexity of Pickup-and-Delivery Problems with Precedence Constraints or Time Windows

Xing Tan
Jimmy Xiangji Huang

Pickup-and-Delivery (PD) problems consider routing vehicles to achieve a set of tasks related to ``Pickup'', and to ``Delivery''. Meanwhile these tasks might subject to Precedence Constraints (PDPC) or Time Windows (PDTW). PD is a variant to Vehicle Routing Problems (VRP), which have been extensively studied for decades. In the recent years, PD demonstrates its closer relevance to AI. With an awareness that few work has been dedicated so far in addressing where the tractability boundary line can be drawn for PD problems, we identify in this paper a set of highly restricted PD problems and prove their NP-completeness. Many problems from a multitude of applications and industry domains are general versions of PDPC. Thus this new result of NP-hardness, of PDPC, not only clarifies the computational complexity of these problems, but also sets up a firm base for the requirement on use of approximation or heuristics, as opposed to looking for exact but intractable algorithms for solving them. We move on to perform an empirical study to locate sources of intractability in PD problems. That is, we propose a local-search formalism and algorithm for solving PDPC problems in particular. Experimental results support strongly effectiveness and efficiency of the local-search. Using the local-search as a solver for randomly generated PDPC problem instances, we obtained interesting and potentially useful insights regarding computational hardness of PDPC and PD.

PDF Details