bluuebunny/crossref_metadata_2025 huggingface dataset:
A Simple and Fast Bi-Objective Search Algorithm
Authors: Hernández Ulloa Carlos , Yeoh William , Baier Jorge A. , Zhang Han , Suazo Luis , Koenig Sven
Published: September 2022

Many interesting search problems can be formulated as bi-objective search problems, that is, search problems where two kinds of costs have to be minimized, for example, travel distance and time for transportation problems. Bi-objective search algorithms have to maintain the set of undominated paths from the start state to each state to compute the set of paths from the start state to the goal state that are not dominated by some other path from the start state to the goal state (called the Pareto-optimal solution set). Each time they find a new path to a state s, they perform a dominance check to determine whether this path dominates any of the previously found paths to s or whether any of the previously found paths to s dominates this path. Existing algorithms do not perform these checks efficiently. On the other hand, our Bi-Objective A* (BOA*) algorithm requires only constant time per check. In our experimental evaluation, we show that BOA* can run an order of magnitude (or more) faster than state-of-the-art bi-objective search algorithms, such as NAMOA*, NAMOA*dr, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.
New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding
Authors: Li Jiaoyang , Gange Graeme , Harabor Daniel , Stuckey Peter J. , Ma Hang , Koenig Sven
Published: September 2022

We consider two new classes of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage in opposite directions. The second, target symmetry, arises when the shortest path of one agent passes through the target location of a second agent after the second agent has already arrived at it. These symmetries can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes even for state-of-the-art MAPF algorithms such as Conflict-Based Search (CBS). We propose to break these symmetries using new reasoning techniques that: (1) detect each class of symmetry and (2) resolve them by introducing specialized constraints. We experimentally show that our techniques can, in some cases, more than double the success rate of CBS and improve its runtime by one order of magnitude.
Efficient Robot Planning for Achieving Multiple Independent Partially Observable Tasks That Evolve over Time
Authors: Mohseni-Kabir Anahita , Veloso Manuela , Likhachev Maxim
Published: September 2022

We focus on domains where a robot is required to accomplish a set of tasks that are partially observable and evolve independently of each other according to their dynamics. An example domain is a restaurant setting where a robot waiter should take care of an ongoing stream of tasks, namely serving a number of tables, including delivering food to the tables and checking on customers. An action that the robot should take next at any point of time typically depends on the duration of possible actions, the state of each table, and how these tables evolve over time, e.g., the food becomes cold after a few time steps. As most of these domains are dynamic and tasks are frequently being added and removed, the robot typically needs to plan for a short h-step horizon to quickly decide on the next action and replans at each time step. A conventional approach to deal with this problem is to combine all the tasks' states and robot actions into one large model and to compute an h-step optimal policy for this combined model. For the problems that we are interested in, the number of tasks, e.g., the number of tables in the restaurant domain, can be large making this planning approach computationally impractical. The observation that we make however is that in many domains the number of tasks that the robot can accomplish within h-steps is very limited. We present an algorithm that exploits this observation and decomposes the problem into a series of much smaller planning problems, the solution to which gives us an optimal solution. We demonstrate the efficiency of our algorithm on the restaurant domain.
Convex Hull Monte-Carlo Tree-Search
Authors: Painter Michael , Lacerda Bruno , Hawes Nick
Published: September 2022

This work investigates Monte-Carlo planning for agents in stochastic environments, with multiple objectives. We propose the Convex Hull Monte-Carlo Tree-Search (CHMCTS) framework, which builds upon Trial Based Heuristic Tree Search and Convex Hull Value Iteration (CHVI), as a solution to multi-objective planning in large environments. Moreover, we consider how to pose the problem of approximating multi-objective planning solutions as a contextual multi-armed bandits problem, giving a principled motivation for how to select actions from the view of contextual regret. This leads us to the use of Contextual Zooming for action selection, yielding Zooming CHMCTS. We evaluate our algorithm using the Generalised Deep Sea Treasure environment, demonstrating that Zooming CHMCTS can achieve a sublinear contextual regret and scales better than CHVI on a given computational budget.
When Perfect Is Not Good Enough: On the Search Behaviour of Symbolic Heuristic Search
Authors: Speck David , Geißer Florian , Mattmüller Robert
Published: September 2022

Symbolic search has proven to be a competitive approach to cost-optimal planning, as it compactly represents sets of states by symbolic data structures. While heuristics for symbolic search exist, symbolic bidirectional blind search empirically outperforms its heuristic counterpart and is therefore the dominant search strategy. This prompts the question of why heuristics do not seem to pay off in symbolic search. As a first step in answering this question, we investigate the search behaviour of symbolic heuristic search by means of BDDA⋆. Previous work identified the partitioning of state sets according to their heuristic values as the main bottleneck. We theoretically and empirically evaluate the search behaviour of BDDA⋆ and reveal another fundamental problem: we prove that the use of a heuristic does not always improve the search performance of BDDA⋆. In general, even the perfect heuristic can exponentially deteriorate search performance.
Multi-Agent Path Finding with Mutex Propagation
Authors: Zhang Han , Li Jiaoyang , Surynek Pavel , Koenig Sven , Kumar T. K. Satish
Published: September 2022

