GenAI4ELab/papercli-papers huggingface dataset:
Inapproximability of STRIPS Planning
Authors: Xing Tan; Alban Grastien
Venue: AAAI 2026 (main)

Abstract: 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.
Symmetries and Other Variations of “End-Recursive” HTN Problems: Mapping the Border Between Decidable and Undecidable Restrictions
Authors: Hadyn Tang; Pascal Bercher
Venue: AAAI 2026 (main)

Abstract: In this paper, we investigate the complexity of determining if various restricted forms of hierarchical task network (HTN) planning have a plan. We perform a systematic analysis of new restrictions formed by applying symmetries and relaxations to two existing restrictions called regularity and tail-recursiveness. By doing so, we confirm that many variations on common restrictions do not affect the complexity of the plan existence problem. However, we also obtain the counter-intuitive result that combining some of these seemingly inert relaxations together renders the plan existence problem undecidable. Additionally, we unearth a critical difference in definitions between an early paper on HTN planning and modern formalisms that appears to have gone unnoticed.
GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets
Authors: Jingtao Tang; Hang Ma
Venue: AAAI 2026 (main)

Abstract: We study GCS-TSP, a variant of the Traveling Salesman Problem (TSP) defined over a Graph of Convex Sets (GCS) - a powerful representation for trajectory planning that decomposes the configuration space into convex regions connected by a sparse graph. In GCS-TSP, edge costs are not fixed but depend on the specific trajectory passing through each convex region, making classical TSP methods inapplicable. We introduce GHOST, a hierarchical framework that optimally solves GCS-TSP by combining combinatorial tour search with convex trajectory optimization. GHOST systematically explores tours on a complete graph induced by the GCS, using a novel abstract-path-unfolding algorithm to compute admissible lower bounds that guide best-first search at both the high level (over tours) and the low level (over feasible GCS paths realizing the tour). These bounds provide strong pruning power, reducing unnecessary optimization calls. We prove that GHOST guarantees optimality and present a bounded-suboptimal variant for time-critical settings. Experiments show that GHOST is orders-of-magnitude faster than unified mixed-integer convex programming baseline while uniquely handling complex problems involving high-order continuity constraints and incomplete GCSs.
Dominance Pruning and Heuristics in Optimal Adversarial Non-Deterministic Planning
Authors: Rasmus G. Tollund; Álvaro Torralba
Venue: AAAI 2026 (main)

Abstract: In many planning problems there are non-deterministic actions for which the outcome cannot be fully controlled by the planning agent. For critical tasks, we need to find a strategy  that achieves the goal within a predictable time-frame and/or cost. Thus, we consider an adversarial planning setting and compute optimal policies that optimize the worst-case cost to reach the goal.
  
  In this work, we introduce domain-independent optimal heuristic search algorithms for this adversarial setting. To guide the search, we show how to leverage classical planning heuristics by applying single-outcome determinization. We also generalize dominance techniques, that analyse when a state is as good as another, to the non-deterministic setting and apply them to prune the search space. Our experimental analysis shows that both methods greatly help to compute optimal policies across multiple domains.
Probabilistic Safety Verification of Neural Policies via Predicate Abstraction
Authors: Marcel Vinzent; Holger Hermanns; Jörg Hoffmann
Venue: AAAI 2026 (main)

Abstract: Neural networks are increasingly important to learn action policies. Policy predicate abstraction (PPA) verifies safety of such a neural policy pi by over-approximating the state space subgraph induced by pi and using counterexample-guided abstraction refinement (CEGAR) to iteratively refine the abstraction. So far, PPA verifies safety in non-deterministic systems. This work extends PPA to probabilistic verification. Extending the abstract state space computation is relatively straightforward. Abstraction refinement, however, becomes substantially more complex, due to the more intricate form of counterexamples and the various sources of spuriousness it entails. We tackle this challenge by drawing inspiration from prior work on probabilistic CEGAR, empowering it to deal with neural pi. The resulting algorithm decides whether pi is safe with respect to a desired upper bound on unsafety probability. Invoking the algorithm incrementally, we can also derive upper and lower bounds automatically. Our experiments show that these algorithms can derive non-trivial bounds, whereas encodings into state-of-the-art probabilistic model checkers turn out to be ineffective.
History-Aware Reasoning for GUI Agents
Authors: Ziwei Wang; Leyang Yang; Xiaoxuan Tang; Sheng Zhou; Dajun Chen; Wei Jiang; Yong Li
Venue: AAAI 2026 (main)

