bluuebunny/crossref_metadata_2025 huggingface dataset:
Planning for Landing Site Selection in the Aerial Supply Delivery
Authors: Kushleyev Aleksandr , MacAllister Brian , Likhachev Maxim
Published: November 2022

In the aerial supply delivery problem, an un-manned aircraft needs to deliver supplies as close as possible to the desired goal location. This involves choosing and landing at a landing site that is closest to or most accessible from the desired goal location. The problem is complicated by the fact that the status of candidate landing sites is unknown before the mission begins, and instead the aircraft needs to compute a sequence according to which it flies and senses the candidate landing sites in order to land as quickly as possible. The problem of computing this sequence corresponds to planning under uncertainty about environment. In this paper, we show how it can be solved efficiently via a recently developed probabilistic planning framework, called Probabilistic Planning with Clear Preferences (PPCP). We show that the problem satisfies the Clear Preferences assumption required by PPCP,and therefore all the theoretical guarantees continue to hold. The experimental results in simulation show that our approachcan solve large-scale problems in real-time while experiments on a physical quad-rotor provide proof of concept.
Real-Time Adaptive A* with Depression Avoidance
Authors: Hernandez Carlos , Baier Jorge
Published: November 2022

Real-time search is a well known approach to solving search problems under tight time constraints. Recently, it has been shown that LSS-LRTA∗ , a well-known real-time search algorithm, can be improved when search is actively guided away of depressions. In this paper we investigate whether or not RTAA∗ can be improved in the same manner. We propose aRTAA∗ and daRTAA∗ , two algorithms based on RTAA∗ that avoid heuristic depressions. Both algorithms outperform RTAA∗ on standard path-finding tasks, obtaining better-quality solutions when the same time deadline is imposed on the duration of the planning episode. We prove, in addition, that both algorithms have good theoretical properties.
Graduated Fidelity Motion Planning
Authors: Pivtoraiko Mihail , Kelly Alonzo
Published: November 2022

This paper presents an approach to differentially constrained robot motion planning and efficient re-planning. Satisfaction of differential constraints is guaranteed by the search space which consists of motions that satisfy the constraints by construction. Any systematic replanning algorithm, e.g. D*, can be utilized to search the state lattice to find a motion plan that satisfies the differential constraints, and to repair it efficiently in the event of a change in the environment. Further efficiency is obtained by varying the fidelity of representation of the planning problem. High fidelity is utilized where it matters most, while it is lowered in the areas that do not affect the quality of the plan significantly. The paper presents a method of modifying the fidelity between replans, thereby enabling dynamic flexibility of the search space, while maintaining its compatibility with replanning algorithms. The approach is especially suited for mobile robotics applications in unknown challenging environments. We successfully applied the motion planner on a real robot: the planner featured 10Hz average replan rate on minimal computing hardware, while satisfying the car-like differential constraints.
On Improving the Quality of Solutions in Large-Scale Cooperative Multi-Agent Pathfinding
Authors: Wang Ko-Hsin , Botea Adi , Kilby Philip
Published: November 2022

Scaling up the number of simultaneously moving units in pathfinding problems to hundreds, or even thousands, is well beyond the capability of theoretically optimal algorithms in practice, which is consistent with existing intractability results. Significant scalability can be achieved by trading off solution optimality, which motivates evaluating the quality of suboptimal solutions, especially in instances much larger than can be handled by optimal algorithms. We consider pathfinding in uniform cost grid maps, and we study the solution quality using the three most common quality criteria, total travel distance, sum of actions, and makespan. We focus on MAPP, which has been shown as state-of-the-art in terms of scalability and success ratio (i.e., percentage of solved units) on realistic game grid maps. Until now, the quality of MAPP's solutions had not been as extensively analyzed. We introduced enhancements that significantly improve MAPP's solution quality. For example, its sum of actions is cut to half on average. MAPP becomes competitive in terms of solution quality with FAR and WHCA*, two successful algorithms from the literature. To evaluate the quality of suboptimal solutions in instances beyond the capability of optimal algorithms, we use lower bounds of optimal values to show our solutions have a reasonable quality. For example, MAPP's average total travel distance is 19 percent longer than the lower bound.
Efficiently Finding Optimal Winding-Constrained Loops in the Plane: Extended Abstract
Authors: Vernaza Paul , Narayanan Venkatraman , Likhachev Maxim
Published: November 2022

We present a method to efficiently find winding-constrained loops in the plane that are optimal with respect to a minimum- cost objective and in the presence of obstacles. Our approach is similar to a typical graph-based search for an optimal path in the plane, but with an additional state variable that encodes information about path homotopy. Upon finding a loop, the value of this state corresponds to a line integral over the loop that indicates how many times it winds around each obstacle, enabling us to reduce the problem of finding paths satisfying winding constraints to that of searching for paths to suitable states in this augmented state space. We give an intuitive in- terpretation of the method based on fluid mechanics and show how this yields a way to perform the necessary calculations efficiently. Results are given in which we use our method to find optimal routes for autonomous surveillance and intruder containment.
Preface
Authors: Borrajo Daniel , Felner Ariel , Korf Richard , Likhachev Maxim , Linares López Carlos , Ruml Wheeler , Sturtevant Nathan
Published: November 2022