Mutex propagation is a form of efficient constraint propagation popularly used in AI planning to tightly approximate the reachable states from a given state. We utilize this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF, mutex propagation provides stronger constraints for conflict resolution in Conflict-Based Search (CBS), a popular optimal MAPF algorithm, and provides it with the ability to identify and reason with symmetries in MAPF. While existing work identifies a limited form of symmetries using rectangle reasoning and requires the manual design of symmetry-breaking constraints, mutex propagation is more general and allows for the automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH with rectangle reasoning, a state-of-the-art variant of CBS, with respect to runtime and success rate.
Scheduling with Complex Consumptive Resources for a Planetary Rover
Authors: Chi Wayne , Chien Steve , Agrawal Jagriti
Published: September 2022

Generating and scheduling activities is particularly challenging when considering both consumptive resources and complex resource interactions such as time-dependent resource usage. We present three methods of determining valid temporal placement intervals for an activity in a temporally grounded plan in the presence of such constraints. We introduce the Max Duration and Probe algorithms which are sound, but incomplete, and the Linear algorithm which is sound and complete for linear rate resource consumption. We apply these techniques to the problem of scheduling awake and asleep episodes for a planetary rover where the awake durations are affected by scheduled activities. We demonstrate how the Probe algorithm performs competitively with the Linear algorithm given an advantageous problem space and well-defined heuristics. We show that the Probe and Linear algorithms outperform the Max Duration algorithm empirically. We then present the runtime differences between the three algorithms. The Probe algorithm is currently base-lined for use in the onboard scheduler for NASA's next planetary rover, the Mars 2020 rover.
Driver Activity Recognition by Means of Temporal HTN Planning
Authors: Fernandez-Olivares Juan , Perez Raul
Published: September 2022

When delivering a transport service, scheduled driver workplans have to be aligned with world wide complex hours of service (HoS) regulations which constraint the amount of working and driving time without resting. The activities of such workplans are recorded by onboard sensors in large temporal event logs. Transport companies are interested on recognizing what a driver is doing, based on the temporal observations from event logs, considering the terms defined by HoS regulations. This work presents an application of temporal HTN planning to plan and goal recognition that, starting from a real event log extracted from a tachograph, identifies different sub-sequences of a driver's daily and weekly driving activity and labels them according to the terms defined by HoS regulation.
Solving Large Real-Life Bus Driver Scheduling Problems with Complex Break Constraints
Authors: Kletzander Lucas , Musliu Nysret
Published: September 2022

When scheduling drivers for public transport, in addition to covering the demand and dealing with the spatial dimension, a range of legal requirements, collective agreements and company policies need to be respected. The level of concentration required while driving leads to strict rules for break assignments. This results in a complex problem where creating cost-efficient and employee-friendly schedules is challenging. This paper deals with bus driver scheduling using the rules of the Austrian collective agreement for private omnibus providers. The contributions are the formalization of the complex Austrian rules for bus drivers, a new set of publicly available instances based on the characteristics of real-life instances, and a metaheuristic solution approach for the problem. The algorithm was able to significantly improve the solutions of real-life instances and is evaluated on the generated instances. Further we provide insight in the necessity of objectives for employee satisfaction and their effects. Our method can even be successfully applied to improve results on a problem with very different constraints from Brasil.
Symbolic Plans as High-Level Instructions for Reinforcement Learning
Authors: Illanes León , Yan Xi , Toro Icarte Rodrigo , McIlraith Sheila A.
Published: September 2022

Reinforcement learning (RL) agents seek to maximize the cumulative reward obtained when interacting with their environment. Users define tasks or goals for RL agents by designing specialized reward functions such that maximization aligns with task satisfaction. This work explores the use of high-level symbolic action models as a framework for defining final-state goal tasks and automatically producing their corresponding reward functions. We also show how automated planning can be used to synthesize high-level plans that can guide hierarchical RL (HRL) techniques towards efficiently learning adequate policies. We provide a formal characterization of taskable RL environments and describe sufficient conditions that guarantee we can satisfy various notions of optimality (e.g., minimize total cost, maximize probability of reaching the goal). In addition, we do an empirical evaluation that shows that our approach converges to near-optimal solutions faster than standard RL and HRL methods and that it provides an effective framework for transferring learned skills across multiple tasks in a given environment.
Conflict-Free Multi-Agent Meeting
Authors: Atzmon Dor , Freiman Shahar Idan , Epshtein Oscar , Shichman Oran , Felner Ariel
Published: September 2022