Abstract: Advances in Multimodal Large Language Models have significantly enhanced Graphical User Interface (GUI) automation. Equipping GUI agents with reliable episodic reasoning capabilities is essential for bridging the gap between users’ concise task descriptions and the complexities of real-world execution. Current methods integrate Reinforcement Learning (RL) with System-2 Chain-of-Thought, yielding notable gains in reasoning enhancement. For long-horizon GUI tasks, historical interactions connect each screen to the goal-oriented episode chain, and effectively leveraging these clues is crucial for the current decision. However, existing native GUI agents exhibit weak short-term memory in their explicit reasoning, interpreting the chained interactions as discrete screen understanding, i.e., unawareness of the historical interactions within the episode. This history-agnostic reasoning challenges their performance in GUI automation. To alleviate this weakness, we propose a History-Aware Reasoning (HAR) framework, which encourages an agent to reflect on its own errors and acquire episodic reasoning knowledge from them via tailored strategies that enhance short-term memory in long-horizon interaction. The framework mainly comprises constructing a reflective learning scenario, synthesizing tailored correction guidelines, and designing a hybrid RL reward function. Using the HAR framework, we develop a native end-to-end model, HAR-GUI-3B, which alters the inherent reasoning mode from history-agnostic to history-aware, equipping the GUI agent with stable short-term memory and reliable perception of screen details. Comprehensive evaluations across a range of GUI-related benchmarks demonstrate the effectiveness and generalization of our method.
Good-for-MDP State Reduction for Stochastic LTL Planning
Authors: Christoph Weinhuber; Giuseppe De Giacomo; Yong Li; Sven Schewe; Qiyi Tang
Venue: AAAI 2026 (main)

Abstract: We study stochastic planning problems in Markov Decision Processes (MDPs) with goals specified in Linear Temporal Logic (LTL). The state-of-the-art approach transforms LTL formulas into good-for-MDP (GFM) automata, which feature a restricted form of nondeterminism. These automata are then composed with the MDP, allowing the agent to resolve the nondeterminism during policy synthesis. A major factor affecting the scalability of this approach is the size of the generated automata. In this paper, we propose a novel GFM state-space reduction technique that significantly reduces the number of automata states. Our method employs a sophisticated chain of transformations, leveraging recent advances in good-for-games minimisation developed for adversarial settings. In addition to our theoretical contributions, we present empirical results demonstrating the practical effectiveness of our state-reduction technique. Furthermore, we introduce a direct construction method for formulas of the form GFφ, where φ is a co-safety formula. This construction is provably single-exponential in the worst case, in contrast to the general doubly-exponential complexity. Our experiments confirm the scalability advantages of this specialised construction.
Online Capacitated General Matching with Knapsack
Authors: Ruoyu Wu; Wei Bao; Ben Liang; Hequn Wang
Venue: AAAI 2026 (main)

Abstract: We study a new online matching problem termed Online Capacitated General Matching with Knapsack (OCGMK), which generalizes the Online General Matching (OGM) problem. In the original OGM, vertices arrive sequentially and need to be paired with other vertices to maximize the total reward of pairing. Our study is the first to consider capacitated vertices in OGM: we allow each vertex to be assigned to multiple vertices up to a capacity limit. We also consider a previously unexamined knapsack constraint in OGM: assigning a pair of vertices has a cost, but the total cost is budgeted. To solve the OCGMK problem, we propose the Online Capacity-Knapsack Assignment (OCKA) algorithm, which constructs capacity-friendly sets and knapsack-friendly sets to simultaneously and effectively address both constraints. OCKA achieves a competitive ratio of ⍺=?/2?, where ?=1/(3+e^(-2)) and ? is the ratio between the overall cost of all edges and the cost budget. When the knapsack constraint is not imposed but the capacitated vertices remain, the competitive ratio of OCKA is ⍺'=1/2, recovering the previous best result for single-capacity OGM. We implement trace-driven experiments to evaluate the practical performance of OCKA on a real-world dating dataset, demonstrating the superior performance of OCKA in online dating applications.
Matching Policy Design for Gig Platforms with “Priority” Features
Authors: Evan Yifan Xu; Pan Xu
Venue: AAAI 2026 (main)

