Author name cluster

Jory Denny

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.

15 papers

1 author row

ICRA Conference 2021 Conference Paper

A Fast and Approximate Medial Axis Sampling Technique

Jory Denny
David Qin
Hanglin Zhou

One key aspect to planning safe motions for a robot requires maintaining a minimum distance from obstacles. The medial axis, or the set of all points equidistant to two or more obstacles, is useful for planning in this context. However, it is computationally intensive to compute this structure directly. As such, prior research proposed directly sampling this structure to avoid its explicit computation. In this paper, we revisit the computational cost of these sampling-based techniques for motion planning, and we propose a novel approximation algorithm that significantly reduces the necessary collision detection invocations in generating samples near the medial axis. At its core, our technique approximates the clearance of a configuration by reasoning about the clearance of nearby configurations. Ultimately, our approach reduces the computational burden of planning on or near the medial axis.

IROS Conference 2018 Conference Paper

A Topology-Based Path Similarity Metric and its Application to Sampling-Based Motion Planning

Jory Denny
Kaiwen Chen
Hanglin Zhou

Many applications of robotic motion planning benefit from considering multiple homotopically distinct paths rather than a single path from start to goal. However, determining whether paths represent different homotopy classes can be difficult to compute. We propose metrics for efficiently approximating the homotopic similarity of two paths are, instead of verifying homotopy equivalence directly. We propose two metrics: (1) a naive application of local planning, a common subroutine of sampling-based motion planning, and (2) a novel approach that reasons about the topologically distinct portions of the workspace that a path visits. We present three applications of our metric to demonstrate its use and effectiveness: extracting topologically distinct paths from an existing roadmap, comparing paths for robot manipulators, and improving the computational efficiency of an existing sampling-based method, Path Deformation Roadmaps (PDRs), by over two orders of magnitude. We explore the trade-off between quality and computational efficiency in the proposed metrics.

IROS Conference 2016 Conference Paper

On the theory of user-guided planning

Jory Denny
Jonathan Colbert
Hongsen Qin
Nancy M. Amato

Sampling-based techniques are often employed to solve various complex motion planning problems -the problem of computing a valid path under various robot and/or obstacle constraints. As these methods are random in nature, the probability of their success is directly related to the expansiveness, or openness, of the underlying planning space. However, little is known theoretically in qualifying the conditions under which user (human)-guided approaches improve the efficiency of sampling-based planners. In this paper, we classify and create simplistic models of common user-guided approaches, and we extend the concept of expansiveness to analyze these models to understand both when and how much user-guidance aids sampling-based planners.

ICRA Conference 2014 Conference Paper

MARRT: Medial Axis biased rapidly-exploring random trees

Jory Denny
Evan Greco
Shawna L. Thomas
Nancy M. Amato

Motion planning is a difficult and widely studied problem in robotics. Current research aims not only to find feasible paths, but to ensure paths have certain properties, e. g. , shortest or safest paths. This is difficult for current state-of-the-art sampling-based techniques as they typically focus on simply finding any path. Despite this difficulty, sampling-based techniques have shown great success in planning for a wide range of applications. Among such planners, Rapidly-Exploring Random Trees (RRTs) search the planning space by biasing exploration toward unexplored regions. This paper introduces a novel RRT variant, Medial Axis RRT (MARRT), which biases tree exploration to the medial axis of free space by pushing all configurations from expansion steps towards the medial axis. We prove that this biasing increases the tree's clearance from obstacles. Improving obstacle clearance is useful where path safety is important, e. g. , path planning for robots performing tasks in close proximity to the elderly. Finally, we experimentally analyze MARRT, emphasizing its ability to effectively map difficult passages while increasing obstacle clearance, and compare it to contemporary RRT techniques.

ICRA Conference 2014 Conference Paper

Robust online belief space planning in changing environments: Application to physical mobile robots

Ali-Akbar Agha-Mohammadi
Saurav Agarwal
Aditya Mahadevan
Suman Chakravorty
Daniel Tomkins
Jory Denny
Nancy M. Amato

Motion planning in belief space (under motion and sensing uncertainty) is a challenging problem due to the computational intractability of its exact solution. The Feedback-based Information RoadMap (FIRM) framework made an important theoretical step toward enabling roadmap-based planning in belief space and provided a computationally tractable version of belief space planning. However, there are still challenges in applying belief space planners to physical systems, such as the discrepancy between computational models and real physical models. In this paper, we propose a dynamic replanning scheme in belief space to address such challenges. Moreover, we present techniques to cope with changes in the environment (e. g. , changes in the obstacle map), as well as unforeseen large deviations in the robot's location (e. g. , the kidnapped robot problem). We then utilize these techniques to implement the first online replanning scheme in belief space on a physical mobile robot that is robust to changes in the environment and large disturbances. This method demonstrates that belief space planning is a practical tool for robot motion planning.

ICRA Conference 2014 Conference Paper

Spark PRM: Using RRTs within PRMs to efficiently explore narrow passages

Kensen Shi
Jory Denny
Nancy M. Amato