Multi-Agent Meeting (MAM) is the problem of finding a meeting location for multiple agents and paths to that location. Practically, a solution to MAM may contain conflicting paths. A related problem that plans conflict-free paths to a given set of goal locations is the Multi-Agent Path Finding problem (MAPF). In this paper, we solve the Conflict-Free Multi-Agent Meeting problem (CF-MAM). In CF-MAM, we find a meeting location for multiple agents (as in MAM) as well as conflict-free paths (as in MAPF) to that location. We introduce two novel algorithms, which combine MAM and MAPF solvers, for optimally solving CF-MAM. We prove the optimality of both algorithms and compare them experimentally, showing the pros and cons of each algorithm.
Computing Opportunities to Augment Plans for Novel Replanning during Execution
Authors: Borrajo Daniel , Veloso Manuela
Published: September 2022

Traditionally, planning provides for execution plans as sequences of actions with preconditions and effects. Execution monitoring identifies failure conditions when the preconditions of an action do not match the state. Interestingly, planning proceeds by consuming a given initial state and abandoning reasoning about any facts not true in that state. In this paper, we define opportunities as such missing facts, and contribute an algorithm to compute them and augment a plan for execution with them. We then introduce a new execution opportunity monitoring that focusedly checks for these opportunities at each execution state. Opportunistic replanning proceeds now from the new state including the detected opportunities.
Approximate Bi-Criteria Search by Efficient Representation of Subsets of the Pareto-Optimal Frontier
Authors: Goldin Boris , Salzman Oren
Published: September 2022

We consider the bi-criteria shortest-path problem where we want to compute shortest paths on a graph that simultaneously balance two cost functions. While this problem has numerous applications, there is usually no path minimizing both cost functions simultaneously. Thus, we typically consider the set of paths where no path is strictly better than the others in both cost functions, a set called the Pareto-optimal frontier. Unfortunately, the size of this set may be exponential in the number of graph vertices and the general problem is NP-hard. While existing schemes to approximate this set exist, they may be slower than exact approaches when applied to relatively small instances and running them on graphs with even a moderate number of nodes is often impractical. The crux of the problem lies in how to efficiently approximate the Pareto-optimal frontier. Our key insight is that the Pareto-optimal frontier can be approximated using pairs of paths. This simple observation allows us to run a best-first-search while efficiently and effectively pruning away intermediate solutions in order to obtain an approximation of the Pareto frontier for any given approximation factor. We compared our approach with an adaptation of BOA*, the state-of-the-art algorithm for computing exact solutions to the bi-criteria shortest-path problem. Our experiments show that as the problem becomes harder, the speedup obtained becomes more pronounced. Specifically, on large roadmaps, when using an approximation factor of 10% we obtain a speedup on the average running time of more than X19.
Pattern Databases for Goal-Probability Maximization in Probabilistic Planning
Authors: Klößner Thorsten , Hoffmann Jörg , Steinmetz Marcel , Torralba Álvaro
Published: September 2022

Heuristic search algorithms for goal-probability maximization
(MaxProb) have been known since a decade. Yet prior work on heuristic
functions for MaxProb relies on determinization, not actually taking
the probabilities into account. Here we begin to fix this, by
introducing MaxProb pattern databases (PDB). We show that, for the
special case of PDBs in contrast to more general abstractions,
abstract transitions have a unique probability so that the abstract
planning task is still an MDP. The resulting heuristic functions are
admissible, i.e., they upper-bound the real goal probability. We
identify conditions allowing to admissibly multiply heuristic values
across several PDBs. Our experiments show that even non-probabilistic
PDB heuristics often outperform previous MaxProb heuristics, and that
our new probabilistic PDBs can in turn yield significant performance
gains over non-probabilistic ones.
Decentralized Refinement Planning and Acting
Authors: Li Ruoxi , Patra Sunandita , Nau Dana S.
Published: September 2022

We describe Dec-RPAE, a system for decentralized multi-agent acting and planning in partially observable and non-deterministic environments. The system includes both an acting component and an online planning component. The acting component is similar to RAE, a well-known acting engine, but incorporates changes that enable it to be used by multiple autonomous agents working independently in a collaborative setting. Each agent runs a local copy of Dec-RPAE, with a set of hierarchical refinement methods using operational models that specify various ways to accomplish its designated tasks. To perform actions, the agent uses Dec-RPAE’s acting component to execute the methods in the agent’s environment. To advise the acting component on which method to execute, the planning component repeatedly does Monte Carlo simulations of the methods to estimate their potential outcomes. Agents can communicate with each other to exchange information about their states, tasks, goals, and plans in order to cooperatively succeed in their respective missions. Our experimental results demonstrate that Dec-RPAE is useful for improving the agents’ performances.
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines
Authors: Pikies Tytus , Turowski Krzysztof , Kubale Marek
Published: September 2022