Abstract: In recent years, gig platforms like Uber and DoorDash have implemented strategies to boost gig drivers' earnings during peak hours. Uber's 'back-to-back' feature allows drivers to accept new trips while still on route, and Uber Eats' 'Batch Order Route' initiative allows drivers to pick up multiple deliveries from different locations, which may result in multiple tops before one order is delivered. Despite revenue gains, these features lead to user complaints about extended waiting times. In response, platforms introduce features like Uber Eats' 'Priority Delivery' and Uber's 'Priority', where customers pay an extra subscription fee for guaranteed reduced waiting times.
This paper focuses on designing matching policies to enhance system revenue while limiting customer waiting times. We present a hybrid model combining online matching and queue theory for quantitative analysis of users' waiting times. Additionally, we introduce an LP-based sampling framework and a unified queue-theory-based method for evaluating online performance. Comprehensive experiments on real datasets validate our theoretical findings, highlighting the efficiency of our matching framework in promoting profit and meeting committed waiting times.
Breaking Model Lock-in: Cost-Efficient Zero-Shot LLM Routing via a Universal Latent Space
Authors: Cheng Yan; Wuyang Zhang; Zhiyuan Ning; Fan Xu; Ziyang Tao; Lu Zhang; Bing Yin; Yanyong Zhang
Venue: AAAI 2026 (main)

Abstract: The rapid proliferation of Large Language Models (LLMs) has led to a fragmented and inefficient ecosystem, a state of ``model lock-in'' where seamlessly integrating novel models remains a significant bottleneck. Current routing frameworks require exhaustive, costly retraining, hindering scalability and adaptability. We introduce ZeroRouter, a new paradigm for LLM routing that breaks this lock-in. Our approach is founded on a universal latent space, a model-agnostic representation of query difficulty that fundamentally decouples the characterization of a query from the profiling of a model. This allows for zero-shot onboarding of new models without full-scale retraining. ZeroRouter features a context-aware predictor that maps queries to this universal space and a dual-mode optimizer that balances accuracy, cost, and latency. Our framework consistently outperforms all baselines, delivering higher accuracy at lower cost and latency.
Optimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks
Authors: Ruixiao Yang; Chuchu Fan
Venue: AAAI 2026 (main)

Abstract: The mixed truck-drone delivery system has attracted increasing attention for its potential to optimize last-mile logistics. While the Flying Sidekick Traveling Salesman Problem (FSTSP) provides a foundation for modeling the truck-drone collaboration, it falls short of capturing real-world complexities by assuming a single truck-drone pair operating on a fully connected graph. We introduce the Multi-Agent FSTSP (MA-FSTSP), which extends FSTSP to handle multiple trucks, each carrying multiple drones operating over real road networks. Trucks must follow roads, while drones can fly directly between locations. To solve this NP-hard problem efficiently, we propose a novel three-phase algorithm that first partitions customers using a set-based distance heuristic, then computes initial truck routes via a Set TSP formulation, and finally optimizes drone deployment patterns by dynamic programming. Through extensive experiments on real-world road networks from Manhattan (1,024 nodes) and Boston (11,000 nodes), we demonstrate that our method achieves more than 30% cost reduction compared to existing approaches while scaling effectively to problems with 150 customers within a 20-minute computational time-bound.
Scalable Solution Methods for Dec-POMDPs with Deterministic Dynamics
Authors: Yang You; Alex Schutz; Zhikun Li; Bruno Lacerda; Robert Skilton; Nick Hawes
Venue: AAAI 2026 (main)