Preface to the Proceedings of the Fifth Annual Symposium on Combinatorial Search held in Niagara Falls, Canada, July 2012.
Performance Analysis of Planning Portfolios
Authors: Núñez Sergio , Borrajo Daniel , Linares López Carlos
Published: November 2022

In recent years the concept of sequential portfolio has become an important topic to improve the performance of modern problem solvers, such as SAT engines or planners. The PbP planner and more recently Fast Downward Stone Soup are successful approaches in Automated Planning that follow this trend. However, neither a theoretical analysis nor formal definitions about sequential portfolios have been described. In this paper, we focus on studying how to evaluate the performance of planners defining a baseline for a set of problems. We present a general method based on Mixed-Integer Programming to define the baseline for a training data set. In addition to prior work, we also introduce a short empirical analysis of the utility of training problems to configure sequential portfolios.
Implementing Fast Heuristic Search Code
Authors: Burns Ethan , Hatem Matthew , Leighton Michael , Ruml Wheeler
Published: November 2022

Published papers rarely disclose implementation details. In this paper we show how such details can account for speedups of up to a factor of 28 for different implementations of the same algorithm. We perform an in-depth analysis of the most popular benchmark in heuristic search: the 15-puzzle. We study implementation choices in C++ for both IDA* and A* using the Manhattan distance heuristic. Results suggest that several optimizations deemed critical in folklore provide only small improvements while seemingly innocuous choices can play a large role. These results are important for ensuring that the correct conclusions are drawn from empirical comparisons
Real-Time Motion Planning with Dynamic Obstacles
Authors: Cannon Jarad , Rose Kevin , Ruml Wheeler
Published: November 2022

Robust robot motion planning in dynamic environments requires that actions be selected under real-time constraints. Existing heuristic search methods that can plan high-speed motions do not guarantee real-time performance in dynamic environments. Existing heuristic search methods for real-time planning in dynamic environments fail in the high-dimensional state space required to plan high-speed actions. In this paper, we present extensions to a leading planner for high-dimensional spaces, R*, that allow it to guarantee real-time performance, and extensions to a leading real-time planner, LSS-LRTA*, that allow it to succeed in dynamic motion planning. In an extensive empirical comparison, we show that the new methods are superior to the originals, providing new state-of-the-art search performance on this challenging problem.
Alternative Forms of Bounded Suboptimal Search
Authors: Valenzano Richard , Jabbari Arfaee Shahab , Thayer Jordan , Stern Roni
Published: November 2022

Previous research into bounded suboptimal search has focused on the development of epsilon-admissible algorithms which are guaranteed to return solutions that are no more than a factor larger than optimal. In this paper, we consider the problem of how to construct search algorithms that satisfy alternative types of guarantees such as an additive bound. This bounding paradigm requires that the cost of any solution found is no more than the optimal cost plus gamma, which is a user-defined constant. To this end, we provide theorems that define sufficient conditions for developing algorithms for arbitrary bounding paradigms when using best-first search, iterative deepening, or focal list-based search. We then show by experimentation that these theorems can be used to construct effective additively bounded algorithms.
Round-Based Public Transit Routing (Extended Abstract)
Authors: Delling Daniel , Pajor Thomas , Werneck Renato
Published: November 2022

We study the problem of computing all Pareto-optimal journeys in a dynamic public transit network for two criteria: arrival time and number of transfers. Existing algorithms consider this as a graph problem, and solve it using variants of Dijkstra's algorithm. Unfortunately, this leads to either high query times or suboptimal solutions. We take a different approach. We introduce RAPTOR, our novel round-based public transit router. Unlike previous algorithms, it is not Dijkstra-based, looks at each route (such as a bus line) in the network at most once per round, and can be made even faster with simple pruning rules and parallelization using multiple cores. Because it does not rely on preprocessing, RAPTOR works in fully dynamic scenarios. Moreover, it can be easily extended to handle flexible departure times or arbitrary additional criteria, such as fare zones. When run on London's complex public transportation network, RAPTOR computes all Pareto-optimal journeys between two random locations an order of magnitude faster than previous approaches, which easily enables interactive applications. This is an extended abstract of the paper published at ALENEX 2012.
Preface
Authors: Helmert Malte , Röger Gabriele
Published: November 2022

This volume contains the papers accepted for presentation at SoCS 2013, the Sixth Annual Symposium on Combinatorial Search, held in Leavenworth, WA, USA on July 11–13, 2013. SoCS 2013 was held in cooperation with AAAI and collocated with the Twenty-Seventh AAAI Conference (AAAI 2013) and the 10th Symposium on Abstraction, Reformulation, and Approximation (SARA 2013).
Throwing Darts: Random Sampling Helps Tree Search when the Number of Short Certificates Is Moderate
Authors: Dickerson John , Sandholm Tuomas
Published: November 2022

