Routing and Scheduling in Answer Set Programming applied to Multi-Agent Path Finding: Preliminary Report

• URL: http://arxiv.org/abs/2403.12153v1
• Date: Mon, 18 Mar 2024 18:09:47 GMT
• Title: Routing and Scheduling in Answer Set Programming applied to Multi-Agent Path Finding: Preliminary Report
• Abstract summary: We present alternative approaches to routing and scheduling in Answer Set Programming (ASP) The idea is to capture the flow of time in terms of partial orders rather than time steps attached to actions and fluents. This also abolishes the need for fixed upper bounds on the length of plans.
• Score: 1.2864531964337733
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present alternative approaches to routing and scheduling in Answer Set Programming (ASP), and explore them in the context of Multi-agent Path Finding. The idea is to capture the flow of time in terms of partial orders rather than time steps attached to actions and fluents. This also abolishes the need for fixed upper bounds on the length of plans. The trade-off for this avoidance is that (parts of) temporal trajectories must be acyclic, since multiple occurrences of the same action or fluent cannot be distinguished anymore. While this approach provides an interesting alternative for modeling routing, it is without alternative for scheduling since fine-grained timings cannot be represented in ASP in a feasible way. This is different for partial orders that can be efficiently handled by external means such as acyclicity and difference constraints. We formally elaborate upon this idea and present several resulting ASP encodings. Finally, we demonstrate their effectiveness via an empirical analysis.

Related papers

• Before Thinking, Learn to Decide: Proactive Routing for Efficient Visual Reasoning [87.18590662029432]
  We propose PRP, a Proactive Routing Paradigm that enables early decision-making by jointly evaluating the competence of both the draft and target models.<n>Our draft Rating Learning (DRL) equips the draft model with an internal confidence estimator, while Joint Rating Learning (JRL) predicts how well the target model can handle a given query.<n>These ratings enable fine-grained, instance-level textbfProactive Routing and substantially accelerate inference without compromising overall performance.
  arXiv  Detail & Related papers  (2026-06-29T12:30:24Z)
• TempAct: Advancing Temporal Plausibility in Autoregressive Video Generation via Planner-Executor RL [72.7712729541565]
  Autoregressive (AR) video diffusion models enable low-latency streaming generation by synthesizing videos chunk by chunk with cached visual context.<n>A single global prompt does not specify which sub-event should be realized in each chunk, while naively switching to step-wise prompts often leads to delayed reactions, blended step semantics, and error propagation across prompt transitions.<n>We address these challenges with TempAct, a planner--executor reinforcement learning framework that jointly optimize temporal decomposition and step-conditioned execution for temporally plausible AR video generation.
  arXiv  Detail & Related papers  (2026-06-26T12:19:28Z)
• From Agent Loops to Structured Graphs:A Scheduler-Theoretic Framework for LLM Agent Execution [1.8222732878503212]
  The dominant paradigm for building LLM based agents is the Agent Loop, an iterative cycle where a single language model decides what to do next by reading an ever growing context window.<n>This perspective places Agent Loops and graph based execution engines on a single semantic continuum.<n>We propose SGH, which lifts control flow from implicit context into an explicit static DAG.
  arXiv  Detail & Related papers  (2026-04-13T12:16:45Z)
• PseudoAct: Leveraging Pseudocode Synthesis for Flexible Planning and Action Control in Large Language Model Agents [5.5917393750392925]
  Large language model (LLM) agents typically rely on reactive decision-making paradigms such as ReAct.<n>This paper introduces PseudoAct, a novel framework for flexible planning and action control in LLM agents through pseudocode synthesis.<n> Experiments on benchmark datasets show that our method significantly outperforms existing reactive agent approaches.
  arXiv  Detail & Related papers  (2026-02-27T04:30:45Z)
• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPE is a framework that disentangles query-specific reasoning from generic code execution.<n>SCOPE achieves state-of-the-art performance while lowering cost and latency.
  arXiv  Detail & Related papers  (2026-01-14T02:58:07Z)
• Beyond Entangled Planning: Task-Decoupled Planning for Long-Horizon Agents [28.061156787350395]
  Task-Decoupled Planning (TDP) is a training-free framework that replaces entangled reasoning with task decoupling.<n>TDP confines reasoning and replanning to the active sub-task without disrupting the workflow.<n>Results on TravelPlanner, ScienceWorld, and HotpotQA show that TDP outperforms strong baselines while reducing token consumption by up to 82%.
  arXiv  Detail & Related papers  (2026-01-12T14:30:10Z)