Abstract: Many high-level multi-agent planning problems, such as multi-robot navigation and path planning, can be modeled with deterministic actions and observations. In this work, we focus on such domains and introduce the class of Deterministic Decentralized POMDPs (Det-Dec-POMDPs)—a subclass of Dec-POMDPs with deterministic transitions and observations given the state and joint actions. We then propose a practical solver, Iterative Deterministic POMDP Planning (IDPP), based on the classic Joint Equilibrium Search for Policies framework, specifically optimized to handle large-scale Det-Dec-POMDPs that existing Dec-POMDP solvers cannot handle efficiently.
Learning to Optimize Job Shop Scheduling Under Structural Uncertainty
Authors: Rui Zhang; Jianwei Niu; Xuefeng Liu; Shaojie Tang; Jing Yuan
Venue: AAAI 2026 (main)

Abstract: The Job-Shop Scheduling Problem (JSSP), under various forms of manufacturing uncertainty, has recently attracted considerable research attention. Most existing studies focus on parameter uncertainty, such as variable processing times, and typically adopt the actor-critic framework. In this paper, we explore a different but prevalent form of uncertainty in JSSP: structural uncertainty. Structural uncertainty arises when a job may follow one of several routing paths, and the selection is determined not by policy, but by situational factors (e.g., the quality of intermediate products) that cannot be known in advance. Existing methods struggle to address this challenge due to incorrect credit assignment: a high-quality action may be unfairly penalized if it is followed by a time-consuming path. To address this problem, we propose a novel method named UP-AAC. In contrast to conventional actor-critic methods, UP-AAC employs an asymmetric architecture. While its actor receives a standard stochastic state, the critic is crucially provided with a deterministic state reconstructed in hindsight. This design allows the critic to learn a more accurate value function, which in turn provides a lower-variance policy gradient to the actor, leading to more stable learning. In addition, we design an attention-based Uncertainty Perception Model (UPM) to enhance the actor's scheduling decisions. Extensive experiments demonstrate that our method outperforms existing approaches in reducing makespan on benchmark instances.
Automating Complex Document Workflows via Stepwise and Rollback-Enabled Operation Orchestration
Authors: Yanbin Zhang; Hanhui Ye; Yue Bai; Qiming Zhang; Liao Xiang; Wu Mianzhi; Renjun Hu
Venue: AAAI 2026 (main)

Abstract: Workflow automation promises substantial productivity gains in everyday document-related tasks. While prior agentic systems can execute isolated instructions, they struggle with automating multi-step, session-level workflows due to limited control over the operational process. To this end, we introduce AutoDW, a novel execution framework that enables stepwise, rollback-enabled operation orchestration. AutoDW incrementally plans API actions conditioned on user instructions, intent-filtered API candidates, and the evolving states of the document. It further employs robust rollback mechanisms at both the argument and API levels, enabling dynamic correction and fault tolerance. These designs together ensure that the execution trajectory of AutoDW remains aligned with user intent and document context across long-horizon workflows. To assess its effectiveness, we construct a comprehensive benchmark of 250 sessions and 1,708 human-annotated instructions, reflecting realistic document processing scenarios with interdependent instructions. AutoDW achieves 90% and 62% completion rates on instruction- and session-level tasks, respectively, outperforming strong baselines by 40% and 76%. Moreover, AutoDW also remains robust for the decision of backbone LLMs and on tasks with varying difficulty.
SPIRAL: Symbolic LLM Planning via Grounded and Reflective Search
Authors: Yifan Zhang; Giridhar Ganapavarapu; Srideepika Jayaraman; Bhavna Agrawal; Dhaval Patel; Achille Fokoue
Venue: AAAI 2026 (main)