One typically proves infeasibility in satisfiability/constraint satisfaction (or optimality in integer programming) by constructing a tree certificate. However, deciding how to branch in the search tree is hard, and impacts search time drastically. We explore the power of a simple paradigm, that of throwing random darts into the assignment space and then using information gathered by that dart to guide what to do next. Such guidance is easy to incorporate into state-of-the-art solvers. This method seems to work well when the number of short certificates of infeasibility is moderate, suggesting the overhead of throwing darts can be countered by the information gained by these darts. We explore results supporting this suggestion both on instances from a new generator where the size and number of short certificates can be controlled, and on industral instances from the annual SAT competition.
GAC for a Linear Inequality and an Atleast Constraint with an Application to Learning Simple Polynomials
Authors: Razakarison Naina , Carlsson Mats , Beldiceanu Nicolas , Simonis Helmut
Published: November 2022

We provide a filtering algorithm achieving GAC for the conjunction of constraints atleast (b, [x(0),x(1),...,x(n-1)], V) and (a(0)*x(0) +...+ a(n-1)*x(n-1)) <= c,  where the atleast constraint enforcesb variables out of x(0), x(1), ..., x(n-1) to be assigned to avalue in the set V. This work was motivated by learning simplepolynomials, i.e. finding the coefficients of polynomialsin several variables from example parameter and function values.We additionally require that coefficients be integers, andthat most coefficients be assigned to zero or integers close to0. These problems occur in the context of learning constraintmodels from sample solutions of different sizes. Experimentswith this more global filtering show an improvement by severalorders of magnitude compared to handling the constraintsin isolation or with cost gcc, while also out-performing a0/1 MIP model of the problem.
Online Detection of Dead States in Real-Time Agent-Centered Search
Authors: Sharon Guni , Sturtevant Nathan , Felner Ariel
Published: November 2022

In this paper we introduce techniques for state pruning atruntime in a priori unknown domains. We describe how toidentify states that can be deleted from the state-space whenlooking for both optimal and suboptimal solutions. We discussgeneral graphs and special cases like 8-connected grids.Experimental results show a speed up of up to an order ofmagnitude when applying our techniques on real-time agentcenteredsearch problems.
Experimental Real-Time Heuristic Search Results in a Video Game
Authors: Burns Ethan , Kiesel Scott , Ruml Wheeler
Published: November 2022

In real-time domains such as video games, a planning algo- rithm has a strictly bounded time before it must return the next action for the agent to execute. We introduce a realistic video game benchmark domain that is useful for evaluating real-time heuristic search algorithms. Unlike previous bench- marks such as grid pathfinding and the sliding tile puzzle, this new domain includes dynamics and induces a directed graph. Using both the previous and new domains, we investigate sev- eral enhancements to a leading real-time search algorithm, LSS-LRTA*. We show experimentally that 1) it is not dif- ficult to outperform A* when optimizing goal achievement time, 2) it is better to plan after each action than to commit to multiple actions or to use a dynamically sized lookahead, 3) A*-based lookahead can cause undesirable actions to be selected, and 4) on-line de-biasing of the heuristic can lead to improved performance. We hope that this new domain and results will stimulate further research on applying real-time search to dynamic real-time domains.
Optimal-Generation Variants of EPEA*
Authors: Goldenberg Meir , Felner Ariel , Sturtevant Nathan , Holte Robert C. , Schaeffer Jonathan
Published: November 2022

It is known that A* is optimal with respect to the expanded nodes (Dechter and Pearl 1985) (D&P). The exact meaning of this optimality varies depending on the class of algorithms and instances over which A* is claimed to be optimal. A* does not provide any optimality guarantees with respect to the generated nodes. However, such guarantees may be critical for optimally solving instances of domains with a large branching factor. In this paper, we introduce two new variants of the recently introduced Enhanced Partial Expansion A* algorithm (EPEA*) (Felner et al. 2012). We leverage the results of D&P to show that these variants possess optimality with respect to the generated nodes in much the same sense as A* possesses optimality with respect to the expanded nodes. The results in this paper are theoretical. A study of the practical performance of the new variants is beyond the scope of this paper.
Finding Optimal Solutions to Sokoban Using Instance Dependent Pattern Databases
Authors: Pereira André , Ritt Marcus , Buriol Luciana
Published: November 2022

Pattern databases have been successfully applied to several problems. Their use assumes that the goal state is known, and once the pattern database is built, commonly it can be used by all instances. However, in Sokoban, before solving the puzzle, the goal position of each stone is unknown. Moreover, each Sokoban instance has its own state space search. In this paper we apply pattern databases to Sokoban. The proposed approach uses an instance decomposition, that allows multiple possible goal states to be abstracted into a single state. Thus, an instance dependent pattern database is employed. Experiments with the standard set of instances show that the proposed approach overcomes the current best lower bounds in initial states for several instances. Furthermore, three of these new best lower bounds match exactly with the optimal solution length. Finally, we run experiments of 5 million explored states for each instance. Nine instances were solved with optimality guarantees, while only four instances were solved under the same conditions by previous methods.
Multi-Agent Path Finding for Self Interested Agents
Authors: Bnaya Zahy , Stern Roni , Felner Ariel , Zivan Roie , Okamoto Steven
Published: November 2022

