bluuebunny/crossref_metadata_2025 huggingface dataset:
Bridging the Gap between Abstractions and Critical-Path Heuristics via Hypergraphs
Authors: Steinmetz Marcel , Torralba Álvaro
Published: September 2022

Abstractions and critical-path heuristics are among the most important families of admissible heuristics in classical planning. In this paper, we present a new family of heuristics, which we name hyperabstractions, given by the combination of the principal ideas underlying abstractions and critical-path heuristics. Hyperabstractions approximate goal distances through a mapping from states to sets of abstract states. The abstract transition behavior forms a relation between abstract states and sets of abstract states, and is formally represented via the notion of hypergraphs. We show that both abstractions and critical-path heuristics can naturally be expressed as members of this family. Moreover, we devise a method to construct hyperabstractions, using either a set of abstractions or a critical-path heuristic as a seed, in a way that guarantees that the resulting distance estimations dominate those of the input heuristics, sometimes even strictly. By finding suitable cost partitionings for hyperabstraction heuristics, this dominance result is preserved even in comparison to the additive combination of the input heuristics. Our experiments indicate the potential of this new class of heuristics, opening a wide range of future research topics.
Reinforcement Learning Based Querying in Camera Networks for Efficient Target Tracking
Authors: Sharma Anil , Anand Saket , Kaul Sanjit K.
Published: September 2022

Surveillance camera networks are a useful monitoring infrastructure that can be used for various visual analytics applications, where high-level inferences and predictions could be made based on target tracking across the network. Most multi-camera tracking works focus on re-identification problems and trajectory association problems. However, as camera networks grow in size, the volume of data generated is humongous, and scalable processing of this data is imperative for deploying practical solutions. In this paper, we address the largely overlooked problem of scheduling cameras for processing by selecting one where the target is most likely to appear next. The inter-camera handover can then be performed on the selected cameras via re-identification or another target association technique. We model this scheduling problem using reinforcement learning and learn the camera selection policy using Q-learning. We do not assume the knowledge of the camera network topology but we observe that the resulting policy implicitly learns it. We evaluate our approach using NLPR MCT dataset, which is a real multi-camera multi-target tracking benchmark and show that the proposed policy substantially reduces the number of frames required to be processed at the cost of a small reduction in recall.
Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks
Authors: Abeywickrama Tenindra , Cheema Muhammad Aamir , Storandt Sabine
Published: September 2022

Location-based services rely heavily on efficient methods that search for relevant points-of-interest (POIs) close to a given location. A k nearest neighbors (kNN) query is one such example that finds k closest POIs from an agent's location. While most existing techniques focus on finding nearby POIs for a single agent, many applications require POIs that are close to multiple agents. In this paper, we study a natural extension of the kNN query for multiple agents, namely, the Aggregate k Nearest Neighbors (AkNN) query. An AkNN query retrieves k POIs with the smallest aggregate distances where the aggregate distance of a POI is obtained by aggregating its distances from the multiple agents (e.g., sum of its distances from each agent). Existing search heuristics are designed for a single agent and do not work well for multiple agents. We propose a novel data structure COLT (Compacted Object-Landmark Tree) to address this gap by enabling efficient hierarchical graph traversal. We then utilize COLT for a wide range of aggregate functions to efficiently answer AkNN queries. In our experiments on real-world and synthetic data sets, our techniques significantly improve query performance, typically outperforming existing approaches by more than an order of magnitude in almost all settings.
EFP 2.0: A Multi-Agent Epistemic Solver with Multiple E-State Representations
Authors: Fabiano Francesco , Burigana Alessandro , Dovier Agostino , Pontelli Enrico
Published: September 2022

Multi-agent systems have been employed to model, simulate and explore a variety of real-world scenarios. It is becoming more and more important to investigate formalisms and tools that would allow us to exploit automated reasoning in these domains. An area that has received increasing attention is the use of multi-agent systems which allow an agent to reason about the knowledge and beliefs of other agents. This type of reasoning, i.e., about agents' perception of the world and also about agents' knowledge of her and others' knowledge, is referred to as epistemic reasoning. This paper presents an updated formalization and implementation of a multi-agent epistemic planner, called EFP. In particular, the paper explores the advantages of using alternative state representations that deviate from the commonly used Kripke structures. The paper explores such alternatives in the context of an action language for multi-agent epistemic planning. The paper presents also an actual implementation of a planner that uses the novel ideas, demonstrating concrete performance improvements on benchmarks collected from the literature.
Faster Dynamic-Consistency Checking for Conditional Simple Temporal Networks
Authors: Hunsberger Luke , Posenato Roberto
Published: September 2022