In this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine.

We provide several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality: Cmax (makespan) and ∑Cj (total completion time). We consider a variety of machine types in our paper: identical, uniform, and unrelated. Our results consist of delimitation of the easy (polynomial) and NP-hard problems within these constraints. We also provide algorithms, either polynomial exact algorithms for the easier problems, or algorithms with a guaranteed constant worst-case approximation ratio.

In particular, we fill the gap on research for the problem of finding a schedule with the smallest ∑Cj on uniform machines. We address this problem by developing a linear programming relaxation technique with an appropriate rounding, which to our knowledge is a novelty for this criterion in the considered setting.
Distributed Fair Scheduling for Information Exchange in Multi-Agent Systems
Authors: Raeis Majid , Golestani S. Jamaloddin
Published: September 2022

Information exchange is a crucial component of many real-world multi-agent systems. However, the communication between the agents involves two major challenges: the limited bandwidth, and the shared communication medium between the agents, which restricts the number of agents that can simultaneously exchange information. While both of these issues need to be addressed in practice, the impact of the latter problem on the performance of the multi-agent systems has often been neglected. This becomes even more important when the agents' information or observations have different importance, in which case the agents require different priorities for accessing the medium and sharing their information. Representing the agents' priorities by fairness weights and normalizing each agent's share by the assigned fairness weight, the goal can be expressed as equalizing the agents' normalized shares of the communication medium. To achieve this goal, we adopt a queueing theoretic approach and propose a distributed fair scheduling algorithm for providing weighted fairness in single-hop networks. Our proposed algorithm guarantees an upper-bound on the normalized share disparity among any pair of agents. This can particularly improve the short-term fairness, which is important in real-time applications. Moreover, our scheduling algorithm adjusts itself dynamically to achieve a high throughput at the same time. The simulation results validate our claims and comparisons with the existing methods show our algorithm's superiority in providing short-term fairness, while achieving a high throughput.
Flexible FOND Planning with Explicit Fairness Assumptions
Authors: Rodriguez Ivan D. , Bonet Blai , Sardiña Sebastian , Geffner Hector
Published: September 2022

We consider the problem of reaching a propositional goal condition in fully-observable non-deterministic (FOND) planning under a general class of fairness assumptions that are given explicitly. The fairness assumptions are of the form A/B and say that state trajectories that contain infinite occurrences of an action a from A in a state s and finite occurrence of actions from B, must also contain infinite occurrences of action a in s followed by each one of its possible outcomes. The infinite trajectories that violate this condition are deemed as unfair, and the solutions are policies for which all the fair trajectories reach a goal state. We show that strong and strong-cyclic FOND planning, as well as QNP planning, a planning model introduced recently for generalized planning, are all special cases of FOND planning with fairness assumptions of this form which can also be combined. FOND+ planning, as this form of planning is called, combines the syntax of FOND planning with some of the versatility of LTL for expressing fairness constraints. A new planner is implemented by reducing FOND+ planning to answer set programs, and the performance of the planner is evaluated in comparison with FOND and QNP planners, and LTL synthesis tools.
Conflict-Based Increasing Cost Search
Authors: Walker Thayne T. , Sturtevant Nathan R. , Felner Ariel , Zhang Han , Li Jiaoyang , Kumar T. K. Satish
Published: September 2022

Two popular optimal search-based solvers for the multi-agent pathfinding (MAPF) problem, Conflict-Based Search (CBS) and Increasing Cost Tree Search (ICTS), have been extended separately for continuous time domains and symmetry breaking. However, an approach to symmetry breaking in continuous time domains remained elusive. In this work, we introduce a new algorithm, Conflict-Based Increasing Cost Search (CBICS), which is capable of symmetry breaking in continuous time domains by combining the strengths of CBS and ICTS. Our experiments show that CBICS often finds solutions faster than CBS and ICTS in both unit time and continuous time domains.
A Simulator-based Planning Framework for Optimizing Autonomous Greenhouse Control Strategy
Authors: An Zhicheng , Cao Xiaoyan , Yao Yao , Zhang Wanpeng , Li Lanqing , Wang Yue , Guo Shihui , Luo Dijun
Published: September 2022

