bluuebunny/crossref_metadata_2025 huggingface dataset:
Discriminatively Reranking Abductive Proofs for Plan Recognition
Authors: Wiseman Sam , Shieber Stuart
Published: September 2022

We investigate the use of a simple, discriminative reranking approach to plan recognition in an abductive setting. In contrast to recent work, which attempts to model abductive plan recognition using various formalisms that integrate logic and graphical models (such as Markov Logic Networks or Bayesian Logic Programs), we instead advocate a simpler, more flexible approach in which plans found through an abductive beam-search are discriminatively scored based on arbitrary features. We show that this approach performs well even with relatively few positive training examples, and we obtain state-of-the-art results on two abductive plan recognition datasets, outperforming more complicated systems.
A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration
Authors: Valenzano Richard , Sturtevant Nathan , Schaeffer Jonathan , Xie Fan
Published: September 2022

GBFS-based satisficing planners often augment their search with knowledge-based enhancements such as preferred operators and multiple heuristics. These techniques seek to improve planner performance by making the search more informed. In our work, we will focus on how these enhancements impact coverage and we will use a simple technique called epsilon-greedy node selection to demonstrate that planner coverage can also be improved by introducing knowledge-free random exploration into the search. We then revisit the existing knowledge-based enhancements so as to determine if the knowledge these enhancements employ is offering necessary guidance, or if the impact of this knowledge is to add exploration which can be achieved more simply using randomness. This investigation provides further evidence of the importance of preferred operators and shows that the knowledge added when using an additional heuristic is crucial in certain domains, while not being as effective as random exploration in others. Finally, we demonstrate that random exploration can also improve the coverage of LAMA, a planner which already employs multiple enhancements. This suggests that knowledge-based enhancements need to be compared to appropriate knowledge-free random baselines so as to ensure the importance of the knowledge being used.
Plan and Activity Recognition from a Topic Modeling Perspective
Authors: Freedman Richard , Jung Hee-Tae , Zilberstein Shlomo
Published: September 2022

We examine new ways to perform plan recognition (PR) using natural language processing (NLP) techniques. PR often focuses on the structural relationships between consecutive observations and ordered activities that comprise plans. However, NLP commonly treats text as a bag-of-words, omitting such structural relationships and using topic models to break down the distribution of concepts discussed in documents. In this paper, we examine an analogous treatment of plans as distributions of activities. We explore the application of Latent Dirichlet Allocation topic models to human skeletal data of plan execution traces obtained from a RGB-D sensor. This investigation focuses on representing the data as text and interpreting learned activities as a form of activity recognition (AR). Additionally, we explain how the system may perform PR. The initial empirical results suggest that such NLP methods can be useful in complex PR and AR tasks.
Simulated Penetration Testing: From "Dijkstra" to "Turing Test++"
Authors: Hoffmann Joerg
Published: September 2022

Penetration testing (pentesting) is a well established method for identifying security weaknesses, by conducting friendly attacks. Simulated pentesting automates this process, through designing a model of the system at hand, and using model-based attack planning to generate the attacks. Classical planning variants of this idea are being used commercially by the pentesting industry since 2010. Such models can pinpoint potentially dangerous combinations of known vulnerabilities, but ignore the incomplete knowledge characteristic of hacking from the attacker's point of view. Yet, ideally, the simulation should conduct its attacks the same way a real attacker would. Hence the ultimate goal is much more ambitious: to realistically simulate a human hacker. This is a grand vision indeed; e.g., the classical Turing Test can be viewed as a sub-problem. Taking a more practical perspective, the simulated pentesting model space spans a broad range of sequential decision making problems. Analyzing prior work in AI and other relevant areas, we derive a systematization of this model space, highlighting a multitude of interesting challenges to AI sequential decision making research.
Multi-UAV Monitoring with Priorities and Limited Energy Resources
Authors: Mersheeva Vera , Friedrich Gerhard
Published: September 2022

This paper introduces a monitoring problem with limited energy resources and soft constraints on priorities employing a fleet of unmanned aerial vehicles (UAVs). This monitoring problem is a generalization of application cases ranging from surveillance of open-air events to monitoring crime scenes or disaster sites. In order to compute solutions, we propose an insertion heuristic with a negotiation mechanism for energy resources. The solution quality of the heuristic method is compared to cases where an optimal solution is known resulting in an average deviation of approximately 4%. By using this approach, we are able to plan routes for real-world scenarios which are currently unsolvable by general problem solvers in acceptable time. Moreover, the run-time is within seconds for such scenarios. Therefore, the method can be applied to dynamic environments, where re-planning during the mission is required.
Mixed-Initiative Planning and Execution for Multiple Drones in Search and Rescue Missions
Authors: Bevacqua Giuseppe , Cacace Jonathan , Finzi Alberto , Lippiello Vincenzo
Published: September 2022