A Conditional Simple Temporal Network (CSTN) is a structure for representing and reasoning about time in domains where temporal constraints may be conditioned on outcomes of observations made in real time. A CSTN is dynamically consistent (DC) if there is a strategy for executing its time-points such that all relevant constraints will necessarily be satisfied no matter which outcomes happen to be observed. The literature on CSTNs contains only one sound-and-complete DC-checking algorithm that has been implemented and empirically evaluated. It is a graph-based algorithm that propagates labeled constraints/edges. A second algorithm has been proposed, but not evaluated. It aims to speed up DC checking by more efficiently dealing with so-called negative q-loops.This paper presents a new two-phase approach to DC-checking for CSTNs. The first phase focuses on identifying negative q-loops and labeling key time-points within them. The second phase focuses on computing (labeled) distances from each time-point to a single sink node. The new algorithm, which is also sound and complete for DC-checking, is then empirically evaluated against both pre-existing algorithms and shown to be much faster across not only previously published benchmark problems, but also a new set of benchmark problems. The results show that, on DC instances, the new algorithm tends to be an order of magnitude faster than both existing algorithms. On all other benchmark cases, the new algorithm performs better than or equivalently to the existing algorithms.
New Valid Inequalities in Branch-and-Cut-and-Price for Multi-Agent Path Finding
Authors: Lam Edward , Le Bodic Pierre
Published: September 2022

BCP, a state-of-the-art algorithm for optimal Multi-agent Path Finding, uses the branch-and-cut-and-price framework to decompose the problem into (1) a master problem that selects a set of collision-free low-cost paths, (2) a pricing problem that adds lower-cost paths to the master problem, (3) separation problems that resolve various kinds of conflicts in the master problem, and (4) branching rules that split the nodes in the high-level branch-and-bound search tree. This paper focuses on the separation aspects of the decomposition by introducing five new classes of fractional conflicts and valid inequalities that remove these conflicts to tighten the linear programming relaxation in the master problem. Experimental results on 12820 instances across 16 maps indicate that including the five families of inequalities allows BCP to solve an additional 585 instances, optimize the same instances 41% faster, and solve 2068 more instances than CBSH-RM and 157 more than Lazy CBS.
Search-Guidance Mechanisms for Numeric Planning Through Subgoaling Relaxation
Authors: Scala Enrico , Saetti Alessandro , Serina Ivan , Gerevini Alfonso E.
Published: September 2022

Recently, a new decomposition based relaxation has been proposed for numeric planning problems. Roughly, this relaxation is grounded on the identification of regression-based necessary conditions for the satisfaction of sets of numeric subgoals. So far, it has been used to define novel heuristics that are able to provide great guidance in problems exhibiting a pronounced numeric structure. This paper investigates how to further exploit this relaxation; it does so by introducing the notion of the multi-repetition relaxed plan. The multi-repetition plan annotates actions with the number of times such actions need to be executed. We use this structure for different purposes: extraction of a concrete relaxed plan based heuristic, definition of subgoaling based helpful actions, and definition of what we call up-to-jumping actions. Up-to-jumping actions allow us to deeply leverage from the metric structure of the problem and devise an informed search strategy that can collapse several decision steps. We experimentally analyze a forward state space planner equipped with these novel mechanisms across several planning benchmarks, showing the benefit of the ideas presented in the paper.
New Developments for Robert – Assisting Novice Users Even Better in DIY Projects
Authors: Behnke Gregor , Bercher Pascal , Kraus Matthias , Schiller Marvin , Mickeleit Kristof , Häge Timo , Dorna Michael , Dambier Michael , Manstetten Dietrich , Minker Wolfgang , Glimm Birte , Biundo Susanne
Published: September 2022

Do-It-Yourself (DIY) home improvement projects require a combination of specific knowledge and practical abilities. Novice users often lack both and thus tend to fail or be frightful of performing DIY projects – even though they would like to. By providing suitable and individualised assistance in the form of step-by-step instructions, the assistant Robert allows even novice users to successfully complete their DIY projects. Simultaneously, Robert allows its users to learn how to perform these steps themselves and thus enables them to become more independent in the future. In this paper, we report on the latest progress with Robert. Compared to earlier versions, Robert is now able to adaptively change its instructions based on the wishes and preferences of the user. Further, Robert is now able to use connected tools – i.e. tools that are able to sense and communicate their status – to check whether the user is performing the project's steps correctly and to provide further assistance in the case of failure. Lastly, we present the results of an empirical study conducted to show Robert's effectiveness.
Deep Reinforcement Learning Approach to Solve Dynamic Vehicle Routing Problem with Stochastic Customers
Authors: Joe Waldy , Lau Hoong Chuin
Published: September 2022

