Ryan Luna

ICRA Conference 2014 Conference Paper

Fast stochastic motion planning with optimality guarantees using local policy reconfiguration

• Ryan Luna
• Morteza Lahijanian
• Mark Moll
• Lydia E. Kavraki

This work presents a framework for fast reconfiguration of local control policies for a stochastic system to satisfy a high-level task specification. The motion of the system is abstracted to a class of uncertain Markov models known as bounded-parameter Markov decision processes (BMDPs). During the abstraction, an efficient sampling-based method for stochastic optimal control is used to construct several policies within a discrete region of the state space in order for the system to transit between neighboring regions. A BMDP is then used to find an optimal strategy over the local policies by maximizing a continuous reward function; a new policy can be computed quickly if the reward function changes. The efficacy of the framework is demonstrated using a sequence of online tasks, showing that highly desirable policies can be obtained by reconfiguring existing local policies in just a few seconds.

AAAI Conference 2014 Conference Paper

Optimal and Efficient Stochastic Motion Planning in Partially-Known Environments

• Ryan Luna
• Morteza Lahijanian
• Mark Moll
• Lydia Kavraki

A framework capable of computing optimal control policies for a continuous system in the presence of both action and environment uncertainty is presented in this work. The framework decomposes the planning problem into two stages: an offline phase that reasons only over action uncertainty and an online phase that quickly reacts to the uncertain environment. Offline, a bounded-parameter Markov decision process (BMDP) is employed to model the evolution of the stochastic system over a discretization of the environment. Online, an optimal control policy over the BMDP is computed. Upon the discovery of an unknown environment feature during policy execution, the BMDP is updated and the optimal control policy is efficiently recomputed. Depending on the desired quality of the control policy, a suite of methods is presented to incorporate new information into the BMDP with varying degrees of detail online. Experiments confirm that the framework recomputes high-quality policies in seconds and is orders of magnitude faster than existing methods.

ICRA Conference 2013 Conference Paper

Anytime solution optimization for sampling-based motion planning

• Ryan Luna
• Ioan Alexandru Sucan
• Mark Moll
• Lydia E. Kavraki

Recent work in sampling-based motion planning has yielded several different approaches for computing good quality paths in high degree of freedom systems: path shortcutting methods that attempt to shorten a single solution path by connecting non-consecutive configurations, a path hybridization technique that combines portions of two or more solutions to form a shorter path, and asymptotically optimal algorithms that converge to the shortest path over time. This paper presents an extensible meta-algorithm that incorporates a traditional sampling-based planning algorithm with offline path shortening techniques to form an anytime algorithm which exhibits competitive solution lengths to the best known methods and optimizers. A series of experiments involving rigid motion and complex manipulation are performed as well as a comparison with asymptotically optimal methods which show the efficacy of the proposed scheme, particularly in high-dimensional spaces.

SoCS Conference 2013 Conference Paper

From Feasibility Tests to Path Planners for Multi-Agent Pathfinding

• Athanasios Krontiris
• Ryan Luna
• Kostas E. Bekris

Multi-agent pathfinding is an important challenge that relates to combinatorial search and has many applications, such as warehouse management, robotics and computer games. Finding an optimal solution is NP-hard and raises scalability issues for optimal solvers. Interestingly, however, it takes linear time to check the feasibility of an instance. These linear-time feasibility tests can be extended to provide path planners but to the best of the authors’ knowledge no such solver has been provided for general graphs. This work first describes a path planner that is inspired by a linear-time feasibility test for multi-agent pathfinding on general graphs. Initial experiments indicated reasonable scalability but worse path quality relative to existing suboptimal solutions. This led to the development of an algorithm that achieves both efficient running time and path quality relative to the alternatives and which finds a solution on available benchmarks. The paper outlines the relation of the final method to the feasibility tests and existing suboptimal planners. Experimental results evaluate the different algorithms, including an optimal solver.

SoCS Conference 2012 Conference Paper

Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives

• Qandeel Sajid
• Ryan Luna
• Kostas E. Bekris

Multi-agent pathfinding is a challenging combinatorial problem that involves multiple agents moving on a graph from a set of initial nodes to a set of desired goals without inter-agent collisions. Searching the composite space of all agents has exponential complexity and does not scale well. Decoupled methods are more efficient but are generally incomplete. There are, however, polynomial time algorithms, which utilize single or few-agents primitives with completeness guarantees. One limitation of these alternatives is that the resulting solution is sequential, where only one agent moves at a time. Such solutions are of low quality when compared to methods where multiple agents can move simultaneously. This work proposes an algorithm for multi-agent pathfinding that utilizes similar single-agent primitives but allows all agents to move in parallel. The paper describes the algorithm and its properties. Experimental comparisons suggest that the resulting paths are considerably better than sequential ones, even after a post-processing, parallelization step, as well as solutions returned by decoupled and coupled alternatives. The experiments also suggest good scalability and competitive computational performance.

AAAI Conference 2011 Conference Paper

An Efficient and Complete Approach for Cooperative Path-Finding

• Ryan Luna
• Kostas Bekris

IROS Conference 2011 Conference Paper

Efficient and complete centralized multi-robot path planning

• Ryan Luna
• Kostas E. Bekris

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 paper 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. This paper provides a full proof of completeness. The algorithm employs two primitives: “push”, where a robot moves toward its goal until no progress can be made, and “swap”, that allows two robots to swap positions without altering the position of any other robot. Additionally, this paper provides a smoothing procedure for improving solution quality. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique improves computation time and solution quality, while scaling to problems with 100s of robots, solving them in under 5 seconds.

SoCS Conference 2011 Conference Paper

Efficient and Complete Centralized Multi-Robot Path Planning

• Ryan Luna
• Kostas E. Bekris

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.

IJCAI Conference 2011 Conference Paper

Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees

• Ryan Luna
• Kostas E. Bekris

Cooperative path-finding can be abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. This paper proposes a fast algorithm that can provide completeness guarantees for a general class of problems without any assumptions about the graph's topology. Specifically, the approach can address any solvable instance where there are at most n-2 agents in a graph of size n. The algorithm employs two primitives: a "push" operation where agents move towards their goals up to the point that no progress can be made, and a "swap" operation that allows two agents to swap positions without altering the configuration of other agents. Simulated experiments are provided on hard instances of cooperative path-finding, including comparisons against alternative methods. The results are favorable for the proposed algorithm and show that the technique scales to problems that require high levels of coordination, involving hundreds of agents.

IROS Conference 2010 Conference Paper

Network-guided multi-robot path planning in discrete representations

• Ryan Luna
• Kostas E. Bekris

This work deals with problems where multiple robots move on a roadmap guided by wireless nodes that form a communication network. The nodes compute paths for the robots within their communication range given information about robots only in their vicinity and communicating only with neighbors. The objective is to compute paths that are collision-free, minimize the occurrence of deadlocks, as well as the time it takes to reach the robots' goals. This paper formulates this challenge as a distributed constraint optimization problem. This formulation lends itself to a message-passing solution that guarantees collision-avoidance despite only local knowledge of the world by the network nodes. Simulations on benchmarks that cannot be solved with coupled or simple decoupled schemes are used to evaluate parameters and study the scalability, path quality and computational overhead of the approach.