Author name cluster

Kevin Rose

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

SoCS Conference 2012 Conference Paper

Real-Time Motion Planning with Dynamic Obstacles

Jarad Cannon
Kevin Rose
Wheeler Ruml

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.

Details

SoCS Conference 2011 Conference Paper

Best-First Search for Bounded-Depth Trees

Kevin Rose
Ethan Burns
Wheeler Ruml

Tree search is a common technique for solving constraint satisfaction and combinatorial optimization problems. The most popular strategies are depth-first search and limited discrepancy search. Aside from pruning or ordering the children of each node, these algorithms do not adapt their search order to take advantage of information that becomes available during search, such as heuristic scores or leaf costs. We present a framework called best-leaf-first search (BLFS) that uses this additional information to estimate the cost of taking discrepancies in the search tree and then attempts to visit leaves in a best-first order. In this way, BLFS brings the idea of best-first search from shortest path problems to the areas of constraint satisfaction and combinatorial optimization. Empirical results demonstrate that this new dynamic approach results in better search performance than previous static search strategies on two very different domains: structured CSPs and the traveling salesman problem.

Details