In real-world urban logistics operations, changes to the routes and tasks occur in response to dynamic events. To ensure customers' demands are met, planners need to make these changes quickly (sometimes instantaneously). This paper proposes the formulation of a dynamic vehicle routing problem with time windows and both known and stochastic customers as a route-based Markov Decision Process. We propose a solution approach that combines Deep Reinforcement Learning (specifically neural networks-based Temporal-Difference learning with experience replay) to approximate the value function and a routing heuristic based on Simulated Annealing, called DRLSA. Our approach enables optimized re-routing decision to be generated almost instantaneously. Furthermore, to exploit the structure of this problem, we propose a state representation based on the total cost of the remaining routes of the vehicles. We show that the cost of the remaining routes of vehicles can serve as proxy to the sequence of the routes and time window requirements. DRLSA is evaluated against the commonly used Approximate Value Iteration (AVI) and Multiple Scenario Approach (MSA). Our experiment results show that DRLSA can achieve on average, 10% improvement over myopic, outperforming AVI and MSA even with small training episodes on problems with degree of dynamism above 0.5.
We Mind Your Well-Being: Preventing Depression in Uncertain Social Networks by Sequential Interventions
Authors: Aung Aye Phyu Phyu , Wang Xinrun , An Bo , Li Xiaoli
Published: September 2022

Mental health has become a major concern according to WHO who estimates that more than 350 million people worldwide are affected by depression. Studies have shown that interventions and social support can reduce stress and depression. However, counselling centers do not have enough resources to provide counselling and social support to all the participants in their interest. This paper helps social support organizations (e.g., university counselling centers) sequentially select the participants for interventions. Unfortunately, previous works do not consider emotion propagation from other neighbours of the influencees and initial uncertainties of mental states and influence. Moreover, they fail to scale up to solve problems with a large number of participants due to the huge state space. Our contributions in this paper are fourfold. Firstly, we propose a new model that addresses the sequential intervention of participants while considering the propagation of emotions and formulate it as a Partially Observable Markov Decision Process (POMDP) to handle uncertainties about their mental states and the influence between them. Secondly, we apply reasoning to refine belief to improve solution quality for the lack of initial information on mental state values. Thirdly, we improve the scalability by the abstraction of states to reduce the number of states by representing the mental states with an abstracted discrete set. We further improve the scalability by multi-level partitioning to get smaller POMDPs. Finally, we conduct extensive experiments on both synthetic and real networks to show that our algorithm significantly improves scalability with comparable solution quality compared to the state-of-the-art algorithms.
Learning Neural Search Policies for Classical Planning
Authors: Gomoluch Pawel , Alrajeh Dalal , Russo Alessandra , Bucchiarone Antonio
Published: September 2022

Heuristic forward search is currently the dominant paradigm in classical planning. Forward search algorithms typically rely on a single, relatively simple variation of best-first search and remain fixed throughout the process of solving a planning problem. Existing work combining multiple search techniques usually aims at supporting best-first search with an additional exploratory mechanism, triggered using a handcrafted criterion. A notable exception is very recent work which combines various search techniques using a trainable policy. That approach, however, is confined to a discrete action space comprising several fixed subroutines.In this paper, we introduce a parametrized search algorithm template which combines various search techniques within a single routine. The template's parameter space defines an infinite space of search algorithms, including, among others, BFS, local and random search. We then propose a neural architecture for designating the values of the search parameters given the state of the search. This enables expressing neural search policies that change the values of the parameters as the search progresses. The policies can be learned automatically, with the objective of maximizing the planner's performance on a given distribution of planning problems. We consider a training setting based on a stochastic optimization algorithm known as the cross-entropy method (CEM). Experimental evaluation of our approach shows that it is capable of finding effective distribution-specific search policies, outperforming the relevant baselines.
Block Compression and Invariant Pruning for SAT-based Totally-Ordered HTN Planning
Authors: Behnke Gregor
Published: September 2022

Translations into propositional logic are currently one of the most efficient techniques for solving Totally-Ordered HTN planning problems.
The two current encodings both iterate over the maximum allowed depth of decomposition.
Given this depth, they compute a tree that represents all possible decompositions up to this depth.
Based on this tree, a formula in propositional logic is created.
We show that much of the computed tree is actually useless as it cannot possibly belong to a solution.
We provide a technique for removing (parts of) these useless structures using state invariants.
We further show that is often not necessary to encode all leafs of this tree as separate timesteps, as the prior encodings did.
Instead, we can compress the leafs into blocks and encode all leafs of a block at one timestep.
We show that these changes provide an improvement over the state-of-the-art in HTN planning.
Fully Observable Nondeterministic HTN Planning -- Formalisation and Complexity Results
Authors: Chen Dillon , Bercher Pascal
Published: September 2022