We present a mixed-initiative planning and execution system for human multi-drones interaction during search and rescue missions. The proposed system should allow a single operator to supervise and orchestrate the operations of a set of UAVs by means of a natural multimodal communication. In particular, we consider the task of searching for missing persons in a real-world alpine scenario. In this context, we assume that the human operator is an alpine rescuer, involved in the scene and co-located with the drones, hence not fully dedicated to the robotic platforms, but only able to provide sparse and sketchy interventions. This scenario requires a framework that supports adjustable autonomy, from explicit teleoperation to a complete autonomy, and an effective and natural mixed-initiative interaction between the human and the robotic team. In this paper, we illustrate the domain and the overall framework discussing the system at work in a simulated case study.
Temporal Landmarks: What Must Happen, and When
Authors: Karpas Erez , Wang David , Williams Brian , Haslum Patrik
Published: September 2022

Current temporal planners have a hard time solving large, real-world problems which involve dealing with metric time and concurrent actions. While landmarks have enabled classical planners to scale up to significantly larger problems, they have not yet brought as much benefit to temporal planning. We argue that the reason for this is that for landmarks to make an effective addition to planning with complex temporal interactions (such as required concurrency), they must incorporate information about the timing of conditions and events. We define temporal landmarks, which associate time intervals and time points, respectively, with state and action landmarks, thereby capturing both what must happen and when it must happen. We show how to derive temporal landmarks and constraints on their associated time points from planning problems, and how exploiting them, in a planner-independent way, can improve planner performance. Notably, the greatest gain is on problems which require concurrency, showing that the temporal information we add to landmarks complements the reasoning used by current temporal planners.
PDDL+ Planning with Hybrid Automata: Foundations of Translating Must Behavior
Authors: Bogomolov Sergiy , Magazzeni Daniele , Minopoli Stefano , Wehrle Martin
Published: September 2022

Planning in hybrid domains poses a special challenge due to the involved mixed discrete-continuous dynamics. A recent solving approach for such domains is based on applying model checking techniques on a translation of PDDL+ planning problems to hybrid automata. However, the proposed translation is limited because must behavior is only over-approximated, and hence, processes and events are not reflected exactly. In this paper, we present the theoretical foundation of an exact PDDL+ translation. We propose a schema to convert a hybrid automaton with must transitions into an equivalent hybrid automaton featuring only may transitions.
Tight Bounds for HTN Planning
Authors: Alford Ron , Bercher Pascal , Aha David
Published: September 2022

Although HTN planning is in general undecidable, there are many syntactically identifiable sub-classes of HTN problems that can be decided. For these sub-classes, the decision procedures provide upper complexity bounds. Lower bounds were often not investigated in more detail, however. We generalize a propositional HTN formalization to one that is based upon a function-free first-order logic and provide tight upper and lower complexity results along three axes: whether variables are allowed in operator and method schemas, whether the initial task and methods must be totally ordered, and where recursion is allowed (arbitrary recursion, tail-recursion, and acyclic problems). Our findings have practical implications, both for the reuse of classical planning techniques for HTN planning, and for the design of efficient HTN algorithms.
Speeding-Up Any-Angle Path-Planning on Grids
Authors: Uras Tansel , Koenig Sven
Published: September 2022

Simple Subgoal Graphs are constructed from grids by placing subgoals at the corners of obstacles and connecting them. They are analogous to visibility graphs for continuous terrain but have fewer edges and can be used to quickly find shortest paths on grids. The vertices of a Simple Subgoal Graph can be partitioned into different levels to create N-Level Subgoal Graphs, which can be used to find shortest paths on grids even more quickly by ignoring subgoals that are not relevant for the search, which significantly reduces the size of the graph being searched. Search using Two-Level Subgoal Graphs was a non-dominated entry in the Grid-Based Path Planning Competitions 2012 and 2013. In this paper, we take advantage of the similarities between Subgoal Graphs and visibility graphs to show that Subgoal Graphs can be used, with small modifications, to quickly find “any-angle” paths, thus extending their applicability. Any-angle paths are usually shorter and more realistic looking than grid paths since the movement along any-angle paths is not constrained to grid edges. Our algorithm has the advantage that it is a simple extension of searching Subgoal Graphs and is up to two orders of magnitude faster than Theta* and up to an order of magnitude faster than Block A* (using 5 × 5 blocks), two of the most well-known any-angle pathplanning algorithms, while still finding any-angle paths of comparable lengths.
On the Complexity of HTN Plan Verification and Its Implications for Plan Recognition
Authors: Behnke Gregor , Höller Daniel , Biundo Susanne
Published: September 2022