Multi-agent pathfinding (MAPF) deals with planning paths for individual agents such that a global cost function (e.g., the sum of costs) is minimized while avoiding collisions between agents. Previous work proposed centralized or fully cooperative decentralized algorithms assuming that agents will follow paths assigned to them. When agents are {\em self-interested}, however, they are expected to follow a path only if they consider that path to be their most beneficial option. In this paper we propose the use of a taxation scheme to implicitly coordinate self-interested agents in MAPF. We propose several taxation schemes and compare them experimentally. We show that intelligent taxation schemes can result in a lower total cost than the non coordinated scheme even if we take into consideration both travel cost and the taxes paid by agents.
Bounded Suboptimal Heuristic Search in Linear Space
Authors: Hatem Matthew , Stern Roni , Ruml Wheeler
Published: November 2022

It is commonly appreciated that solving search problems optimally can overrun time and memory constraints. Bounded suboptimal search algorithms trade increased solution cost for reduced solving time and memory consumption. However, even suboptimal search can overrun memory on large problems. The conventional approach to this problem is to combine a weighted admissible heuristic with an optimal linear space algorithm, resulting in algorithms such as Weighted IDA* (wIDA*). However, wIDA* does not exploit distance-to-go estimates or inadmissible heuristics, which have recently been shown to be helpful for suboptimal search. In this paper, we present a linear space analogue of Explicit Estimation Search (EES), a recent algorithm specifically designed for bounded suboptimal search. We call our method Iterative Deepening EES (IDEES). In an empirical evaluation, we show that IDEES dramatically outperforms wIDA* on domains with non-uniform edge costs and can scale to problems that are out of reach for the original EES.
To UCT, or not to UCT? (Position Paper)
Authors: Domshlak Carmel , Feldman Zohar
Published: November 2022

Monte-Carlo search is successfully used in simulation-based planning for various large-scale sequential decision problems, and the UCT algorithm seems to be the choice in most (if not all) such recent success stories. Based on some recent discoveries in theory and empirical analysis of Monte-Carlo search, here we argue that, if online sequential decision making is your problem, and Monte-Carlo tree search is your way to go, then UCT is unlikely to be the best fit for your needs.
Multi-Agent Planning with Mixed-Integer Programming and Adaptive Interaction Constraint Generation (Extended Abstract)
Authors: Calliess Jan-P. , Roberts Stephen
Published: November 2022

We consider multi-agent planning in which the agents' optimal plans are solutions to mixed-integer programs (MIP) that are coupled via integer constraints. While in principle, one could find the joint solution by combining the separate problems into one large joint centralized MIP, this approach rapidly becomes intractable for growing numbers of agents and large problem domains. To address this issue, we propose an iterative approach that combines conflict detection with constraint-generation whereby the agents plan repeatedly until all conflicts are resolved. In each planning iteration, the agents plan with as few other agents and interaction-constraints as possible. This yields an optimal method that can reduce computation markedly. We test our approach in the context of multi-agent collision avoidance in graphs with indivisible flows. Our initial simulations on randomized graph routing problems confirm predicted optimality and reduced computational effort.
Identifying Hierarchies for Fast Optimal Search
Authors: Uras Tansel , Koenig Sven
Published: November 2022

For some search problems, the graph is known beforehand and there is time to preprocess the graph to make the search faster. One such example is video games, where one can often preprocess maps before a game is released or while a map is loaded into memory. The data produced by preprocessing should use only a small amount of memory, and, in case they are generated during runtime, preprocessing should be fast. Search with Subgoal Graphs (Uras, Koenig, and Hernandez 2013) was a non-dominated optimal path-planning algorithm in the Grid-Based Path Planning Competitions 2012 and 2013. During a preprocessing phase, it computes a Simple Subgoal Graph from a given grid, which is analogous to a visibility graph for continuous terrain, and then partitions the vertices into global and local subgoals to obtain a Two-Level Subgoal Graph. During the path-planning phase, it performs an A* search over the subgoal graph that ignores local subgoals that are not relevant to the search, which significantly reduces the size of the graph being searched. This paper is an abstract of (Uras and Koenig 2014), which generalizes this partitioning process to any undirected graph and shows that it can be recursively applied to generate more than two levels, which reduces the size of the graph being searched even further. We call these graphs N-Level Graphs.
Invited Talks
Authors: Koenig Sven , Reinefeld Alexander
Published: November 2022

Abstracts of the invited talks presented at SoCS 2014.
Fast First-Move Queries through Run-Length Encoding
Authors: Strasser Ben , Harabor Daniel , Botea Adi
Published: November 2022