The rapidly growing global population presents challenges and demands for efficient production of healthy fresh food. Autonomous greenhouse equipped with standard sensors and actuators (such as heating and lighting) which enables control of indoor climate for crop production, contributes to producing higher yields. However, it requires skilled and expensive labor, as well as a large amount of energy. An autonomous greenhouse control strategy, powered by AI algorithms by optimizing the yields and resource use simultaneously, offers an ideal solution to the dilemma.
In this paper, we propose a two-stage planning framework to automatically optimize greenhouse control setpoints given specific outside weather conditions. Firstly, we take advantage of cumulative planting data and horticulture knowledge to build a multi-modular simulator using neural networks, to simulate climate change and crop growth in the greenhouse. Secondly, two AI algorithms (reinforcement learning and heuristic algorithm) as planning methods are applied to obtain optimal control strategies based on the simulator.
We evaluate our framework on a cherry-tomato planting dataset and demonstrate that the simulator is able to simulate greenhouse planting processes with high accuracy and fast speed. Moreover, the control strategies produced by the AI algorithms all obtain superhuman performance, in particular, significantly outperform all teams of the second “Autonomous Greenhouse Challenge” in terms of net profits.
Automated Design of fMRI Paradigms
Authors: Bianchini Esper Katherine , Meneguzzi Felipe
Published: September 2022

Neuroimaging techniques have been widely used in recent decades to assess brain activation patterns for neuroscience. Task design is the most important challenge for neuroimaging studies, to achieve the best modeling for assessing brain patterns within and across subjects. Specifically, functional magnetic resonance imaging (fMRI) experiments rely on the precise and effective design of sequences of stimuli intended to activate specific brain regions (i.e. paradigm design). In this paper, we use PDDL+ to model fMRI paradigms so that neuroscientists can use automated planning to design neuroimaging paradigms in a declarative way. Planning neuroimaging paradigms is especially important for functional studies and presurgical planning. The former should help to ensure an experimental design that allows the analysis of the brain regions that are interesting in the study. The latter should help surgeons select the correct stimuli for a presurgical, non-invasive, exploration of the cognitive functions that might be affected by debridement of brain lesions.
A Deep Ensemble Method for Multi-Agent Reinforcement Learning: A Case Study on Air Traffic Control
Authors: Ghosh Supriyo , Laguna Sean , Lim Shiau Hong , Wynter Laura , Poonawala Hasan
Published: September 2022

Reinforcement learning (RL), a promising framework for data-driven decision making in an uncertain environment, has successfully been applied in many real-world operation and control problems. However, the application of RL in a large-scale decentralized multi-agent environment remains a challenging problem due to the partial observability and limited communications between agents. In this paper, we develop a model-based kernel RL approach and a model-free deep RL approach for learning a decentralized, shared policy among homogeneous agents. By leveraging the strengths of both these methods, we further propose a novel deep ensemble multi-agent reinforcement learning (MARL) method that efficiently learns to arbitrate between the decisions of the local kernel-based RL model and the wider-reaching deep RL model. We validate the proposed deep ensemble method on a highly challenging real-world air traffic control problem, where the goal is to provide effective guidance to aircraft to avoid air traffic congestion, conflicting situations, and to improve arrival timeliness, by dynamically recommending adjustments of aircraft speeds in real-time. Extensive empirical results from an open-source air traffic management simulation model, developed by Eurocontrol and built on a real-world data set including thousands of aircrafts, demonstrate that our proposed deep ensemble MARL method significantly outperforms three state-of-the-art benchmark approaches.
Meta Reinforcement Learning for Heuristic Planing
Authors: Luna Gutierrez Ricardo , Leonetti Matteo
Published: September 2022

Heuristic planning has a central role in classical planning applications and competitions. Thanks to this success, there has been an increasing interest in using Deep Learning to create high-quality heuristics in a supervised fashion, learning from optimal solutions of previously solved planning problems. Meta-Reinforcement learning is a fast growing research area concerned with learning, from many tasks, behaviours that can quickly generalize to new tasks from the same distribution of the training ones. We make a connection between meta-reinforcement learning and heuristic planning, showing that heuristic functions meta-learned from planning problems, in a given domain, can outperform both popular domain-independent heuristics, and heuristics learned by supervised learning. Furthermore, while most supervised learning algorithms rely on ad-hoc encodings of the state representation, our method uses as input a general PDDL 3.1 description. We evaluated our heuristic with an A* planner on six domains from the International Planning Competition and the FF Domain Collection, showing that the meta-learned heuristic leads to the expansion, on average, of fewer states than three popular heuristics used by the FastDownward planner, and a supervised-learned heuristic.
Abstraction-Guided Policy Recovery from Expert Demonstrations
Authors: Ponnambalam Canmanie T. , Oliehoek Frans A. , Spaan Matthijs  T. J.
Published: September 2022

Behavior cloning is a method of automated decision-making that aims to extract meaningful information from expert demonstrations and reproduce the same behavior autonomously. It is unlikely that demonstrations will exhaustively cover the potential problem space, compromising the quality of automation when out-of-distribution states are encountered. Our approach RECO jointly learns both an imitation policy and recovery policy from expert data. The recovery policy steers the agent from unknown states back to the demonstrated states in the data set. While there is, per definition, no data available to learn the recovery policy, we exploit abstractions to generalize beyond the available data and simulate the recovery problem. When the most appropriate abstraction for the given data is unknown, our method selects the best recovery policy from a set generated by several candidate abstractions. In tabular domains, where we assume an agent must call to a human supervisor for help if it is in an unknown state, we show how RECO results in drastically fewer calls without compromising solution quality and with relatively few trajectories provided by an expert. We also introduce a continuous adaptation of our method and demonstrate the ability of RECO to recover an agent from states where its supervised learning-based imitation policy would otherwise fail.
Guiding Robot Exploration in Reinforcement Learning via Automated Planning
Authors: Hayamizu Yohei , Amiri Saeid , Chandan Kishan , Takadama Keiki , Zhang Shiqi
Published: September 2022