Much progress has been made in advancing the state of the art of HTN planning theory in recent years. However, scarce studies have been made with regards to the theory and complexity of HTN problems on nondeterministic domains. In this paper we provide a novel formalisation for fully observable nondeterministic HTN planning. We propose and study different solution criteria which differ in when nondeterministic action outcomes are considered: at plan generation or at plan execution. We integrate our solution criteria with notions of weak and strong plans canonical in nondeterministic planning and identify similarities and differences with plans in other fields of AI planning.

We also provide completeness results for a majority of HTN problem subclasses and show the significant result that problems are not made any harder under nondeterminism for certain solution criteria by using compilation techniques to deterministic HTN planning. This supports and justifies the practicality and scalability of extending HTN problems over nondeterministic domains to deal with real world scenarios.
S*: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding
Authors: Chour Kenny , Rathinam Sivakumar , Ravi Ramamoorthi
Published: September 2022

We combine ideas from uni-directional and bi-directional heuristic search, and approximation algorithms for the Traveling Salesman Problem, to develop a novel framework for a Multi-Goal Path Finding (MGPF) problem that provides a 2-approximation guarantee. MGPF aims to find a least-cost path from an origin to a destination such that each node in a given set of goals is visited at least once along the path. We present numerical results to illustrate the advantages of our framework over conventional alternates in terms of the number of expanded nodes and run time.
Delete-Relaxation Heuristics for Lifted Classical Planning
Authors: Corrêa Augusto B. , Francès Guillem , Pommerening Florian , Helmert Malte
Published: September 2022

Recent research in classical planning has shown the importance of search techniques that operate directly on the lifted representation of the problem, particularly in domains where the ground representation is prohibitively large. In this paper, we show how to compute the additive and maximum heuristics from the lifted representation of a problem. We do this by adapting well-known reachability analysis techniques based on a Datalog formulation of the delete relaxation of the problem. Our adaptation allows us to obtain not only the desired heuristic value, but also other useful heuristic information such as helpful actions. Our empirical evaluation shows that our lifted version of the additive heuristic is competitive with its ground counterpart on most of the standard international competition benchmarks, and significantly outperforms other state-of-the-art lifted heuristic methods in the literature.
Subset-Saturated Transition Cost Partitioning
Authors: Drexler Dominik , Seipp Jendrik , Speck David
Published: September 2022

Cost partitioning admissibly combines the information from multiple heuristics for optimal state-space search. One of the strongest cost partitioning algorithms is saturated cost partitioning. It considers the heuristics in sequence and assigns to each heuristic the minimal fraction of the remaining costs that are needed for preserving all heuristic estimates. Saturated cost partitioning has recently been generalized in two directions: first, by allowing to use different costs for the transitions induced by the same operator, and second, by preserving the heuristic estimates for only a subset of states. In this work, we unify these two generalizations and show that the resulting subset-saturated transition cost partitioning algorithm usually yields stronger heuristics than the two generalizations by themselves.
A Competitive Analysis of Online Multi-Agent Path Finding
Authors: Ma Hang
Published: September 2022

We study online Multi-Agent Path Finding (MAPF), where new agents are constantly revealed over time and all agents must find collision-free paths to their given goal locations. We generalize existing complexity results of (offline) MAPF to online MAPF. We classify online MAPF algorithms into different categories based on (1) controllability (the set of agents that they can plan paths for at each time) and (2) rationality (the quality of paths they plan) and study the relationships between them. We perform a competitive analysis for each category of online MAPF algorithms with respect to commonly-used objective functions. We show that a naive algorithm that routes newly-revealed agents one at a time in sequence achieves a competitive ratio that is asymptotically bounded from both below and above by the number of agents with respect to flowtime and makespan. We then show a counter-intuitive result that, if rerouting of previously-revealed agents is not allowed, any rational online MAPF algorithms, including ones that plan optimal paths for all newly-revealed agents, have the same asymptotic competitive ratio as the naive algorithm, even on 2D 4-neighbor grids. We also derive constant lower bounds on the competitive ratio of any rational online MAPF algorithms that allow rerouting. The results thus provide theoretical insights into the effectiveness of using MAPF algorithms in an online setting for the first time.
Non-Deterministic Conformant Planning Using a Counterexample-Guided Incremental Compilation to Classical Planning
Authors: Scala Enrico , Grastien Alban
Published: September 2022