In classical planning it is easy to verify if a given sequence of actions is a solution to a planning problem. It has to be checked whether the actions are applicable in the given order and if a goal state is reached after executing them. In this paper we show that verifying whether a plan is a solution to an HTN planning problem is much harder. More specifically, we prove that this problem is NP-complete, even for very simple HTN planning problems. Furthermore, this problem remains NP-complete if an executable sequence of tasks is already provided. HTN-like hierarchical structures are commonly used to represent plan libraries in plan and goal recognition. By applying our result to plan and goal recognition we provide insight into its complexity.
A Semantic Notion of Interference for Planning Modulo Theories
Authors: Bofill Miquel , Espasa Joan , Villaret Mateu
Published: September 2022

The aim of being able to reason about quantities, time, space and much more has been the main objective of the many efforts on the integration of propositional planning with extensions to handle different theories. Planning Modulo Theories (PMT) is an approximation inspired by Satisfiability Modulo Theories (SMT) that generalizes the integration of arbitrary theories with propositional planning. Parallel plans are crucial to reduce plan lengths and hence the time needed to reach a feasible plan in many approaches. Parallelization of actions relies on the notion of (non-)interference, which is usually determined syntactically at compile time. In this paper we present a general semantic notion of interference between actions in PMT. Along its generality, this notion can be efficiently checked at compile time by means of satisfiability checks.
Online Macro Generation for Privacy Preserving Planning
Authors: Maliah Shlomi , Shani Guy , Brafman Ronen
Published: September 2022

Agents that use Multi-Agent Forward Search (MAFS) todo privacy-preserving planning, often repeatedly develop similar paths. We describe a simple technique for online macro generation allowing agents to reuse successful previous action sequences. By focusing on specific sequences that end with a single public action only, we are able to address the utility problem -- our technique has negligible cost, yet provides both speedups and reduced communication in domains where agents have a reasonable amount of private actions. We describe two variants of our approach, both with attractive privacy preserving properties, and demonstrate the value of macros empirically. We also show that one variant is equivalent to secure MAFS.
Change the Plan — How Hard Can That Be?
Authors: Behnke Gregor , Höller Daniel , Bercher Pascal , Biundo Susanne
Published: September 2022

Interaction with users is a key capability of planning systems that are applied in real-world settings. Such a system has to be able to react appropriately to requests issued by its users. Most of these systems are based on a generated plan that is continually criticised by him, resulting in a mixed-initiative planning system. We present several practically relevant requests to change a plan in the setting of hierarchical task network planning and investigate their computational complexity. On the one hand, these results provide guidelines when constructing algorithms to execute the respective requests, but also provide translations to other well-known planning queries like plan existence or verification. These can be employed to extend an existing planner such that it can form the foundation of a mixed-initiative planning system simply by adding a translation layer on top.
PARIS: A Polynomial-Time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty
Authors: Santana Pedro , Vaquero Tiago , Toledo Cláudio , Wang Andrew , Fang Cheng , Williams Brian
Published: September 2022

Inspired by risk-sensitive, robust scheduling for planetary rovers under temporal uncertainty, this work introduces the Probabilistic Simple Temporal Network with Uncertainty (PSTNU), a temporal planning formalism that unifies the set-bounded and probabilistic temporal uncertainty models from the STNU and PSTN literature. By allowing any combination of these two types of uncertainty models, PSTNU's can more appropriately reflect the varying levels of knowledge that a mission operator might have regarding the stochastic duration models of different activities. We also introduce PARIS, a novel sound and provably polynomial-time algorithm for risk-sensitive strong scheduling of PSTNU's. Due to its fully linear problem encoding for typical temporal uncertainty models, PARIS is shown to outperform the current fastest algorithm for risk-sensitive strong PSTN scheduling by nearly four orders of magnitude in some instances of a popular probabilistic scheduling dataset, while results on a new PSTNU scheduling dataset indicate that PARIS is, indeed, amenable for deployment on resource-constrained hardware.
Domain Model Acquisition in Domains with Action Costs
Authors: Gregory Peter , Lindsay Alan
Published: September 2022

This paper addresses the challenge of automated numeric domain model acquisition from observations. Many industrial and commercial applications of planning technology rely on numeric planning models. For example, in the area of autonomous systems and robotics, an autonomous robot often has to reason about its position in space, power levels and storage capacities. It is essential for these models to be easy to construct. Ideally, they should be automatically constructed. Learning the structure of planning domains from observations of action traces has produced successful results in classical planning. In this work, we present the first results in generalising approaches from classical planning to numeric planning. We restrict the numeric domains to those that include fixed action costs. Taking the finite state automata generated by the LOCM family of algorithms, we learn costs associated with machines; specifically to the object transitions and the state parameters. We learn action costs from action traces (with only the final cost of the plans as extra information) using a constraint programming approach. We demonstrate the effectiveness of this approach on standard benchmarks.
Bayesian Optimization with Resource Constraints and Production
Authors: Dolatnia Nima , Fern Alan , Fern Xiaoli
Published: September 2022