Reinforcement learning (RL) enables an agent to learn from trial-and-error experiences toward achieving long-term goals; automated planning aims to compute plans for accomplishing tasks using action knowledge. Despite their shared goal of completing complex tasks, the development of RL and automated planning has been largely isolated due to their different computational modalities. Focusing on improving RL agents' learning efficiency, we develop Guided Dyna-Q (GDQ) to enable RL agents to reason with action knowledge to avoid exploring less-relevant states. The action knowledge is used for generating artificial experiences from an optimistic simulation. GDQ has been evaluated in simulation and using a mobile robot conducting navigation tasks in a multi-room office environment. Compared with competitive baselines, GDQ significantly reduces the effort in exploration while improving the quality of learned policies.
E2Coop: Energy Efficient and Cooperative Obstacle Detection and Avoidance for UAV Swarms
Authors: Huang Shuangyao , Zhang Haibo , Huang Zhiyi
Published: September 2022

Energy efficiency is of critical importance to trajectory planning for UAV swarms in obstacle avoidance. In this paper, we present E2Coop, a new scheme designed to avoid collisions for UAV swarms by tightly coupling Artificial Potential Field (APF) with Particle Swarm Planning (PSO) based trajectory planning. In E2Coop, swarm members perform trajectory planning cooperatively to avoid collisions in an energy-efficient manner. E2Coop exploits the advantages of the active contour model in image processing for trajectory planning. Each swarm member plans its trajectories on the contours of the environment field to save energy and avoid collisions to obstacles. Swarm members that fall within the safeguard distance of each other plan their trajectories on different contours to avoid collisions with each other. Simulation results demonstrate that E2Coop can save energy up to 51% compared with two state-of-the-art schemes.
Encoding Lifted Classical Planning in Propositional Logic
Authors: Höller Daniel , Behnke Gregor
Published: September 2022

Planning models are usually defined in lifted, i.e. first order formalisms, while most solvers need (variable-free) grounded representations. Though techniques for grounding prune unnecessary parts of the model, grounding might – nevertheless – be prohibitively expensive in terms of runtime. To overcome this issue, there has been renewed interest in solving planning problems based on the lifted representation in the last years. While these approaches are based on (heuristic) search, we present an encoding of lifted classical planning in propositional logic and use SAT solvers to solve it. Our evaluation shows that our approach is competitive with the heuristic search-based approaches in satisficing planning and outperforms them in a (length-)optimal setting.
An Exact Algorithm for the Linear Tape Scheduling Problem
Authors: Honoré Valentin , Simon Bertrand , Suter Frédéric
Published: September 2022

Magnetic tapes are often considered as an outdated storage
technology, yet they are still used to store huge amounts of
data. Their main interests are a large capacity and a low price
per gigabyte, which come at the cost of a much larger file access time than on disks. With tapes, finding the right ordering
of multiple file accesses is thus key to performance. Moving
the reading head back and forth along a kilometer long tape
has a non-negligible cost and unnecessary movements thus
have to be avoided. However, the optimization of tape request
ordering has rarely been studied in the scheduling literature,
much less than I/O scheduling on disks. For instance, minimizing
the average service time for several read requests on a
linear tape remains an open question.

Therefore, in this paper, we aim at improving the quality of
service experienced by users of tape storage systems, and not
only the peak performance of such systems. To this end, we
propose a reasonable polynomial-time exact algorithm while
this problem and simpler variants have been conjectured NP-hard. We also refine the proposed model by considering U-turn penalty costs accounting for inherent mechanical accelerations. Then, we propose a low-cost variant of our optimal
algorithm by restricting the solution space, yet still yielding
an accurate suboptimal solution. Finally, we compare our algorithms to existing solutions from the literature on logs of
the mass storage management system of a major datacenter.
This allows us to assess the quality of previous solutions and
the improvement achieved by our low-cost algorithm. Aiming
for reproducibility, we make available the complete implementation of the algorithms used in our evaluation, alongside
the dataset of tape requests that is, to the best of our knowledge, the first of its kind to be publicly released.
On Speeding Up Methods for Identifying Redundant Actions in Plans
Authors: Med Jakub , Chrpa Lukáš
Published: September 2022