We address the problem of non-deterministic conformant planning, i.e., finding a plan in a non-deterministic context where the environment is not observable. Our approach uses an unsound but complete reduction from non-deterministic conformant planning to classical planning to find a candidate plan; the validity of this plan is then verified by a SAT solver; if the plan is invalid, the reduction is revised to guarantee that the invalid plan will not be valid in the classical planning problem. This procedure is executed until a valid plan is found, or it is shown that there is no plan. Experiments show that this approach provides a nice trade-off between fast but unsound, and complete but slow approaches.
Knowledge Compilation for Nondeterministic Action Languages
Authors: Scheck Sergej , Niveau Alexandre , Zanuttini Bruno
Published: September 2022

We study different languages for representing nondeterministic actions in planning from the point of view of knowledge compilation. Precisely, we consider succintness issues (how succinct is the description of an action in each language?) and complexity issues (tractability or hardness of several queries which arise naturally in planning and belief tracking). We study an abstract, nondeterministic version of PDDL, nondeterministic conditional STRIPS, the language NNFAT of NNF action theories, and the language NPDDLseq obtained by adding a sequence operator to nondeterministic PDDL. We show that these languages have different succinctness and different complexity even for the most natural queries.
Situated Temporal Planning Using Deadline-aware Metareasoning
Authors: Shperberg Shahaf S. , Coles Andrew , Karpas Erez , Ruml Wheeler , Shimony Solomon E.
Published: September 2022

We address the problem of situated temporal planning, in which an agent's plan can depend on scheduled exogenous events, and thus it becomes important to take the passage of time into account during the planning process.
Previous work on situated temporal planning has proposed simple pruning strategies, as well as complex schemes for a simplified version of the associated metareasoning problem. Although even the
simplified version of the metareasoning problem is NP-hard,
we provide a pseudo-polynomial time
optimal solution to the case with known deadlines.
We leverage intuitions emerging from this case to provide a fast greedy
scheme that significantly improves upon previous schemes even for the case
of unknown deadlines.
Finally, we show how this new method can be applied inside a practical situated temporal planner.
An empirical evaluation suggests that the new planner provides state-of-the-art results on problems where external deadlines play a significant role.
Scheduling Stochastic Jobs - Complexity and Approximation Algorithms
Authors: Tao Liangde , Chen Lin , Zhang Guochuan
Published: September 2022

Uncertainty is an omnipresent issue in real-world optimization problems. This paper studies a fundamental problem concerning uncertainty, known as the beta-robust scheduling problem. Given a set of identical machines and a set of jobs whose processing times follow a normal distribution, the goal is to assign jobs to machines such that the probability that all the jobs are completed by a given common due date is maximized. We give the first systematic study on the complexity and algorithms for this problem. A strong negative result is shown by ruling out the existence of any polynomial-time algorithm with a constant approximation ratio for the general problem unless P=NP. On the positive side, we provide the first FPT-AS (fixed parameter tractable approximation scheme) parameterized by the number of different kinds of jobs, which is a common parameter in scheduling problems. It returns a solution arbitrarily close to the optimal solution, provided that the job processing times follow a few different types of distributions. We further complement the theoretical results by implementing our algorithm. The experiments demonstrate that by choosing an appropriate approximation ratio, the algorithm can efficiently compute a near-optimal solution.
Automatic Instance Generation for Classical Planning
Authors: Torralba Álvaro , Seipp Jendrik , Sievers Silvan
Published: September 2022

The benchmarks from previous International Planning Competitions (IPCs) are the de-facto standard for evaluating planning algorithms. The IPC set is both a collection of planning domains and a selection of instances from these domains. Most of the domains come with a parameterized generator that generates new instances for a given set of parameter values. Due to the steady progress of planning research some of the instances that were generated for past IPCs are inadequate for evaluating current planners. To alleviate this problem, we introduce Autoscale, an automatic tool that selects instances for a given domain. Autoscale takes into account constraints from the domain designer as well as the performance of current planners to generate an instance set of appropriate difficulty, while avoiding too much bias with respect to the considered planners. We show that the resulting benchmark set is superior to the IPC set and has the potential of improving empirical evaluation of planning research.
In-Station Train Dispatching: A PDDL+ Planning Approach
Authors: Cardellini Matteo , Maratea Marco , Vallati Mauro , Boleto Gianluca , Oneto Luca
Published: September 2022

In railway networks, stations are probably the most critical points for interconnecting trains' routes: in a restricted geographical area, a potentially large number of trains have to stop according to an official timetable, with the concrete risk of accumulating delays that can then have a knockout effect on the rest of the network. In this context, in-station train dispatching plays a central role in maximising the effective utilisation of available railway infrastructures and in mitigating the impact of incidents and delays. Unfortunately, in-station train dispatching is still largely handled manually by human operators in charge of a group of stations.