In this paper, we aim to take a step toward a tighter integration of automated planning and Bayesian Optimization (BO). BO is an approach for optimizing costly-to-evaluate functions by selecting a limited number of experiments that each evaluate the function at a specified input. Typical BO formulations assume that experiments are selected one at a time, or in fixed batches, and that experiments can be executed immediately upon request. This setup fails to capture many real-world domains where the execution of an experiment requires setup and preparation time. In this paper, we define a novel BO problem formulation that models the resources and activities needed to prepare and run experiments. We then present a planning approach, based on finite-horizon tree search, for scheduling the potentially concurrent experimental activities with the aim of best optimizing the function within a limited time horizon. A key element of the approach is a novel state evaluation function for evaluating leaves of the search tree, for which we prove approximate guarantees. We evaluate the approach on a number of diverse benchmark problems and show that it produces high-quality results compared to a number of natural baselines.
Traps, Invariants, and Dead-Ends
Authors: Lipovetzky Nir , Muise Christian , Geffner Hector
Published: September 2022

We consider the problem of deriving formulas that capture traps, invariants, and dead-ends in classical planning through polynomial forms of preprocessing. An invariant is a formula that is true in the initial state and in all reachable states. A trap is a conditional invariant: once a state is reached that makes the trap true, all the states that are reachable from it will sat- isfy the trap formula as well. Finally, dead-ends are formulas that are satisfied in states that make the goal unreachable. We introduce a preprocessing algorithm that computes traps in k- DNF form that is exponential in the k parameter, and show how the algorithm can be used to precompute invariants and dead-ends. We report also preliminary tests that illustrate the effectiveness of the preprocessing algorithm for identifying dead-end states, and compare it with the identification that follows from the use of the h1 and h2 heuristics that cannot be preprocessed, and must be computed at run time.
Towards Next Generation Touring: Personalized Group Tours
Authors: Lim Kwan Hui , Chan Jeffrey , Leckie Christopher , Karunasekera Shanika
Published: September 2022

Recommending and planning tour itineraries are challenging and time-consuming for tourists, hence they may seek tour operators for help. Traditionally tour operators have offered standard tour packages of popular locations, but these packages may not cater to tourist's interests. In addition, tourists may want to travel in a group, e.g., extended family, and want an operator to help them. We introduce the novel problem of group tour recommendation (GroupTourRec), which involves many challenges: forming tour groups whose members have similar interests; recommending Points-of-Interests (POI) that form the tour itinerary and cater for the group's interests; and assigning guides to lead these tours. For each challenge, we propose solutions involving: clustering for tourist groupings; optimizing a variant of the Orienteering problem for POI recommendations; and integer programming for tour guide assignments. Using a Flickr dataset of seven cities, we compare our proposed approaches against various baselines and observe significant improvements in terms of interest similarity, total/maximum/minimum tour interests and total tour guide expertise.
Solving Realistic Unit Commitment Problems Using Temporal Planning: Challenges and Solutions
Authors: Piacentini Chiara , Magazzeni Daniele , Long Derek , Fox Maria , Dent Chris
Published: September 2022

When facing real world planning problems, standard planners are often inadequate and enhancement of the current techniques are required. In this paper we present the challenges that we have faced in solving the Unit Commitment (UC) problem, a well-known problem in the electrical power industry for which current best methods are based on Mixed Integer Programming (MIP). Typical UC instances involve hundreds or even thousands of generating units, pushing the scalability of state of the art planners beyond their limits. Furthermore, UC is characterised by state-dependent action costs, a feature that not many domain independent planners can efficiently handle. In this paper we focus on the challenge of making domain-independent planning competitive with the MIP method on realistic-sized UC instances. We present the results of our investigation into modelling the UC problem as a temporal planning problem, and show how we scaled up from handling fewer than 10 generating units to more than 400, obtaining solutions almost as high quality as those generated by MIP. We conclude by discussing future directions for temporal planning in this domain, that lie beyond what can be modelled and solved using MIP methods.
Scheduling Ocean Color Observations for a GEO-Stationary Satellite
Authors: Frank Jeremy , Do Minh , Tran Tony
Published: September 2022

The GEO-Stationary Coastal and Air Pollution Events (GEO-CAPE) mission plans to put a visible spectrum imaging instrument on a satellite in geo-stationary orbit to perform ocean color remote sensing. Two different instrument designs, Filter Radiometer (FR) and COastal Ecosystems Dynamic Imager (COEDI), with different shape for the imaged area and image acquisition time, are being evaluated. Scheduling observations for either instrument requires optimizing science objectives in the presence of predicted cloud cover and available daylight. We model this scheduling problem as both Mixed Integer Linear Program (MILP) and Constraint Programming (CP) problems, and compare these two formulations for FR and COEDI using real cloudiness data collected at different times throughout the year. Our results show that MILP is the more suitable technique, and the schedule quality metric shows FR is the preferred design. We have reported our results to the GEO-CAPE mission team to assist them making an informed decision for the next step in formulating this mission.
Robot Motion Planning for Pouring Liquids
Authors: Pan Zherong , Park Chonhyon , Manocha Dinesh
Published: September 2022