We introduce a novel preprocessing-based algorithm to solve the problem of determining the first arc of a shortest path in sparse graphs. Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix.
On Different Strategies for Eliminating Redundant Actions from Plans
Authors: Balyo Tomáš , Chrpa Lukáš , Kilani Asma
Published: November 2022

Satisficing planning engines are often able to generate plans in a reasonable time, however, plans are often far from optimal. Such plans often contain a high number of redundant actions, that are actions, which can be removed without affecting the validity of the plans. Existing approaches for determining and eliminating redundant actions work in polynomial time, however, do not guarantee eliminating the "best" set of redundant actions, since such a problem is NP-complete. We introduce an approach which encodes the problem of determining the "best" set of redundant actions (i.e. having the maximum total-cost) as a weighted MaxSAT problem. Moreover, we adapt the existing polynomial technique which greedily tries to eliminate an action and its dependants from the plan in order to eliminate more expensive redundant actions. The proposed approaches are empirically compared to existing approaches on plans generated by state-of-the-art planning engines on standard planning benchmarks.
A* with Lookahead Re-Evaluated
Authors: Bu Zhaoxing , Stern Roni , Felner Ariel , Holte Robert
Published: November 2022

A* with lookahead (AL*) is a variant of A* that performs a cost-bounded DFS lookahead from a node when it is generated. We show that the original version of AL* (AL*0) can, in some circumstances, fail to return an optimal solution because of the move pruning it does. We present two new versions, AL*1 and ELH, that we prove to always be correct and give conditions in which AL*0 is guaranteed to be correct. In our experiments with unit costs, AL*0 was usually the fastest AL* version, but its advantage was usually small. In our experiments with non-unit costs, AL*0 substantially outperforms both A* and IDA*. We also evaluate the idea of immediately expanding a generated node if it has the same f-value as its parent. We find that doing so causes AL* to require more memory and sometimes slows AL* down.
Non-Linear Merging Strategies for Merge-and-Shrink Based on Variable Interactions
Authors: Fan Gaojian , Müller Martin , Holte Robert
Published: November 2022

Merge-and-shrink is a general method for deriving accurate abstraction heuristics.We present two novel nonlinear merging strategies, UMC and MIASM, based on variable interaction. The principle underlying our methods is to merge strongly interacting variables early on. UMC measures variable interaction by weighted causal graph edges, and MIASM measures variable interaction in terms of the number of necessary states in the abstract space defined by the variables. The methods partition variables into clusters in which the variable interactions are strong, and merge variables within each cluster before merging the clusters. Experiment results show that our merging strategies outperform existing merging strategies in general and can produce heuristics that give perfect guidance for solving tasks that previous methods cannot even solve.
Exploiting the Rubik's Cube 12-Edge PDB by Combining Partial Pattern Databases and Bloom Filters
Authors: Sturtevant Nathan , Felner Ariel , Helmert Malte
Published: November 2022

Pattern Databases (PDBs) are a common form of abstraction-based heuristic whichare often compressed so that a large PDB can fit inmemory. Partial Pattern Databases (PPDBs) achieve this by storing only layersof the PDB which are close to the goal. This paper studies the problem of howto best compress and use the 457 GB 12-edge Rubik's cube PDB, suggesting anumber of ways that Bloom filters can be used to effectively compress PPDBs. Wethen develop a theoretical model of the common min compression approach and ourBloom filters, showing that the original method of compressed PPDBs can neverbe better than min compression. We conclude with experimental results showingthat Bloom filter compression of PPDBs provides superior performance to mincompression in Rubik's cube.
Improved Heuristic Search for Sparse Motion Planning Data Structures
Authors: Dobson Andrew , Bekris Kostas
Published: November 2022

Sampling-based methods provide efficient, flexible solutions for motion planning, even for complex, high-dimensional systems. Asymptotically optimal planners ensure convergence to the optimal solution, but produce dense structures. This work shows how to extend sparse methods achieving asymptotic near-optimality using multiple-goal heuristic search during graph constuction. The resulting method produces identical output to the existing Incremental Roadmap Spanner approach but in an order of magnitude less time.
PLEASE: Palm Leaf Search for POMDPs with Large Observation Spaces
Authors: Zhang Zongzhang , Hsu David , Lee Wee Sun , Lim Zhan Wei , Bai Aijun
Published: November 2022

This paper provides a novel POMDP planning method, called Palm LEAf SEarch (PLEASE), which allows the selection of more than one outcome when their potential impacts are close to the highest one during its forward exploration. Compared with existing trial-based algorithms, PLEASE can save considerable time to propagate the bound improvements of beliefs in deep levels of the search tree to the root belief because of fewer backup operations. Experiments showed that PLEASE scales up SARSOP, one of the fastest algorithms, by orders of magnitude on some POMDP tasks with large observation spaces.
Planning Single-Arm Manipulations with N-Arm Robots
Authors: Cohen Benjamin , Phillips Mike , Likhachev Maxim
Published: November 2022