Satisficing planning aims at generating plans that are not necessarily optimal. Often, minimising plan generation time negatively affects quality of generated plans. Acquiring plans quickly might be of critical importance in decision-making systems that operate nearly in realtime. However, (very) suboptimal plans might be expensive to execute and more prone to failures. Optimising plans after they are generated, in a spare time, can improve their quality. This paper focuses on speeding up the (Greedy) Action Elimination methods, which are used for identifying and removing redundant actions from plans in polynomial time. We present two enhancements of these methods: Plan Action Landmarks, actions that are not redundant in a given plan, and Action Cycles which are subsequences of actions which if removed do not affect the state trajectory after the last action of the cycle. We evaluate the introduced methods on benchmark problems from the Agile tracks of the International Planning Competition and on plans generated by several state-of-the-art planners, successful in the recent editions of the competition.
Lazy Rearrangement Planning in Confined Spaces
Authors: Wang Rui , Gao Kai , Yu Jingjin , Bekris Kostas
Published: September 2022

Object rearrangement is important for many applications but remains challenging, especially in confined spaces, such as shelves, where objects cannot be accessed from above and they block reachability to each other. Such constraints require many motion planning and collision checking calls, which are computationally expensive. In addition, the arrangement space grows exponentially with the number of objects. To address these issues, this work introduces a lazy evaluation framework with a local monotone solver and a global planner. Monotone instances are those that can be solved by moving each object at most once. A key insight is that reachability constraints at the grasps for objects' starts and goals can quickly reveal dependencies between objects without having to execute expensive motion planning queries. Given that, the local solver builds lazily a search tree that respects these reachability constraints without verifying that the arm paths are collision free. It only collision checks when a promising solution is found. If a monotone solution is not found, the non-monotone planner loads the lazy search tree and explores ways to move objects to intermediate locations from where monotone solutions to the goal can be found. Results show that the proposed framework can solve difficult instances in confined spaces with up to 16 objects, which state-of-the-art methods fail to solve. It also solves problems faster than alternatives, when the alternatives find a solution. It also achieves high-quality solutions, i.e., only 1.8 additional actions on average are needed for non-monotone instances.
OFFICERS: Operational Framework for Intelligent Crime-and-Emergency Response Scheduling
Authors: Chase Jonathan , Goh Siong Thye , Tran Phong , Lau Hoong Chuin
Published: September 2022

In the quest to achieve better response times in dense urban environments, law enforcement agencies are seeking AI-driven planning systems to inform their patrol strategies. In this paper, we present a framework, OFFICERS, for deployment planning that learns from historical data to generate deployment schedules on a daily basis. We accurately predict incidents using ST-ResNet, a deep learning technique that captures wide-ranging spatio-temporal dependencies, and solve a large-scale optimization problem to schedule deployment, significantly improving its scalability through a simulated annealing solver. Methodologically, our approach outperforms our previous works where prediction was done using Generative Adversarial Networks, and optimization was performed with the CPLEX solver. Furthermore, we show that our proposed framework is designed to be readily transferable between use cases, handling a wide range of both criminal and non-criminal incidents, with the use of deep learning and a general-purpose efficient solver, reducing dependence on context-specific details. We demonstrate the value of our approach on a police patrol case study, and discuss both the ethical considerations, and operational requirements, for deployment of a lightweight and responsive planning system.
Reinforcement Learning Approach to Solve Dynamic Bi-objective Police Patrol Dispatching and Rescheduling Problem
Authors: Joe Waldy , Lau Hoong Chuin , Pan Jonathan
Published: September 2022

Police patrol aims to fulfill two main objectives namely to project presence and to respond to incidents in a timely manner. Incidents happen dynamically and can disrupt the initially-planned patrol schedules. The key decisions to be made will be which patrol agent to be dispatched to respond to an incident and subsequently how to adapt the patrol schedules in response to such dynamically-occurring incidents whilst still fulfilling both objectives; which sometimes can be conflicting. In this paper, we define this real-world problem as a Dynamic Bi-Objective Police Patrol Dispatching and Rescheduling Problem and 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 rescheduling heuristic based on ejection chains to learn both dispatching and rescheduling policies jointly. To address the dual objectives, we propose a reward function that implicitly tries to maximize the rate of successfully responding to an incident within a response time target while minimizing the reduction in patrol presence without the need to explicitly set predetermined weights for each objective. The proposed approach is able to compute both dispatching and rescheduling decisions almost instantaneously. Our work serves as the first work in the literature that takes into account these dual patrol objectives and real-world operational consideration where incident response may disrupt existing patrol schedules.
Hyper-Heuristics for Personnel Scheduling Domains
Authors: Kletzander Lucas , Musliu Nysret
Published: September 2022