We present a new algorithm to compute a collision-free trajectory for a robot manipulator to pour liquid from one container to the other. Our formulation uses a physical fluid model to predicate its highly deformable motion. We present simulation guided and optimization based method to automatically compute the transferring trajectory. Instead of abstract or simplified liquid models, we use the full-featured and accurate Navier-Stokes model that provides the fine-grained information of velocity distribution inside the liquid body. Moreover, this information is used as an additional guiding energy term for the planner. One of our key contributions is the tight integration between the fine-grained fluid simulator, liquid transfer controller, and the optimization-based planner. We have implemented the method using hybrid particle-mesh fluid simulator (FLIP) and demonstrated its performance on 4 benchmarks, with different cup shapes and viscosity coefficients.
Experience-Based Robot Task Learning and Planning with Goal Inference
Authors: Mokhtari Vahid , Seabra Lopes Luis , J. Pinho Armando
Published: September 2022

Learning and deliberation are required to endow a robotwith the capabilities to acquire knowledge, perform a variety of tasks and interactions, and adapt to open-ended environments. This paper explores the notion of experience-based planning domains (EBPDs) for task-level learning and planning in robotics. EBPDs rely on methods for a robot to: (i) obtain robot activity experiences from the robot's performance; (ii) conceptualize each experience to a task model called activity schema; and (iii) exploit the learned activity schemata to make plans in similar situations. Experiences are episodic descriptions of plan-based robot activities including environment perception, sequences of applied actions and achieved tasks. The conceptualization approach integrates different techniques including deductive generalization, abstraction and feature extraction to learn activity schemata. A high-level task planner was developed to find a solution for a similar task by following an activity schema. In this paper, we extend our previous approach by integrating goal inference capabilities. The proposed approach is illustrated in a restaurant environment where a service robot learns how to carry out complex tasks.
Online Learning of Robot Soccer Free Kick Plans Using a Bandit Approach
Authors: Mendoza Juan Pablo , Simmons Reid , Veloso Manuela
Published: September 2022

This paper presents an online learning approach for teams of autonomous soccer robots to select free kick plans. In robot soccer, free kicks present an opportunity to execute plans with relatively controllable initial conditions. However, the effectiveness of each plan is highly dependent on the adversary, and there are few free kicks during each game, making it necessary to learn online from sparse observations. To achieve learning, we first greatly reduce the planning space by framing the problem as a contextual multi-armed bandit problem, in which the actions are a set of pre-computed plans, and the state is the position of the free kick on the field. During execution, we model the reward function for different free kicks using Gaussian Processes, and perform online learning using the Upper Confidence Bound algorithm. Results from a physics-based simulation reveal that the robots are capable of adapting to various different realistic opponents to maximize their expected reward during free kicks.
Tailoring Pattern Databases for Unsolvable Planning Instances
Authors: Ståhlberg Simon
Published: September 2022

There has been an astounding improvement in domain-independent planning for solvable instances over the last decades and planners have become increasingly efficient at constructing plans. However, this advancement has not been matched by a similar improvement for identifying unsolvable instances. In this paper, we specialise pattern databases for dead-end detection and, thus, for detecting unsolvable instances. We propose two methods of constructing pattern collections and show that spending any more time constructing the pattern collection is likely to be unproductive. In other words, very few other pattern collections within the given space bounds are able to detect more dead-ends. We show this by carrying out a novel statistical analysis: a large computer cluster has been used to approximate the limit of pattern collections with respect to dead-end detection for many unsolvable instances, and this information is used in the analysis of the proposed methods. Consequently, further improvement must come from combining pattern databases with other techniques, such as mutexes. Furthermore, we explain why one of the proposed methods tends to find significantly more unsolvable variable projections, which is desirable since they imply that the instance is unsolvable. Finally, we compare the best proposed method with the winner and the runner up of the first unsolvability international planning competition, and show that the method is competitive.
Symmetry Breaking in Star-Topology Decoupled Search
Authors: Gnad Daniel , Torralba Álvaro , Shleyfman Alexander , Hoffmann Joerg
Published: September 2022

