Efficient Temporal Piecewise-Linear Numeric Planning with Lazy Consistency Checking

• URL: http://arxiv.org/abs/2105.10176v1
• Date: Fri, 21 May 2021 07:36:54 GMT
• Title: Efficient Temporal Piecewise-Linear Numeric Planning with Lazy Consistency Checking
• Authors: Josef Bajada, Maria Fox and Derek Long
• Abstract summary: We propose a set of techniques that allow the planner to compute LP consistency checks lazily where possible. We also propose an algorithm to perform duration-dependent goal checking more selectively. The resultant planner is not only more efficient, but outperforms most state-of-the-art temporal-numeric and hybrid planners.
• Score: 4.834203844100679
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: State-of-the-art temporal planners that support continuous numeric effects typically interweave search with scheduling to ensure temporal consistency. If such effects are linear, this process often makes use of Linear Programming (LP) to model the relationship between temporal constraints and conditions on numeric fluents that are subject to duration-dependent effects. While very effective on benchmark domains, this approach does not scale well when solving real-world problems that require long plans. We propose a set of techniques that allow the planner to compute LP consistency checks lazily where possible, significantly reducing the computation time required, thus allowing the planner to solve larger problem instances within an acceptable time-frame. We also propose an algorithm to perform duration-dependent goal checking more selectively. Furthermore, we propose an LP formulation with a smaller footprint that removes linearity restrictions on discrete effects applied within segments of the plan where a numeric fluent is not duration dependent. The effectiveness of these techniques is demonstrated on domains that use a mix of discrete and continuous effects, which is typical of real-world planning problems. The resultant planner is not only more efficient, but outperforms most state-of-the-art temporal-numeric and hybrid planners, in terms of both coverage and scalability.

Related papers

• Proactive and Reactive Constraint Programming for Stochastic Project Scheduling with Maximal Time-Lags [3.723602673856398]
  This study investigates scheduling strategies for the resource-constrained project scheduling problem with maximal time lags (SRCPSP/max) Recent advances in Constraint Programming (CP) and Temporal Networks have reinvoked interest in evaluating the advantages and drawbacks of various proactive and reactive scheduling methods.
  arXiv  Detail & Related papers  (2024-09-13T15:01:25Z)
• Short-Long Convolutions Help Hardware-Efficient Linear Attention to Focus on Long Sequences [60.489682735061415]
  We propose CHELA, which replaces state space models with short-long convolutions and implements linear attention in a divide-and-conquer manner. Our experiments on the Long Range Arena benchmark and language modeling tasks demonstrate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2024-06-12T12:12:38Z)
• Differentiable Combinatorial Scheduling at Scale [18.09256072039255]
  We propose a differentiable scheduling framework, utilizing Gumbel-Softmax differentiable sampling technique. To encode inequality constraints for scheduling tasks, we introduce textitconstrained Gumbel Trick, which adeptly encodes arbitrary inequality constraints. Our method facilitates an efficient and scalable scheduling via gradient descent without the need for training data.
  arXiv  Detail & Related papers  (2024-06-06T02:09:39Z)
• Constant-time Motion Planning with Anytime Refinement for Manipulation [17.543746580669662]
  We propose an anytime refinement approach that works in combination with constant-time motion planners (CTMP) algorithms. Our proposed framework, as it operates as a constant time algorithm, rapidly generates an initial solution within a user-defined time threshold. functioning as an anytime algorithm, it iteratively refines the solution's quality within the allocated time budget.
  arXiv  Detail & Related papers  (2023-11-01T20:40:10Z)
• Dynamic Scheduling for Federated Edge Learning with Streaming Data [56.91063444859008]
  We consider a Federated Edge Learning (FEEL) system where training data are randomly generated over time at a set of distributed edge devices with long-term energy constraints. Due to limited communication resources and latency requirements, only a subset of devices is scheduled for participating in the local training process in every iteration.
  arXiv  Detail & Related papers  (2023-05-02T07:41:16Z)
• Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
  This work introduces a new notion of complexity, the generalized bracketing numbers, which marries constraints on the adversary to the size of the space. We then instantiate our bounds in several problems of interest, including online prediction and planning of piecewise continuous functions.
  arXiv  Detail & Related papers  (2023-02-10T18:45:52Z)
• A Hierarchical Temporal Planning-Based Approach for Dynamic Hoist Scheduling Problems [11.66506213335498]
  Hoist scheduling has become a bottleneck in electroplating industry applications with the development of autonomous devices. We formulate the hoist scheduling problem as a new temporal planning problem in the form of adapted PDDL. We provide a collection of real-life benchmark instances that can be used to evaluate solution methods for the problem.
  arXiv  Detail & Related papers  (2022-12-11T05:30:44Z)
• Gradient-Based Mixed Planning with Discrete and Continuous Actions [34.885999774739055]
  We propose a quadratic-based framework to simultaneously optimize continuous parameters and actions of candidate plans. The framework is combined with a module to estimate the best plan candidate to transit initial state to the goal based on relaxation.
  arXiv  Detail & Related papers  (2021-10-19T14:21:19Z)
• 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)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Time-varying Gaussian Process Bandit Optimization with Non-constant Evaluation Time [93.6788993843846]
  We propose a novel time-varying Bayesian optimization algorithm that can effectively handle the non-constant evaluation time. Our bound elucidates that a pattern of the evaluation time sequence can hugely affect the difficulty of the problem.
  arXiv  Detail & Related papers  (2020-03-10T13:28:33Z)

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.