Probabilistic RoadMaps (PRMs) have been successful for many high-dimensional motion planning problems. However, they encounter difficulties when mapping narrow passages. While many PRM sampling methods have been proposed to increase the proportion of samples within narrow passages, such difficult planning areas still pose many challenges. We introduce a novel algorithm, Spark PRM, that sparks the growth of Rapidly-expanding Random Trees (RRTs) from narrow passage samples generated by a PRM. The RRT rapidly generates further narrow passage samples, ideally until the passage is fully mapped. After reaching a terminating condition, the tree stops growing and is added to the roadmap. Spark PRM is a general method that can be applied to all PRM variants. We study the benefits of Spark PRM with a variety of sampling strategies in a wide array of environments. We show significant speedups in computation time over RRT, Sampling-based Roadmap of Trees (SRT), and various PRM variants.

ICRA Conference 2014 Conference Paper

UMAPRM: Uniformly sampling the medial axis

Hsin-Yi Yeh
Jory Denny
Aaron Lindsey
Shawna L. Thomas
Nancy M. Amato

Maintaining clearance, or distance from obstacles, is a vital component of successful motion planning algorithms. Maintaining high clearance often creates safer paths for robots. Contemporary sampling-based planning algorithms that utilize the medial axis, or the set of all points equidistant to two or more obstacles, produce higher clearance paths. However, they are biased heavily toward certain portions of the medial axis, sometimes ignoring parts critical to planning, e. g. , specific types of narrow passages. We introduce Uniform Medial Axis Probabilistic RoadMap (UMAPRM), a novel planning variant that generates samples uniformly on the medial axis of the free portion of C space. We theoretically analyze the distribution generated by UMAPRM and show its uniformity. Our results show that UMAPRM's distribution of samples along the medial axis is not only uniform but also preferable to other medial axis samplers in certain planning problems. We demonstrate that UMAPRM has negligible computational overhead over other sampling techniques and can solve problems the others could not, e. g. , a bug trap. Finally, we demonstrate UMAPRM successfully generates higher clearance paths in the examples.

IROS Conference 2013 Conference Paper

Adapting RRT growth for heterogeneous environments

Jory Denny
Marco Morales 0001
Samuel Rodríguez
Nancy M. Amato

Rapidly-exploring Random Trees (RRTs) are effective for a wide range of applications ranging from kinodynamic planning to motion planning under uncertainty. However, RRTs are not as efficient when exploring heterogeneous environments and do not adapt to the space. For example, in difficult areas an expensive RRT growth method might be appropriate, while in open areas inexpensive growth methods should be chosen. In this paper, we present a novel algorithm, Adaptive RRT, that adapts RRT growth to the current exploration area using a two level growth selection mechanism. At the first level, we select groups of expansion methods according to the visibility of the node being expanded. Second, we use a cost-sensitive learning approach to select a sampler from the group of expansion methods chosen. Also, we propose a novel definition of visibility for RRT nodes which can be computed in an online manner and used by Adaptive RRT to select an appropriate expansion method. We present the algorithm and experimental analysis on a broad range of problems showing not only its adaptability, but efficiency gains achieved by adapting exploration methods appropriately.

IROS Conference 2013 Conference Paper

Blind RRT: A probabilistically complete distributed RRT

Cesar Rodriguez
Jory Denny
Sam Ade Jacobs
Shawna L. Thomas
Nancy M. Amato

Rapidly-Exploring Random Trees (RRTs) have been successful at finding feasible solutions for many types of problems. With motion planning becoming more computationally demanding, we turn to parallel motion planning for efficient solutions. Existing work on distributed RRTs has been limited by the overhead that global communication requires. A recent approach, Radial RRT, demonstrated a scalable algorithm that subdivides the space into regions to increase the computation locality. However, if an obstacle completely blocks RRT growth in a region, the planning space is not covered and is thus not probabilistically complete. We present a new algorithm, Blind RRT, which ignores obstacles during initial growth to efficiently explore the entire space. Because obstacles are ignored, free components of the tree become disconnected and fragmented. Blind RRT merges parts of the tree that have become disconnected from the root. We show how this algorithm can be applied to the Radial RRT framework allowing both scalability and effectiveness in motion planning. This method is a probabilistically complete approach to parallel RRTs. We show that our method not only scales but also overcomes the motion planning limitations that Radial RRT has in a series of difficult motion planning tasks.

ICRA Conference 2013 Conference Paper

Lazy Toggle PRM: A single-query approach to motion planning

Jory Denny
Kensen Shi
Nancy M. Amato