Symmetry breaking is a well-known method for search reduction. It identifies state-space symmetries prior to search, and prunes symmetric states during search. A recent proposal, star-topology decoupled search, is to search not in the state space, but in a factored version thereof, which avoids the multiplication of states across leaf components in an underlying star-topology structure. We show that, despite the much more complex structure of search states -- so-called decoupled states -- symmetry breaking can be brought to bear in this framework as well. Starting from the notion of structural symmetries over states, we identify a sub-class of such symmetries suitable for star-topology decoupled search, and we show how symmetries from that sub-class induce symmetry relations over decoupled states. We accordingly extend the routines required for search pruning and solution reconstruction. The resulting combined method can be exponentially better than both its components in theory, and this synergetic advantage is also manifested in practice: empirically, our method reliably inherits the best of its base components, and often outperforms them both.
Using Hierarchical Constraints to Avoid Conflicts in Multi-Agent Pathfinding
Authors: Walker Thayne , Chan David , Sturtevant Nathan
Published: September 2022

Recent work in multi-agent path planning has provided a number of optimal and suboptimal solvers that can efficiently find solutions to problems of growing complexity. Solvers based on Conflict-Based Search (CBS) combine single-agent solvers with shared constraints between agents to find feasible solutions. Suboptimal variants of CBS introduce alternate heuristics to avoid conflicts. In this paper we study the multi-agent planning problem in the context of non-holonomic vehicles planning on a lattice. We propose that in addition to using heuristics to avoid conflicts, we can plan using a hierarchy of movement constraints to efficiently avoid conflicts. We develop a new extension to the CBS algorithm, CBS with constraint layering (CBS+CL), which iteratively applies different movement constraint models during the CBS planning process. Our results show that this approach allows us to solve for about 2.4 times more agents in the same amount of time when compared to regular CBS without using a constraint hierarchy.
Occupation Measure Heuristics for Probabilistic Planning
Authors: Trevizan Felipe , Thiébaux Sylvie , Haslum Patrik
Published: September 2022

For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. To remedy this situation, we explore the use of occupation measures, which represent the expected number of times a given action will be executed in a given state of a policy. By relaxing the well-known linear program that computes them, we derive occupation measure heuristics -- the first admissible heuristics for stochastic shortest path problems (SSPs) taking probabilities into account. We show that these heuristics can also be obtained by extending recent operator-counting heuristic formulations used in deterministic planning. Since the heuristics are formulated as linear programs over occupation measures, they can easily be extended to more complex probabilistic planning models, such as constrained SSPs (C-SSPs). Moreover, their formulation can be tightly integrated into i-dual, a recent LP-based heuristic search algorithm for (constrained) SSPs, resulting in a novel probabilistic planning approach in which policy update and heuristic computation work in unison. Our experiments in several domains demonstrate the benefits of these new heuristics and approach.
On the Exploitation of Automated Planning for Reducing Machine Tools Energy Consumption between Manufacturing Operations
Authors: Parkinson Simon , Longstaff Andrew , Fletcher Simon , Vallati Mauro , Chrpa Lukas
Published: September 2022

There has recently been an increased emphasis on reducing energy consumption in manufacturing, driven by the fluctuations in energy costs and the growing importance given to environmental impact of manufactured goods. Lots of attention has been given to the reduction of machine tools energy consumption, as they require large amounts of energy to perform manufacturing tasks. One area that has received relatively little interest, yet could harness great potential, is reducing energy consumption by planning machine activities between manufacturing operations, while the machine is not in use. The intuitive option --which is currently exploited in manufacturing-- is to leave the machine in a normal operating state in anticipation of the next manufacturing job. However, this is far from optimal due to the thermal deformation phenomenon, which usually require an energy-intensive warm-up cycle in order to bring all the components (e.g. spindle motor) into a suitable (stable) state for actual machining. Evidently, the use of this strategy comes with the associated commercial and environmental repercussions. In this paper, we investigate the exploitability of automated planning techniques for planning machine activities between manufacturing operations. We present a PDDL 2.2 formulation of the task that considers energy consumption, thermal deformation, and accuracy. We then demonstrate the effectiveness of the proposed approach using a case study which considers real-world data.
Efficient Motion Planning for Problems Lacking Optimal Substructure
Authors: Salzman Oren , Hou Brian , Srinivasa Siddhartha
Published: September 2022

We consider the motion-planning problem of planning a collision-free path of a robot in the presence of risk zones. The robot is allowed to travel in these zones but is penalized in a super-linear fashion for consecutive accumulative time spent there. We suggest a natural cost function that balances path length and risk-exposure time. Specifically, we consider the discrete setting where we are given a graph, or a roadmap, and we wish to compute the minimal-cost path under this cost function. Interestingly, paths defined using our cost function do not have an optimal substructure. Namely, subpaths of an optimal path are not necessarily optimal. Thus, the Bellman condition is not satisfied and standard graph-search algorithms such as Dijkstra cannot be used. We present a path-finding algorithm, which can be seen as a natural generalization of Dijkstra’s algorithm. Our algorithm runs in O ((n B · n) log(n B · n) + n B · m) time, where n and m are the number of vertices and edges of the graph, respectively, and n B is the number of intersections between edges and the boundary of the risk zone. We present simulations on robotic platforms demonstrating both the natural paths produced by our cost function and the computational efficiency of our algorithm.
Scalability of Route Planning Techniques
Authors: Blum Johannes , Storandt Sabine
Published: September 2022