• Compiling Metric Temporal Answer Set Programming [2.3861066707217202]
  A central challenge is to maintain scalability when dealing with fine-grained timing constraints.<n>We leverage extensions of ASP with difference constraints, a simplified form of linear constraints, to handle time-related aspects externally.<n>Our approach effectively decouples metric ASP from the granularity of time, resulting in a solution that is unaffected by time precision.
  arXiv  Detail & Related papers  (2025-06-09T18:56:57Z)
• Recursive Decomposition with Dependencies for Generic Divide-and-Conquer Reasoning [48.829971427616854]
  We introduce Recursive Decomposition with Dependencies (RDD), a scalable divide-and-conquer method for solving reasoning problems.<n>RDD can be directly applied to a new problem class even in the absence of any task-specific guidance.<n>We evaluate our approach on two benchmarks with six difficulty levels each and in two in-context settings.
  arXiv  Detail & Related papers  (2025-05-05T11:24:20Z)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  We present Recipe2Plan, a novel benchmark framework based on real-world cooking scenarios. Unlike conventional benchmarks, Recipe2Plan challenges agents to optimize cooking time through parallel task execution.
  arXiv  Detail & Related papers  (2025-03-04T03:27:02Z)
• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents. Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• Diffusion Meets Options: Hierarchical Generative Skill Composition for Temporally-Extended Tasks [12.239868705130178]
  We propose a data-driven hierarchical framework that generates and updates plans based on instruction specified by linear temporal logic (LTL) Our method decomposes temporal tasks into chain of options with hierarchical reinforcement learning from offline non-expert datasets. We devise a determinantal-guided posterior sampling technique during batch generation, which improves the speed and diversity of diffusion generated options.
  arXiv  Detail & Related papers  (2024-10-03T11:10:37Z)
• Temporally Grounding Instructional Diagrams in Unconstrained Videos [51.85805768507356]
  We study the challenging problem of simultaneously localizing a sequence of queries in instructional diagrams in a video. Most existing methods focus on grounding one query at a time, ignoring the inherent structures among queries. We propose composite queries constructed by exhaustively pairing up the visual content features of the step diagrams. We demonstrate the effectiveness of our approach on the IAW dataset for grounding step diagrams and the YouCook2 benchmark for grounding natural language queries.
  arXiv  Detail & Related papers  (2024-07-16T05:44:30Z)
• Deciphering Movement: Unified Trajectory Generation Model for Multi-Agent [53.637837706712794]
  We propose a Unified Trajectory Generation model, UniTraj, that processes arbitrary trajectories as masked inputs. Specifically, we introduce a Ghost Spatial Masking (GSM) module embedded within a Transformer encoder for spatial feature extraction. We benchmark three practical sports game datasets, Basketball-U, Football-U, and Soccer-U, for evaluation.
  arXiv  Detail & Related papers  (2024-05-27T22:15:23Z)
• A Formal Metareasoning Model of Concurrent Planning and Execution [22.963769931698874]
  This work lays the foundation for a principled time-aware executive that concurrently plans and executes. We identify special cases that are solvable in time, develop greedy solution algorithms, and, through tests on instances derived from search problems, find several methods that achieve promising practical performance.
  arXiv  Detail & Related papers  (2023-03-05T13:05:26Z)
• Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling [18.286430978487388]
  We deal with a challenging scheduling problem on parallel machines with sequence-dependent setup times and release dates. We put the individual machine spans in non-ascending order and lexicographically minimise the resulting robustnesss. Our experimental results show that ASP is indeed a promising KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers.
  arXiv  Detail & Related papers  (2022-12-18T12:43:24Z)
• Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling [7.977161233209228]
  Job-shop Scheduling Problem (JSP) is a well-known and challenging optimization problem in which tasks sharing a machine are to be arranged in a sequence such that encompassing jobs can be completed as early as possible. In this paper, we investigate problem decomposition into time windows whose operations can be successively scheduled and optimized by means of multi-shot Answer Set Programming (ASP) solving.
  arXiv  Detail & Related papers  (2022-05-16T09:33:00Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay. We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
  arXiv  Detail & Related papers  (2021-05-01T10:18:34Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks. One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
  arXiv  Detail & Related papers  (2020-10-11T14:39:50Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• Query Resolution for Conversational Search with Limited Supervision [63.131221660019776]
  We propose QuReTeC (Query Resolution by Term Classification), a neural query resolution model based on bidirectional transformers. We show that QuReTeC outperforms state-of-the-art models, and furthermore, that our distant supervision method can be used to substantially reduce the amount of human-curated data required to train QuReTeC.
  arXiv  Detail & Related papers  (2020-05-24T11:37:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.