In this paper we make a step towards supporting the operator with some automatic tool, by describing an approach for performing in-station dispatching by means of automated planning techniques. Given the mixed discrete-continuous nature of the problem, we employ PDDL+ for the specification of the problem, and the ENHSP planning engine enhanced by domain-specific solving techniques. Results on a range of scenarios, using real-data of a station of the North West of Italy, show the potential of our approach.
Autonomous Building of Structures in Unstructured Environments via AI Planning
Authors: Roberts Jamie O. , Franco Santiago , Stokes Adam A. , Bernardini Sara
Published: September 2022

In this paper, we offer a novel AI planning representation, based on a Cartesian coordinate system, for enabling the autonomous operations of Multi-Robot Systems in 3D environments. Each robot in the system has to conform to unique actuation and connection constraints that create a complex set of valid configurations. Our approach allows Multi-Robot Systems to self-assemble themselves into larger structures via AI planning, with the overarching goal of providing structural capabilities in harsh and uncertain environments.

In comparing four different PDDL (Planning Domain Definition Language) domain representations, we show that our novel formulation satisfies the practical requirements emerging from robot deployment in the real world, resulting in an AI planning system that is accurate and efficient. We scale up performance by implementing direct FDR (Finite Domain Representation) generation based on the best performing PDDL model, bypassing the PDDL-to-FDR translation used by the majority of modern planners. The proposed approach is general and can be applied to a broad range of AI problems involving reasoning in 3D spaces.
Predicted Composite Signed-Distance Fields for Real-Time Motion Planning in Dynamic Environments
Authors: Finean Mark Nicholas , Merkt Wolfgang , Havoutis Ioannis
Published: September 2022

We present a novel framework for motion planning in dynamic environments that accounts for the predicted trajectories of moving objects. We explore the use of composite signed-distance fields in motion planning and detail how they can be used to generate signed-distance fields (SDFs) in real-time to incorporate predicted obstacle motions; to achieve this, we introduce the concept of predicted signed-distance fields. We benchmark our approach of using composite SDFs against performing exact SDF calculations on the workspace occupancy grid. Our proposed technique generates predictions substantially faster and typically exhibits an 81-97% reduction in time for subsequent predictions. We integrate our framework with GPMP2 to demonstrate a full implementation of our approach in real-time, enabling a 7-DoF Panda manipulator to smoothly avoid a moving obstacle in simulation and hardware experiments.
Task-Aware Waypoint Sampling for Robotic Planning
Authors: Keren Sarah , Canal Gerard , Cashmore Michael
Published: September 2022

To achieve a complex task, a robot often needs to navigate in a physical space in order to complete activities in different locations. For example, it may need to inspect several structures, making multiple observations of each structure from different perspectives. Typically, the positions from which these activities can be performed are represented as waypoints – discrete positions that are sampled from the continuous physical space and used to find a task plan. Existing approaches to waypoint selection either iteratively consider the entire space or use domain knowledge to consider each activity separately. This can lead to task planning problems that are more complex than is necessary or to plans of compromised quality. Moreover, all previous approaches only consider geometric constraints that can be imposed on the waypoint selection process.

We present Task-Aware Waypoint Sampling (TAWS), which offers two key novelties. First, it is an anytime approach that combines the benefits of random sampling with the use of domain knowledge in waypoint selection by performing a one-time computation of the connectivity graph from which waypoints are sampled. In addition, TAWS is the first approach that accounts for performance preferences, which are preferences a system operator may have about the generated task plan. These can account, for example, for areas near doorways where it is preferable that the robot does not stop to perform activities. We demonstrate the performance benefits of our approach on simulated automated manufacturing tasks.
Efficient Computation and Informative Estimation of h+ by Integer and Linear Programming
Authors: Feyzbakhsh Rankooh Masood , Rintanen Jussi
Published: September 2022

We investigate modeling cost optimal delete-free STRIPS Planning by Integer/Linear Programming (IP/LP). We introduce two IP models and their LP relaxations based on a recently formulated representation of relaxed plans, named causal relaxed plan representation. The new models are produced by enforcing acyclicity in so-called causal relation graphs using vertex elimination and time labeling methods. We empirically show that while the vertex elimination based method outperforms the time labeling based method and all previously introduced domain independent methods for computing the exact values of h+, the time labeling based LP model is faster to solve compared to its vertex elimination based alternative, making it more suitable for using as heuristic function for optimal planning. We also theoretically analyze the admissible heuristic functions obtained by solving our LP models, and prove that the vertex elimination based heuristic is at least as informative as the time labeling based heuristic. Moreover, our empirical analysis shows that our vertex elimination based heuristic, which is a novel admissible estimation of h+, often has information complementary to that of the LM-cut heuristic.
Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution
Authors: Okumura Keisuke , Défago Xavier
Published: September 2022