In this paper, we thoroughly analyze the scaling behavior of several state-of-the-art route planning techniques for road networks, all of which rely on preprocessing. One goal is to determine which technique is most suitable to be used on huge networks. To be able to conduct scalability studies in a clean way, we first describe a new kind of road network generator that allows to produce road networks even larger than that of our planet with similar properties as real networks. We then carefully implement several preprocessing-based route planning techniques, as contraction hierarchies, hub labels and transit nodes, to study their space consumption as well as their search spaces in different sized networks. This allows to derive functions that describe their empirical scaling behavior for the first time. We also compare our functions to existing theoretical bounds. We show that several of our results can not be sufficiently explained by the theoretical investigations conducted so far. Hence our results encourage a further look for road network models that allow for better predictions.
Planning for Partial Observability by SAT and Graph Constraints
Authors: Pandey Binda , Rintanen Jussi
Published: September 2022

Chatterjee et al. have recently shown the utility of SAT in solving a class of planning problems with partial observability. A core component of their logical formulation of planning is constraints expressing s-t-reachability in directed graphs. In this work, we show that the scalability of the approach can be dramatically improved by using dedicated graph constraints, and that a far broader class of important planning problems can be expressed in terms of s-t-reachability and acyclicity constraints.
Bootstrapping LPs in Value Iteration for Multi-Objective and Partially Observable MDPs
Authors: Roijers Diederik , Walraven Erwin , Spaan Matthijs
Published: September 2022

Iteratively solving a set of linear programs (LPs) is a common strategy for solving various decision-making problems in Artificial Intelligence, such as planning in multi-objective or partially observable Markov Decision Processes (MDPs). A prevalent feature is that the solutions to these LPs become increasingly similar as the solving algorithm converges, because the solution computed by the algorithm approaches the fixed point of a Bellman backup operator. In this paper, we propose to speed up the solving process of these LPs by bootstrapping based on similar LPs solved previously. We use these LPs to initialize a subset of relevant LP constraints, before iteratively generating the remaining constraints. The resulting algorithm is the first to consider such information sharing across iterations. We evaluate our approach on planning in Multi-Objective MDPs (MOMDPs) and Partially Observable MDPs (POMDPs), showing that it solves fewer LPs than the state of the art, which leads to a significant speed-up. Moreover, for MOMDPs we show that our method scales better in both the number of states and the number of objectives, which is vital for multi-objective planning.
A Hybrid Genetic Algorithm for Parallel Machine Scheduling at Semiconductor Back-End Production
Authors: Adan Jelle , Adan Ivo , Akcay Alp , Van den Dobbelsteen Rick , Stokkermans Joep
Published: September 2022

This paper addresses batch scheduling at a back-end semiconductor plant of Nexperia. This complex manufacturing environment is characterized by a large product and batch size variety, numerous parallel machines with large capacity differences, sequence and machine dependent setup times and machine eligibility constraints. A hybrid genetic algorithm is proposed to improve the scheduling process, the main features of which are a local search enhanced crossover mechanism, two additional fast local search procedures and a user-controlled multi-objective fitness function. Testing with real-life production data shows that this multi-objective approach can strike the desired balance between production time, setup time and tardiness, yielding high-quality practically feasible production schedules.
Footprint Placement for Mosaic Imaging by Sampling and Optimization
Authors: Mitchell Scott , Valicka Christopher , Rowe Stephen , Zou Simon
Published: September 2022

We consider the problem of selecting a small set (mosaic) of sensor images (footprints) whose union covers a twodimensional Region Of Interest (ROI) on Earth. We take the approach of modeling the mosaic problem as a Mixed-Integer Linear Program (MILP). This allows solutions to this subproblem to feed into a larger remote-sensor collection-scheduling MILP. This enables the scheduler to dynamically consider alternative mosaics, without having to perform any new geometric computations. Our approach to set up the optimization problem uses maximal disk sampling and point-in-polygon geometric calculations. Footprints may be of any shape, even non-convex, and we show examples using a variety of shapes that may occur in practice. The general integer optimization problem can become computationally expensive for large problems. In practice, the number of placed footprints is within an order of magnitude of ten, making the time to solve to optimality on the order of minutes. This is fast enough to make the approach relevant for near real-time mission applications.We provide open source software for all our methods, “GeoPlace.”
Compiling Optimal Numeric Planning to Mixed Integer Linear Programming
Authors: Piacentini Chiara , Castro Margarita , Cire Andre , Beck J. Christopher
Published: September 2022

