In the multi-agent path-finding (MAPF) problem a plan is needed to move a set of agents from their initial location to their goals without collisions. In this paper we introduce and study the k -robust MAPF problem, where we seek a plan that is robust to k unexpected delays per agent. We say that a plan π is k -robust if it does not have any k - delay conflicts. Informally, this means that no conflicts will occur even if some of the agents are delayed by up to k time steps. The problem we address in this paper is how to find optimal sum-of-costs k -robust plans.

Any-angle path finding on grids is an important problem with applications in autonomous robot navigation. In this paper, we show that a well-known pre-processing technique, namely subgoal graphs, originally proposed for (non any-angle) 8-connected grids, can be straightforwardly adapted to the 2 k neighborhoods, a family of neighborhoods that allow an increasing number of movements (and angles) as k is increased. This observation yields a pathfinder that computes 2 k -optimal paths very quickly. Compared to ANYA, an optimal true any-angle planner, over a variety of benchmarks, our planner is one order of magnitude faster while being less than 0.0005% suboptimal. Important to our planner's performance was the development of an iterative 2 k heuristic, linear in k, which is also a contribution of this paper.

We investigate GPU-based parallelization of Iterative-Deepening A* (IDA*). We show that straightforward thread-based parallelization techniques which were previously proposed for massively parallel SIMD processors perform poorly due to warp divergence and load imbalance. We propose Block-Parallel IDA* (BPIDA*), which assigns the search of a subtree to a block (a group of threads with access to fast shared memory) rather than a thread. On the 15-puzzle, BP-IDA* on a NVIDIA GRID K520 with 1536 CUDA cores achieves a speedup of 4.98 compared to a highly optimized sequential IDA* implementation on a Xeon E5-2670 core.

Pattern databases are among the strongest known heuristics for many classical search benchmarks such as sliding-tile puzzles, the 4-peg Towers of Hanoi puzzles, Rubik's Cube, and TopSpin. Min-compression is a generally applicable technique for augmenting pattern database heuristics that has led to marked experimental improvements in some settings, while being ineffective in others. We provide a theoretical explanation for these experimental phenomena by studying the interaction between the ranking function used to order abstract states in a pattern database, the compression scheme used to abstract states, and the dependencies between state variables in the problem representation.

Dynamic Potential Search (DPS) is a recently introduced search algorithm that returns a bounded-suboptimal cost solution. DPS orders nodes in the open-list based on their potential which is a combination of both the g - and h -values of a node. In this paper we study the behavior of DPS on weighted graphs. In particular, we develop a new variant of DPS, called DPSU which calculates the potential by counting one for each edge regardless of its costs. We develop an eager version and a restrained version of DPSU. We then compare all these algorithms on a number of weighted graphs and study the pros and cons of each of them.

A* is optimal among admissible unidirectional algorithms when searching with a consistent heuristic. Recently, similar optimality bounds have been established for bidirectional search but, no practical algorithm is guaranteed to always achieve this bound. In this paper we study the nature of the number of nodes that must be expanded in any front-to-end bidirectional search. We present an efficient algorithm for computing that number and show that a theoretical param-eterized generalization of MM, with the correct parameter, is the optimal front-to-end bidirectional search. We then experimentally compare various algorithms and show how far they are from optimal.

In the Any-Angle Pathfinding problem, the goal is to find the shortest path between a pair of vertices on a uniform square grid, that is not constrained to any fixed number of possible directions over the grid. Visibility Graphs are a known optimal algorithm for solving the problem with the use of pre-processing. However, Visibility Graphs are known to perform poorly in terms of running time, especially on large, complex maps. In this paper, we introduce two improvements over the Visibility Graph Algorithm to compute optimal paths. Sparse Visibility Graphs (SVGs) are constructed by pruning unnecessary edges from the original Visibility Graph. Edge N-Level Sparse Visibility Graphs (ENLSVGs) is a hierarchical SVG built by iteratively pruning non-taut paths. We also introduce Line-of-Sight Scans, a faster algorithm for building Visibility Graphs over a grid. SVGs run much faster than Visibility Graphs by reducing the average vertex degree. ENLSVGs, a hierarchical algorithm, improves this further, especially on larger maps, with millisecond runtimes even on 6000 x 6000 maps. On large maps, with the use of pre-processing, these algorithms are at least an order of magnitude faster than existing algorithms like Visibility Graphs, Anya and Theta*.

Most state-of-the-art satisfiability (SA T) solvers are capable of solving large application instances with efficient branching heuristics. The VSIDS heuristic is widely used because of its robustness. This paper focuses on the inherent ties in VSIDS and proposes a new branching heuristic called TB-VSIDS, which attempts to break the ties with the consideration of the interplay between the branching heuristic and learned clauses. However, a branching heuristic cannot cover all problems, and its performance improves when combined with an appropriate configuration. Therefore, we also propose a hybrid model of branching heuristics based on random forest. The efficiencies of TBVSIDS and hybrid branching heuristics are evaluated on benchmarks in SA T Competitions. By constructing a model that reduces the overfitting problem, we hope to realize a hybrid branching heuristic that is widely applicable to other solvers.

Multi-agent pathfinding (MAPF) is an area of expanding research interest. At the core of this research area, numerous diverse search-based techniques were developed in the past 6 years for optimally solving MAPF under the sum-of-costs objective function. In this paper we survey these techniques, while placing them into the wider context of the MAPF field of research. Finally, we provide analytical and experimental comparisons that show that no algorithm dominates all others in all circumstances. We conclude by listing important future research directions.

For self-driving cars and other smart transport to be successfully integrated in the real-world, the safety of passengers and pedestrians must be ensured. In the world of intelligent machines, perception answers the question: what is around me? This situational awareness is paramount for safe operation of autonomous vehicles in real-world environments. Scientists working in this field point to robotic perception as fundamental in equipping machines with a semantic understanding of the world, so that they can reliably identify objects and make informed predictions and actions. Michael Milford, Associate Professor at Queensland University of Technology (QUT), is a leading robotics researcher working to improve perception and more in autonomous vehicles, conducting his research at the intersection of robotics, neuroscience and computer vision.