Abstract: Large Language Models (LLMs) often falter at complex planning tasks that require exploration and self-correction, as their linear reasoning process struggles to recover from early mistakes. While search algorithms like Monte Carlo Tree Search (MCTS) can explore alternatives, they are often ineffective when guided by sparse rewards and fail to leverage the rich semantic capabilities of LLMs. We introduce SPIRAL (Symbolic LLM Planning via Grounded and Reflective Search), a novel framework that embeds a cognitive architecture of three specialized LLM agents into an MCTS loop. SPIRAL's key contribution is its integrated planning pipeline where a Planner proposes creative next steps, a Simulator grounds the search by predicting realistic outcomes, and a Critic provides dense reward signals through reflection. This synergy transforms MCTS from a brute-force search into a guided, self-correcting reasoning process. On the DailyLifeAPIs and HuggingFace datasets, SPIRAL consistently outperforms the default Chain-of-Thought planning method and other state-of-the-art agents. More importantly, it substantially surpasses other state-of-the-art agents; for example, SPIRAL achieves 83.6% overall accuracy on DailyLifeAPIs, an improvement of over 16 percentage points against the next-best search framework, while also demonstrating superior token efficiency. Our work demonstrates that structuring LLM reasoning as a guided, reflective, and grounded search process yields more robust and efficient autonomous planners. The source code, full appendices, and all experimental data are available for reproducibility at the official project repository.
VipAct: Visual-Perception Enhancement via Specialized VLM Agent Collaboration and Tool-use
Authors: Zhehao Zhang; Ryan A. Rossi; Tong Yu; Franck Dernoncourt; Ruiyi Zhang; Jiuxiang Gu; Sungchul Kim; Xiang Chen; Zichao Wang; Nedim Lipka
Venue: AAAI 2026 (main)

Abstract: While vision-language models (VLMs) have demonstrated remarkable performance across various tasks combining textual and visual information, they continue to struggle with fine-grained visual perception tasks that require detailed pixel-level analysis. Effectively eliciting comprehensive reasoning from VLMs on such intricate visual elements remains an open challenge. In this paper, we present VipAct, an agent framework that enhances VLMs by integrating multi-agent collaboration and vision expert models, enabling more precise visual understanding and comprehensive reasoning. VipAct consists of an orchestrator agent, which manages task requirement analysis, planning, and coordination, along with specialized agents that handle specific tasks such as image captioning and vision expert models that provide high-precision perceptual information. This multi-agent approach allows VLMs to better perform fine-grained visual perception tasks by synergizing planning, reasoning, and tool use. We evaluate VipAct on benchmarks featuring a diverse set of visual perception tasks, with experimental results demonstrating significant performance improvements over state-of-the-art baselines across all tasks. Furthermore, comprehensive ablation studies reveal the critical role of multi-agent collaboration in eliciting more detailed System-2 reasoning and highlight the importance of image input for task planning. Additionally, our error analysis identifies patterns of VLMs' inherent limitations in visual perception, providing insights into potential future improvements. VipAct offers a flexible and extensible framework, paving the way for more advanced visual perception systems across various real-world applications.
A TSP-Based Algorithm for Multi-League Traveling Tournament
Authors: Jingyang Zhao; Mingyu Xiao; Ken-Ichi Kawarabayashi
Venue: AAAI 2026 (main)

Abstract: In some professional sports leagues, inter-league games are scheduled among multiple divisions or conferences. This inspired us to study the p-partite Traveling Tournament Problem (p-partite TTP), where teams are partitioned into p leagues, and each team plays games against teams from different leagues. Previously, only the case of p=2, known as the Bipartite TTP or BTTP, has been introduced and studied.

In this paper, we show that the p-partite TTP is NP-hard for any fixed p≥3, and we propose an efficient algorithm based on a solution to the Traveling Salesman Problem. Furthermore, we prove that the algorithm achieves a notable approximation ratio of 8/3+O(1/n) when p=3. We also conduct experiments demonstrating that the algorithm produces practical schedules with significantly reduced total travel distances, highlighting its effectiveness in generating high-quality multipartite tournament schedules.
Improved Algorithms for Trip-Vehicle Assignment in Ride-Sharing
Authors: Jingyang Zhao; Mingyu Xiao; Yonghang Su
Venue: AAAI 2026 (main)

Abstract: The Ride-Sharing Assignment Problem (AAAI 2018) is a fundamental problem in intelligent transportation systems, urban mobility, and algorithmic decision-making. Given a set of m vehicles with initial locations and n requests (n≤mk), each with a specified origin and destination, the goal is to assign at most k requests to each vehicle and compute corresponding routes that minimize the total travel distance. The algorithmic approach depends on whether n=mk or n