Compilation techniques in planning reformulate a problem into an alternative encoding for which efficient, off-the-shelf solvers are available. In this work, we present a novel mixed-integer linear programming (MILP) compilation for cost-optimal numeric planning with instantaneous actions. While recent works on the problem are restricted to actions that modify variables present in simple numeric conditions, our MILP formulation, in addition, handles linear conditions and linear action effects on numeric state variables. Such problems are particularly challenging due to the state-dependency of the action effects. Experiments show that our approach, in addition to being the state of the art for the more general problem class, is competitive with heuristic search-based planners on domains with only simple numeric conditions.
RMPD — A Recursive Mid-Point Displacement Algorithm for Path Planning
Authors: Li Fangda , Manerikar Ankit , Kak Avinash
Published: September 2022

Motivated by what is required for real-time path planning, the paper starts out by presenting RMPD, a new recursive ''local'' planner founded on the key notion that, unless made necessary by an obstacle, there must be no deviation from the shortest path between any two points, which would normally be a straight line path in the configuration space. Subsequently, we increase the power of RMPD by introducing the notion of cost-awareness into the algorithm to improve the path quality -- this is done by associating obstacle and smoothness costs with the currently selected path points and factoring those costs in choosing the best points for the next iteration. In this manner, the overall strategy in the cost-aware form of RMPD, cRMPD, combines the computational efficiency made possible by the recursive RMPD planner with the cost efficacy of a stochastic trajectory optimizer to rapidly produce high-quality local collision-free paths. Based on the test cases we have run, our experiments show that cRMPD can reduce planning time by up to two orders of magnitude as compared to RRT-Connect, while still maintaining a path length optimality equivalent to that of RRT*.
A Local Search Approach to Observation Planning with Multiple UAVs
Authors: Bit-Monnot Arthur , Bailon-Ruiz Rafael , Lacroix Simon
Published: September 2022

Observation planning for Unmanned Aerial Vehicles (UAVs) is a challenging task as it requires planning trajectories over a large continuous space and with motion models that can not be directly encoded into current planners. Furthermore, realistic problems often require complex objective functions that complicate problem decomposition. In this paper, we propose a local search approach to plan the trajectories of a fleet of UAVs on an observation mission. The strength of the approach lies in its loose coupling with domain specific requirements such as the UAV model or the objective function that are both used as black boxes. Furthermore, the Variable Neighborhood Search (VNS) procedure considered facilitates the adaptation of the algorithm to specific requirements through the addition of new neighborhoods. We demonstrate the feasibility and convenience of the method on a large joint observation task in which a fleet of fixed-wing UAVs maps wildfires over areas of a hundred square kilometers. The approach allows generating plans over tens of minutes for a handful of UAVs in matter of seconds, even when considering very short primitive maneuvers.
Minimizing Movement to Establish the Connectivity of Randomly Deployed Robots
Authors: Engin K. , Isler Volkan
Published: September 2022

We study the following connectivity formation problem: Robots equipped with radio transmitters with a bounded communication range are scattered over a large area. They would like to relocate so as to form a connected network as soon as possible. Where should each robot move? We present an $O(\sqrt{n})$-factor approximation algorithm for this problem when $n$ robots are initially distributed uniformly at random in a bounded area. In addition to analytical proofs, we verify the performance of our algorithm through simulations.
Handling Model Uncertainty and Multiplicity in Explanations via Model Reconciliation
Authors: Sreedharan Sarath , Chakraborti Tathagata﻿ , Kambhampati Subbarao
Published: September 2022

Model reconciliation has been proposed as a way for an agent to explain its decisions to a human who may have a different understanding of the same planning problem by explaining its decisions in terms of these model differences.However, often the human's mental model (and hence the difference) is not known precisely and such explanations cannot be readily computed.In this paper, we show how the explanation generation process evolves in the presence of such model uncertainty or incompleteness by generating {\em conformant explanations} that are applicable to a set of possible models.We also show how such explanations can contain superfluous informationand how such redundancies can be reduced using conditional explanations to iterate with the human to attain common ground. Finally, we will introduce an anytime version of this approach and empirically demonstrate the trade-offs involved in the different forms of explanations in terms of the computational overhead for the agent and the communication overhead for the human.We illustrate these concepts in three well-known planning domains as well as in a demonstration on a robot involved in a typical search and reconnaissance scenario with an external human supervisor.
Theoretical Foundations for Structural Symmetries of Lifted PDDL Tasks
Authors: Sievers Silvan , Röger Gabriele , Wehrle Martin , Katz Michael
Published: September 2022

We transfer the notion of structural symmetries to lifted planning task representations, based on abstract structures which we define to model planning tasks. We show that symmetries are preserved by common grounding methods and we shed some light on the relation to previous symmetry concepts used in planning. Using a suitable graph representation of lifted tasks, our experimental analysis of common planning benchmarks reveals that symmetries occur in the lifted representation of many domains. Our work establishes the theoretical ground for exploiting symmetries beyond their previous scope, such as for faster grounding and mutex generation, as well as for state space transformations and reductions.