In real-life applications problems can frequently change or require small adaptations. Manually creating and tuning algorithms for different problem domains or different versions of a problem can be cumbersome and time-consuming. In this paper we consider several important problems with high practical relevance, which are Bus Driver Scheduling, Rotating Workforce Scheduling, and Minimum Shift Design. Instead of designing very specific solution methods, we propose to use the more general approach based on hyper-heuristics which take a set of simpler low-level heuristics and combine them to automatically create a fitting heuristic for the problem at hand. This paper presents a major study on applying hyper-heuristics to these domains, which contributes in three different ways: First, it defines new low-level heuristics for these scheduling domains, allowing to apply hyper-heuristics to them for the first time. Second, it provides a comparison of several state-of-the-art hyper-heuristics on those domains. Third, new best solutions for several instances of the different problem domains are found. These results show that hyper-heuristics are able to perform well even on very complex practical problem domains in the area of scheduling and, while being more general and requiring less problem-specific adaptation, can in several cases compete with specialized algorithms for the specific problems. These results help to improve industrial systems in use for solving different scheduling scenarios by allowing faster and easier adaptation to new problem variants.
Analyzing the Efficacy of Flexible Execution, Replanning, and Plan Optimization for a Planetary Lander
Authors: Wang Daniel , Russino Joseph A. , Basich Connor , Chien Steve
Published: September 2022

Plan execution in unknown environments poses a number of challenges: uncertainty in domain modeling, stochasticity at execution time, and the presence of exogenous events. These challenges motivate an integrated approach to planning and execution that is able to respond intelligently to variation. We examine this problem in the context of the Europa Lander mission concept, and evaluate a planning and execution framework that responds to feedback and task failure using two techniques: flexible execution and replanning with plan optimization. We develop a theoretical framework to estimate gains from these techniques, and we compare these predictions to empirical results generated in simulation. These results indicate that an integrated approach to planning and execution leveraging flexible execution, replanning, and utility maximization shows significant promise for future tightly-constrained space missions that must address significant uncertainty.
Tuning the Hyperparameters of Anytime Planning: A Metareasoning Approach with Deep Reinforcement Learning
Authors: Bhatia Abhinav , Svegliato Justin , Nashed Samer B. , Zilberstein Shlomo
Published: September 2022

Anytime planning algorithms often have hyperparameters that can be tuned at runtime to optimize their performance. While work on metareasoning has focused on when to interrupt an anytime planner and act on the current plan, the scope of metareasoning can be expanded to tuning the hyperparameters of the anytime planner at runtime. This paper introduces a general, decision-theoretic metareasoning approach that optimizes both the stopping point and hyperparameters of anytime planning. We begin by proposing a generalization of the standard meta-level control problem for anytime algorithms. We then offer a meta-level control technique that monitors and controls an anytime algorithm using deep reinforcement learning. Finally, we show that our approach boosts performance on a common benchmark domain that uses anytime weighted A* to solve a range of heuristic search problems and a mobile robot application that uses RRT* to solve motion planning problems.
Presentación
Authors: Castañeda M. Walter
Published: September 2022

La Revista Kepes número 26, del período julio-diciembre de 2022, se comparte con la comunidad académica de las disciplinas del diseño, las artes, las comunicaciones. Este volumen corresponde a un llamado a publicar que se realizó entre los meses de agosto-septiembre de 2021, con una temática que hacaracterizado a la revista desde sus inicios: acoger reportes de investigaciones o sus avances, con un criterio transdisciplinar, bajo la premisa de que losproblemas de las prácticas proyectuales y las creativas dialogan con otros campos del conocimiento.
La animación documental, estado del arte de una apuesta audiovisual colombiana
Authors: Guzmán Ramírez Jesús Alejandro , Aristizábal Gómez Juan David
Published: September 2022

El presente documento busca revisar el valor que posee la animación documental para la recuperación de memoria colectiva y la visibilización de sucesos que no han podido ser registrados directamente, sin dejar de lado la discusión sobre la pertinencia del término en pos del grado de intervención delrealizador, su carácter discrecional y las decisiones alrededor de los momentos de las narraciones que se quieren presentar. En el caso colombiano, a manera de levantamiento del estado del arte, se puede ver que la preocupación más evidente de los realizadores nacionales a lo largo de las últimas décadas tiene que ver con las problemáticas derivadas del conflicto armado interno, las secuelas que ha dejado en la realidad nacional, la recurrentedinámica de impacto sobre las poblaciones más vulnerables y los actores que se han visto involucrados, el cual no solo es un tema recurrente sino que ha conducido a una forma de denuncia y restauración para víctimas y afectados por la violencia generada. Para poder dimensionar esto se hace un rastreo de la reflexión académica e investigativa que se ha generado sobre el tema de la animación documental, sus impactos, realizaciones, límites yconstrucciones a nivel nacional e internacional, así como una identificación del material audiovisual colombiano en diferentes tipologías de exhibición y pantallas de difusión que se puede enmarcar en dicha categoría.