Many robotic systems are comprised of two or more arms. Such systems range from dual-arm household manipulators to factory floors populated with a multitude of industrial robotic arms. While the use of multiple arms increases the productivity of the system and extends dramatically its workspace, it also introduces a number of challenges. One such challenge is planning the motion of the arm(s) required to relocate an object from one location to another. This problem is challenging because it requires reasoning over which arms and in which order should manipulate the object, finding a sequence of valid handoff locations between the consecutive arms and finally choosing the grasps that allow for successful handoffs. In this paper, we show how to exploit the characteristics of this problem in order to construct a planner that can solve it effectively. We analyze our approach experimentally on a number of simulated examples ranging from a 2-arm system operating at a table to a 3-arm system working at a bar and to a 4-arm system in a factory setting.
Delete Relaxations for Planning with State-Dependent Action Costs
Authors: Geißer Florian , Keller Thomas , Mattmüller Robert
Published: November 2022

Supporting state-dependent action costs in planning admits a more compact representation of many tasks. We generalize the additive heuristic and compute it by embedding decision-diagram representations of action cost functions into the RPG. We give a theoretical evaluation and present an implementation of the generalized additive heuristic. This allows us to handle even the hardest instances of the combinatorial Academic Advising domain from the IPPC 2014.
Heuristic Search and Receding-Horizon Planning in Complex Spacecraft Orbit Domains
Authors: Surovik David , Scheeres Daniel
Published: November 2022

Spacecraft missions to small celestial bodies face sensitive, strongly non-Keplerian dynamics that motivate the employment of automated sampling-based trajectory planning. However, the scarcity of onboard computing resources necessitates careful formulation of heuristics for efficiently searching the reachable sets, which exhibit complex and finely-detailed structure. We examine a global search heuristic that combines aspects of simulated annealing and hill-climbing to locate sparse regions of the planning domain that simultaneously satisfy numerous geometric and timing constraints associated with remote sensing objectives for points of interest on the central body surface. Subsequently, we demonstrate the use of a receding-horizon implementation of this maneuver-planning strategy to produce mission profiles that fulfill sets of such goals.
Search Problems in the Domain of Multiplication: Case Study on Anomaly Detection Using Markov Chains
Authors: Mirsky Yisroel , Cohen Aviad , Stern Roni , Felner Ariel , Rokack Lior , Elovici Yuval , Shapira Bracha
Published: November 2022

Most work in heuristic search focused on path finding problems in which the cost of a path in the state space is the sum of its edges' weights. This paper addresses a different class of path finding problems in which the cost of a path is the product of its weights. We present reductions from different classes of multiplicative path finding problems to suitable classes of additive path finding problems. As a case study, we consider the problem of finding least and most probable paths in a Markov Chain, where path cost corresponds to the probability of traversing it. The importance of this problem is demonstrated in an anomaly detection application for cyberspace security. Three novel anomaly detection metrics for Markov Chains are presented, where computing these metrics require finding least and most probable paths. The underlying Markov Chain is dynamically changing, and so fast methods for computing least and most probable paths are needed. We propose such methods based on the proposed reductions and using heuristic search algorithms.
The Spurious Path Problem in Abstraction
Authors: Fan Gaojian , Holte Robert
Published: November 2022

Abstraction is a powerful technique in search and planning. A fundamental problem of abstraction is that it can create spurious paths, i.e., abstract paths that do not correspond to valid concrete paths. In this paper, we define spurious paths as a generalization of spurious states. We show that spurious paths can be categorized into two types: state-independent spurious paths and state-specific spurious paths. We present a practical method that eliminates state-independent spurious paths, as well as state-specific spurious paths when integrated with mutex detection methods. We provide syntactical conditions under which our method can remove state-independent spurious paths completely. We demonstrate that eliminating spurious paths can improve a heuristic substantially, even in abstract spaces that are free of spurious states.
Solving the Snake in the Box Problem with Heuristic Search: First Results
Authors: Palombo Alon , Stern Roni , Puzis Rami , Felner Ariel , Kiesel Scott , Ruml Wheeler
Published: November 2022

Snake in the Box (SIB) is the problem of finding the longest simple path along the edges of an n-dimensional cube, subject to certain constraints. SIB has important applications in coding theory and communications. State of the art algorithms for solving SIB apply uninformed search with symmetry breaking techniques. We formalize this problem as a search problem and propose several admissible heuristics to solve it. Using the proposed heuristics is shown to have a huge impact on the number of nodes expanded and, in some configurations, on runtime. These results encourage further research in using heuristic search to solve SIB, and to solve maximization problems more generally.
Finding and Exploiting LTL Trajectory Constraints in Heuristic Search
Authors: Simon Salomé , Röger Gabriele
Published: November 2022

We suggest the use of linear temporal logic (LTL) for expressing declarative information about optimal solutions of search problems. We describe a general framework that associates LTLf formulas with search nodes in a heuristic search algorithm. Compared to previous approaches that integrate specific kinds of path information like landmarks into heuristic search, the approach is general, easy to prove correct and easy to integrate with other kinds of path information.
To Reopen or Not To Reopen in the Context of Weighted A*. Classifications of Different Trends (Extended Abstract)
Authors: Sepetnitsky Vitali , Felner Ariel
Published: November 2022