Real-time planning for a combined problem of target assignment and path planning for multiple agents, also known as the unlabeled version of Multi-Agent Path Finding (MAPF), is crucial for high-level coordination in multi-agent systems, e.g., pattern formation by robot swarms. This paper studies two aspects of unlabeled-MAPF: (1) offline scenario: solving large instances by centralized approaches with small computation time, and (2) online scenario: executing unlabeled-MAPF despite timing uncertainties of real robots. For this purpose, we propose TSWAP, a novel sub-optimal complete algorithm, which takes an arbitrary initial target assignment then repeats one-timestep path planning with target swapping. TSWAP can adapt to both offline and online scenarios. We empirically demonstrate that Offline TSWAP is highly scalable; providing near-optimal solutions while reducing runtime by orders of magnitude compared to existing approaches. In addition, we present the benefits of Online TSWAP, such as delay tolerance, through real-robot demos.
Euclidean Distance-Optimal Post-processing of Grid-Based Paths
Authors: Senthil Kumar Guru Koushik , Aine Sandip , Likhachev Maxim
Published: September 2022

Paths planned over grids can often be suboptimal in an Euclidean space and contain a large number of unnecessary turns. Consequently, researchers have looked into post-processing techniques to improve the paths after they are planned. In this paper, we propose a novel post-processing technique, called Homotopic Visibility Graph Planning (HVG) which differentiates itself from existing post-processing methods in that it is guaranteed to shorten the path such that it is at least as short as the provably shortest path that lies within the same topological class as the initially computed path. We propose the algorithm, provide proofs and compare it experimentally against other post-processing methods and any-angle planning algorithms.
Improving Time-Dependent Contraction Hierarchies
Authors: Shen Bojie , Cheema Muhammad Aamir , Harabor Daniel D. , Stuckey Peter J.
Published: September 2022

Computing time-optimal shortest paths, in road networks, is one of the most popular applications of Artificial Intelligence. This problem is tricky to solve because road congestion affects travel times. The state-of-the-art in this area is an algorithm called Time-dependent Contraction Hierarchies (TCH). Although fast and optimal, TCH still suffers from two main drawbacks: (1) the usual query process uses bi-directional Dijkstra search to find the shortest path, which can be time-consuming; and (2) the TCH is constructed w.r.t. the entire time domain T, which complicates the search process for queries q that start and finish in a smaller time period Tq ⊂ T. In this work, we improve TCH by making use of time-independent heuristics, which speed up optimal search, and by computing TCHs for different subsets of the time domain, which further reduces the size of the search space. We give a full description of these methods and discuss their optimality-preserving characteristics. We report significant query time improvements against a baseline implementation of TCH.
Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware
Authors: Zhang Jiachen , Lo Bianco Giovanni , Beck J. Christopher
Published: September 2022

The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm.
Deep Reinforcement Learning for a Multi-Objective Online Order Batching Problem
Authors: Beeks Martijn , Refaei Afshar Reza , Zhang Yingqian , Dijkman Remco , Van Dorst Claudy , De Looijer Stijn
Published: September 2022

On-time delivery and low service costs are two important performance metrics in warehousing operations. This paper proposes a Deep Reinforcement Learning (DRL) based approach to solve the online Order Batching and Sequence Problem (OBSP) to optimize these two objectives.
To learn how to balance the trade-off between two objectives, we introduce a Bayesian optimization framework to shape the reward function of the DRL agent, such that the influences of learning to these objectives are adjusted to different environments. We compare our approach with several heuristics using problem instances of real-world size where thousands of orders arrive dynamically per hour.
We show the Proximal Policy Optimization (PPO) algorithm with Bayesian optimization outperforms the heuristics in all tested scenarios on both objectives. In addition, it finds different weights for the components in the reward function in different scenarios, indicating its capability of learning how to set the importance of two objectives under different environments. We also provide policy analysis on the learned DRL agent, where a decision tree is used to infer decision rules to enable the interpretability of the DRL approach.
RADAR-X: An Interactive Mixed Initiative Planning Interface Pairing Contrastive Explanations and Revised Plan Suggestions
Authors: Valmeekam Karthik , Sreedharan Sarath , Sengupta Sailik , Kambhampati Subbarao
Published: September 2022

Decision support systems seek to enable informed decision-making. In the recent years, automated planning techniques have been leveraged to empower such systems to better aid the human-in-the-loop. The central idea for such decision support systems is to augment the capabilities of the human-in-the-loop with automated planning techniques and enhance the quality of decision-making. In addition to providing planning support, effective decision support systems must be able to provide intuitive explanations based on specific user queries for proposed decisions to its end users. Using this as motivation, we present our decision support system RADAR-X that showcases the ability to engage the user in an interactive explanatory dialogue by first enabling them to specify an alternative to a proposed decision (which we refer to as foils), and then providing contrastive explanations to these user-specified foils which helps the user understand why a specific plan was chosen over the alternative (or foil). Furthermore, the system uses this dialogue to elicit the user's latent preferences and provides revised plan suggestions through three different interaction strategies.
An End-to-End Automatic Cache Replacement Policy Using Deep Reinforcement Learning
Authors: Zhou Yang , Wang Fang , Shi Zhan , Feng Dan
Published: September 2022

