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.

In a number of graph search-based planning problems, the value of the cost function that is being minimized also affects the set of possible actions at some or all the states in the graph. In such planning problems, the cost function typically becomes one of the state variables thereby increasing the dimensionality of the planning problem, and consequently the size of the graph that represents the problem. In this paper, we show how to avoid this increase in the dimensionality for weighted search (with bounded suboptimality) whenever the availability of the actions is monotonically non-increasing with the increase in the cost function.

Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has exponential complexity and becomes computationally prohibitive for problems with just a few robots. This work proposes an efficient and complete algorithm for solving a general class of multi-robot path planning problems, specifically those where there are at most n-2 robots in a connected graph of n vertices. The algorithm employs two primitives: a "push" operation where a robot moves toward its goal until no further progress can be made, and a "swap" operation that allows two robots to swap positions without altering the configuration of any other robot. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique has highly competitive computation time and easily scales to problems involving 100s of robots, solving them in under 5 seconds.

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.

Heuristic functions play an important role in drastically improving performance of satisficing planners based on greedy best-first search (GBFS). While automatic generation of heuristic functions (e.g., (Hoffmann and Nebel 2001; Helmert 2006)) enables state-of-the-art satisficing planners to solve very complicated planning problems including benchmarks in the International Planning Competitions, accurate evaluations of nodes still remain as a challenging task. Although GBFS is fundamental and powerful in planning, it has an essential drawback when heuristic functions return inaccurate estimates. Assume that a heuristic function underestimates the difficulties of unpromising nodes. Then, since GBFS must expand nodes with small heuristic values first, it spends most of time in searching only unpromising areas and delays moving to the promising part. Previous work tackles this issue by adding a diversity to search, which is an ability in simultaneously exploring different parts of the search space to bypass large errors in heuristic functions. Several algorithms combined with diversity (e.g., K-best-first search (KBFS) in (Felner, Kraus, and Korf 2003)) are empirically shown to be superior to naive best-first search algorithms. However, they still have limited diversity, since they do not immediately expand nodes mistakenly evaluated as very unpromising ones. This paper presents a new technique called diverse best-first search (DBFS) , which incorporates a diversity into search in a different way than previous search-based approaches. We show empirical results clearly showing that DBFS is effective in satisficing planning.

The rectangle-packing problem consists of finding an enclosing rectangle of smallest area that can contain a given set of rectangles without overlap. Our new benchmark includes rectangles of successively higher precision, a problem for the previous state-of-the-art, which enumerates all locations for placing rectangles. We instead limit these locations and bounding box dimensions to the set of subset sums of the rectangles' dimensions, allowing us to test 4,500 times fewer bounding boxes and solve N=9 over two orders of magnitude faster. Finally, on the open problem of the feasibility of packing a specific infinite series of rectangles into the unit square, we pack the first 50,000 such rectangles and conjecture that the entire infinite series can fit.

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.

The differential heuristic (DH) is an effective memory-based heuristic for explicit state spaces. In this paper, we aim to improve its performance and memory usage. We introduce a compression method for DHs which stores only a portion of the original uncompressed DH, while preserving enough information to enable efficient search. Compressed DHs (CDH) can be tuned to fit any size of memory, even smaller than the size of the state space.Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompress

Herein, we employ a genetic algorithm (GA) to obtaining solvers for both the difficult FreeCell puzzle and the slidingtile Discrete puzzles, also known as single-player games, are puzzle. Note that although from a computationalcomplexity an excellent problem domain for artificial intelligence research, point of view the Rush Hour puzzle is harder because they can be parsimoniously described yet (unless NP PSPACE), search spaces induced by typical instances are often hard to solve (Pearl 1984). A well-known, highly of FreeCell tend to be substantially larger than those popular example within the domain of discrete puzzles is the of Rush Hour, and thus far more difficult to solve. This is card game of FreeCell. Another highly popular game is the evidenced by the failure of standard search methods to solve sliding-tile puzzle, the traditional versions of which are the FreeCell, as opposed to their success in solving all 6x6 Rush 15-puzzle (4X4) and the 24-puzzle (5X5). State-of-the-art Hour problems without requiring any heuristics (Hauptman heuristics allow for fast solutions of arbitrary instances of et al. 2009).

In many domains, different actions have different costs. In this paper, we show that various kinds of best-first search algorithms are sensitive to the ratio between the lowest and highest operator costs. First, we take common benchmark domains and show that when we increase the ratio of operator costs, the number of node expansions required to find a solution increases. Second, we provide a theoretical analysis showing one reason this phenomenon occurs. We also discuss additional domain features that can cause this increased difficulty. Third, we show that searching using distance-to-go estimates can significantly ameliorate this problem. Our analysis takes an important step toward understanding algorithm performance in the presence of differing costs. This research direction will likely only grow in importance as heuristic search is deployed to solve real-world problems.