This paper studies the tradeoffs between reopening and not reopening nodes in the context of Weighted A*. A straightforward intuitive scenario is that reopening nodes results in finding shorter solutions than not reopening nodes, at the cost of expanding more nodes. In this paper we classify all possibile tendencies and show an example graph where different tendencies are evident only by varying the W parameter of WA* and without changing the structure of the graph. We then experimentally demonstrate the different tendencies on a number of domains. Finally, we provide experimental support that intelligent reopening polices might lead to better performance. This is a work in progress and we discuss several future directions.
Automated Transformation of PDDL Representations
Authors: Riddle Patricia , Barley Michael , Franco Santiago , Douglas Jordan
Published: November 2022

This paper describes a system that automatically transforms a PDDL encoding, calls a planner to solve the transformed representation, and translates the solution back into the original representation. The approach involves counting objects that are indistinguishable, rather than treating them as individuals, which eliminates some unnecessary combinatorial explosion.
No One SATPlan Encoding To Rule Them All
Authors: Balyo Tomáš , Barták Roman
Published: November 2022

Solving planning problems via translation to propositional satisfiability (SAT) is one of the most successful approaches to automated planning. An important aspect of this approach is the encoding, i.e., the construction of a propositional formula from a given planning problem instance. Numerous encoding schemes have been proposed in the recent years each aiming to outperform the previous encodings on the majority of the benchmark problems. In this paper we take a different approach. Instead of trying to develop a new encoding that is better for all kinds of benchmarks we take recently developed specialized encoding schemes and design a method to automatically select the proper encoding for a given planning problem instance. In the paper we also examine ranking heuristics for the Relaxed Relaxed Exists-Step encoding, which plays an important role in our algorithm. Experiments show that our new approach significantly outperforms the state-of-the-art encoding schemes when compared on the benchmarks of the 2011 International Planning Competition.
Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths
Authors: Krontiris Athanasios , Bekris Kostas
Published: November 2022

The typical objective of path planning is to find the shortest feasible path. Many times, however, there may be no solution given the existence of constraints, such as obstacles. In these cases, the minimum constraint removal problem asks for the minimum set of constraints that need to be removed from the state space to find a solution. Unfortunately, minimum constraint removal paths do not exhibit dynamic programming properties, i.e., subsets of optimum solutions are not necessarily optimal. Thus, searching for such solutions is computationally expensive. This leads to approximate methods, which balance the cost of computing a solution and its quality. This work investigates alternatives in this context and evaluates their performance in terms of such tradeoffs. Solutions that follow a bounded-length approach, i.e., searching for paths up to a certain length, seem to provide a good balance between minimizing constraints, computational cost and path length.
An Empirical Comparison of Any-Angle Path-Planning Algorithms
Authors: Uras Tansel , Koenig Sven
Published: November 2022

We compare five any-angle path-planning algorithms, Theta*, Block A*, Field D*, ANYA, and Any-Angle Subgoal Graphs in terms of solution quality and runtime. Any-angle path-planning is a fairly new research area, and no direct comparison exists between these algorithms. We implement each algorithm from scratch and use similar implementations to provide a fair comparison.
Path Planning in Dynamic Environments with Adaptive Dimensionality
Authors: Vemula Anirudh , Muelling Katharina , Oh Jean
Published: November 2022

Path planning in the presence of dynamic obstacles is a challenging problem due to the added time dimension in search space. In approaches that ignore the time dimension and treat dynamic obstacles as static, frequent re-planning is unavoidable as the obstacles move, and their solutions are generally sub-optimal and can be incomplete. To achieve both optimality and completeness, it is necessary to consider the time dimension during planning. The notion of adaptive dimensionality has been successfully used in high-dimensional motion planning such as manipulation of robot arms, but has not been used in the context of path planning in dynamic environments. In this paper, we apply the idea of adaptive dimensionality to speed up path planning in dynamic environments for a robot with no assumptions on its dynamic model. Specifically, our approach considers the time dimension only in those regions of the environment where a potential collision may occur, and plans in a low-dimensional state-space elsewhere. We show that our approach is complete and is guaranteed to find a solution, if one exists, within a cost sub-optimality bound. We experimentally validate our method on the problem of 3D vehicle navigation (x, y, heading) in dynamic environments. Our results show that the presented approach achieves substantial speedups in planning time over 4D heuristic-based A*, especially when the resulting plan deviates significantly from the one suggested by the heuristic.
Sleep Sets Meet Duplicate Elimination
Authors: Alkhazraji Yusra , Wehrle Martin
Published: November 2022