In the past few decades, much research has been conducted on the design of cache replacement policies. Prior work frequently relies on manually-engineered heuristics to capture the most common cache access patterns, or predict the reuse distance and try to identify the blocks that are either cache-friendly or cache-averse. Researchers are now applying recent advances in machine learning to guide cache replacement policy, augmenting or replacing traditional heuristics and data structures. However, most existing approaches depend on the certain environment which restricted their application, e.g, most of the approaches only consider the on-chip cache consisting of program counters (PCs). Moreover, those approaches with attractive hit rates are usually unable to deal with modern irregular workloads, due to the limited feature used. In contrast, we propose a pervasive cache replacement framework to automatically learn the relationship between the probability distribution of different replacement policies and workload distribution by using deep reinforcement learning. We train an end-to-end cache replacement policy only on the past requested address through two simple and stable cache replacement policies. Furthermore, the overall framework can be easily plugged into any scenario that requires cache. Our simulation results on 8 production storage traces run against 3 different cache configurations confirm that the proposed cache replacement policy is effective and outperforms several state-of-the-art approaches.
Inferring Probabilistic Reward Machines from Non-Markovian Reward Signals for Reinforcement Learning
Authors: Dohmen Taylor , Topper Noah , Atia George , Beckus Andre , Trivedi Ashutosh , Velasquez Alvaro
Published: September 2022

The success of reinforcement learning in typical settings is predicated on Markovian assumptions on the reward signal by which an agent learns optimal policies. In recent years, the use of reward machines has relaxed this assumption by enabling a structured representation of non-Markovian rewards. In particular, such representations can be used to augment the state space of the underlying decision process, thereby facilitating non-Markovian reinforcement learning. However, these reward machines cannot capture the semantics of stochastic reward signals. In this paper, we make progress on this front by introducing probabilistic reward machines (PRMs) as a representation of non-Markovian stochastic rewards. We present an algorithm to learn PRMs from the underlying decision process and prove results around its correctness and convergence.
To v or not to v ? Theme vowels, verbalizers, and the structure of the Ancient Greek verb
Authors: Grestenberger Laura
Published: September 2022

This paper offers a Distributed Morphology analysis of verbal theme vowels and primary verbal stem-forming morphology in Ancient Greek (AG). While verbal stem-forming morphemes are standardly analyzed as realizing Aspect in AG, I propose that both the inherited simple thematic and the athematic verbal stem-forming morphology of AG patterns as verbalizing morphology (v) according to a variety of diagnostics proposed in the literature, in particular idiosyncratic selectional properties of roots and the ability to form denominal and deadjectival verbs. Complex thematic suffixes moreover have the same distribution as simple thematic suffixes. These three classes of verbs (simple thematic, complex thematic, athematic) differ from synchronically denominal and deadjectival verbs, whose nominal stem-forming morphemes later became verbalizers in Modern Greek. This paper thus provides clear diagnostics for distinguishing between synchronically denominal, root-derived, and verbal-stem derived verbs in AG and morphologically similar languages. It also provides further evidence that verbal theme vowels occupy the same structural position and have broadly the same Aktionsart properties as other types of verbalizing morphology, contributing to the debate on the functional/semantic content of theme vowels in general.
Margarito d’Arezzo’s Virgin and Child Enthroned: Victorian Beauty Under Attack?
Authors: Avery-Quash Susanna
Published: September 2022

My chosen work of art for the Gallery section of Professor Hilary Fraser’s Festschrift is the National Gallery’s second oldest painting, Margarito d’Arezzo’s Virgin and Child Enthroned of the 1260s and the debates it aroused when the inaugural director Sir Charles Eastlake bought it in 1857 as part of his revolutionary introduction of early Italian art into the national painting collection, much of which was seen as not at the time at all beautiful — ‘unsightly’ to use his own phrase. This warranted him explaining in the first annual report that such art was acquired not for its aesthetic merit but on the grounds of its historic importance. The article will examine the expanding public role of the National Gallery in terms of educating the widest possible public about the history of Western European painting in addition to offering what were deemed to be suitable teaching aids to encourage the native school of painters. It will also shine a light on various women who have played significant roles in promoting interest in and knowledge about early Italian art, including Margarito’s panel, in the National Gallery’s collection.