Probabilistic RoadMaps (PRMs) are quite successful in solving complex and high-dimensional motion planning problems. While particularly suited for multiple-query scenarios and expansive spaces, they lack efficiency in both solving single-query scenarios and mapping narrow spaces. Two PRM variants separately tackle these gaps. Lazy PRM reduces the computational cost of roadmap construction for single-query scenarios by delaying roadmap validation until query time. Toggle PRM is well suited for mapping narrow spaces by mapping both C free and C obst, which gives certain theoretical benefits. However, fully validating the two resulting roadmaps can be costly. We present a strategy, Lazy Toggle PRM, for integrating these two approaches into a method which is both suited for narrow passages and efficient single-query calculations. This simultaneously addresses two challenges of PRMs. Like Lazy PRM, Lazy Toggle PRM delays validation of roadmaps until query time, but if no path is found, the algorithm augments the roadmap using the Toggle PRM methodology. We demonstrate the effectiveness of Lazy Toggle PRM in a wide range of scenarios, including those with narrow passages and high descriptive complexity (e. g. , those described by many triangles), concluding that it is more effective than existing methods in solving difficult queries.

IROS Conference 2013 Conference Paper

Multi-robot caravanning

Jory Denny
Andrew Giese
Aditya Mahadevan
Arnaud Marfaing
Rachel Glockenmeier
Colton Revia
Samuel Rodríguez
Nancy M. Amato

We study multi-robot caravanning, which is loosely defined as the problem of a heterogeneous team of robots visiting specific areas of an environment (waypoints) as a group. After formally defining this problem, we propose a novel solution that requires minimal communication and scales with the number of waypoints and robots. Our approach restricts explicit communication and coordination to occur only when robots reach waypoints, and relies on implicit coordination when moving between a given pair of waypoints. At the heart of our algorithm is the use of leader election to efficiently exploit the unique environmental knowledge available to each robot in order to plan paths for the group, which makes it general enough to work with robots that have heterogeneous representations of the environment. We implement our approach both in simulation and on a physical platform, and characterize the performance of the approach under various scenarios. We demonstrate that our approach can successfully be used to combine the planning capabilities of different agents.

ICRA Conference 2012 Conference Paper

A scalable method for parallelizing sampling-based motion planning algorithms

Sam Ade Jacobs
Kasra Manavi
Juan Burgos
Jory Denny
Shawna L. Thomas
Nancy M. Amato

This paper describes a scalable method for parallelizing sampling-based motion planning algorithms. It subdivides configuration space (C-space) into (possibly overlapping) regions and independently, in parallel, uses standard (sequential) sampling-based planners to construct roadmaps in each region. Next, in parallel, regional roadmaps in adjacent regions are connected to form a global roadmap. By subdividing the space and restricting the locality of connection attempts, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We show that our method is general enough to handle a variety of planning schemes, including the widely used Probabilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algorithms. We compare our approach to two other existing parallel algorithms and demonstrate that our approach achieves better and more scalable performance. Our approach achieves almost linear scalability on a 2400 core LINUX cluster and on a 153, 216 core Cray XE6 petascale machine.

ICRA Conference 2012 Conference Paper

The Toggle Local Planner for sampling-based motion planning

Jory Denny
Nancy M. Amato

Sampling-based solutions to the motion planning problem, such as the probabilistic roadmap method (PRM), have become commonplace in robotics applications. These solutions are the norm as the dimensionality of the planning space grows, i. e. , d >; 5. An important primitive of these methods is the local planner, which is used for validation of simple paths between two configurations. The most common is the straight-line local planner which interpolates along the straight line between the two configurations. In this paper, we introduce a new local planner, Toggle Local Planner (Toggle LP), which extends local planning to a two-dimensional subspace of the overall planning space. If no path exists between the two configurations in the subspace, then Toggle LP is guaranteed to correctly return false. Intuitively, more connections could be found by Toggle LP than by the straight-line planner, resulting in better connected roadmaps. As shown in our results, this is the case, and additionally, the extra cost, in terms of time or storage, for Toggle LP is minimal. Additionally, our experimental analysis of the planner shows the benefit for a wide array of robots, with DOF as high as 70.

IROS Conference 2011 Conference Paper

Toggle PRM: Simultaneous mapping of C-free and C-obstacle - a study in 2D -

Jory Denny
Nancy M. Amato

Motion planning is known to be difficult. Probabilistic planners have made great advances, but still have difficulty for problems that require planning in narrow passages or on surfaces in C space. This work proposes Toggle PRM, a new methodology for PRMs that simultaneously maps both free and obstacle space. In this paper, we focus on 2 DOF problems and show that mapping both spaces leads to increased sampling density in narrow passages and to improved overall efficiency as compared to previous sampling based approaches.

ICRA Conference 2011 Conference Paper

Toward realistic pursuit-evasion using a roadmap-based approach

Samuel Rodríguez
Jory Denny
Juan Burgos
Aditya Mahadevan
Kasra Manavi
Luke Murray
Anton Kodochygov
Takis Zourntos

In this work, we describe an approach for modeling and simulating group behaviors for pursuit-evasion that uses a graph-based representation of the environment and integrates multi-agent simulation with roadmap-based path planning. Our approach can be applied to more realistic scenarios than are typically studied in most previous work, including agents moving in 3D environments such as terrains, multi-story buildings, and dynamic environments. We also support more realistic three-dimensional visibility computations that allow evading agents to hide in crowds or behind hills. We demonstrate the utility of this approach on mobile robots and in simulation for a variety of scenarios including pursuit-evasion and tag on terrains, in multi-level buildings, and in crowds.