The sleep sets technique is a path-dependent pruning method for state space search. In the past, the combination of sleep sets with graph search algorithms that perform duplicate elimination has often shown to be error-prone. In this paper, we provide the theoretical basis for the integration of sleep sets with common search algorithms in AI that perform duplicate elimination. Specifically, we investigate approaches to safely integrate sleep sets with optimal (best-first) search algorithms. Based on this theory, we provide an initial step towards integrating sleep sets within A* and additional state pruning techniques like strong stubborn sets. Our experiments show slight, yet consistent improvements on the number of generated search nodes across a large number of standard domains from the international planning competitions.
Searching with a Corrupted Heuristic
Authors: Lelis Levi , Valenzano Richard , Nazar Gabriel , Stern Roni
Published: November 2022

Memory-based heuristics are a popular and effective class of admissible heuristic functions. However, corruptions to memory they use may cause these heuristics to become inadmissible. Corruption can be caused by the physical environment due to radiation and network errors, or it can be introduced voluntarily in order to decrease energy consumption. We introduce memory error correction schemes that do not require additional memory and exploit knowledge about the behavior of consistent heuristics. This is in contrast with error correcting code approaches which can limit the amount of corruption but at the cost of additional energy and memory consumption. Search algorithms using our methods are guaranteed to find a solution if one exists and its suboptimality is bounded. Moreover, our methods are resilient to any number of memory errors that may occur. An experimental evaluation is also provided to demonstrate the applicability of our approach.
Repair Policies for Not Reopening Nodes in Different Search Settings
Authors: Sepetnitsky Vitaly , Felner Ariel , Stern Roni
Published: November 2022

We examine two policies for reopening of nodes: never reopen (NR) and always reopen (AR). While there are circumstances where each policy isbeneficial, we observed empirically that NR is usually faster. However, NR may fail to return a solution of the desired quality in two scenarios:(1) in a bounded suboptimal search when inconsistent heuristics are usedand (2) in a bounded cost setting. To remedy this we provide two repair policies for NR when the desired quality was not obtained. The firstpolicy is to restart AR. The second policy is to repeatedly place the nodesthat were not reopened back in OPEN and continue with NR. Experimentalresults show that both repair polices outperform the AR policy.
Weighted Lateral Learning in Real-Time Heuristic Search
Authors: Bulitko Vadim , Sampley Alexander
Published: November 2022

Real-time heuristic search models an autonomous agent solving a search task. The agent operates in a real-time setting by interleaving local planning, learning and move execution. In this paper we propose a simple parametric algorithm that combines weighting with learning from multiple neighbors. Doing so breaks heuristic admissibility but allows the agent to escape heuristic depressions more quickly. We prove completeness of the algorithm and empirically compare it to several competitors more than twenty years apart. In a large-scale evaluation the new algorithm found better solutions than the recent algorithms, despite not learning additional information that they do. Finally, we study robustness of the algorithms to noise in the heuristic function — a desirable property in a physical implementation of real-time heuristic search. The new algorithm outperforms its contemporaries.
Trial-Based Heuristic Tree-search for Distributed Multi-Agent Planning
Authors: Schulte Tim , Nebel Bernhard
Published: November 2022

We present a novel search scheme for privacy-preserving multi-agent planning, inspired by UCT search. We compare the presented approach to classical multi-agent forward search and evaluate it based on benchmarks from the CoDMAP competition.
Machine Teaching as Search
Authors: Alfeld Scott , Zhu Xiaojin , Barford Paul
Published: November 2022

Machine teaching (MT) studies the task of designing a training set. Specifically, given a learner (e.g., an artificial neural network or a human) and a target model, a teacher aims to create a training set which results in the target model being learned. MT applications include optimal education design for human learners and computer security where adversaries aim to attack learning-based systems. In this work, we formulate pool-based MT as a state space search problem. We discuss the properties and challenges of the resulting problem and highlight opportunities for novel search techniques. In our preliminary study we use a beam search approach, and find that training and evaluating empirical risk of models dominate the run time of the search. Toward the goal of better search techniques for future work, we develop optimizations ranging from implementation details for specific learners to algorithm changes applicable to general blackbox learners. We conclude with a discussion of open problems and research directions.
Improving a Planner’s Performance through Online Heuristic Configuration of Domain Models
Authors: Vallati Mauro , Chrpa Lukás , McCluskey Thomas
Published: November 2022

The separation of planner logic from domain knowledge supports the use of reformulation and configuration techniques, such as macro-actions and entanglements, which transform the model representation in order to improve a planner’s performance. One drawback of such an approach is that it may require a potentially expensive training phase. In this paper, we introduce heuristic approaches for the online configuration of planning domain models. The proposed heuristics consider different aspects of PDDL-encoded operators for reordering such operators in the domain model, relying on the assumption that the way in which operators are encoded carries useful information about their expected use.
Shortest Path for K Goals
Authors: Stern Roni , Goldenberg Meir , Felner Ariel
Published: November 2022

In this paper we study the k goal search problem (kGS), which is the problem of solving k shortest path problems that share the same start state. Two fundamental heuristic search approaches are analyzed: searching for the k goals one at a time, or searching for all k goals together in a single pass. Key theoretical properties are established and a preliminary experimental evaluation is performed.