Robot Task and Motion Planning

@misc{solis2023adaptive,
title={Adaptive Robot Coordination: A Subproblem-based Approach for Hybrid Multi-Robot Motion Planning},
author={Irving Solis and James Motes and Mike Qin and Marco Morales and Nancy M. Amato},
year={2023},
eprint={2312.08554},
archivePrefix={arXiv},
primaryClass={cs.RO}
}

This work presents Adaptive Robot Coordination (ARC), a novel hybrid framework for multi-robot motion planning (MRMP) that employs local subproblems to resolve inter-robot conflicts. ARC creates subproblems centered around conflicts, and the solutions represent the robot motions required to resolve these conflicts. The use of subproblems enables an inexpensive hybrid exploration of the multi-robot planning space. ARC leverages the hybrid exploration by dynamically adjusting the coupling and decoupling of the multi-robot planning space. This allows ARC to adapt the levels of coordination efficiently by planning in decoupled spaces, where robots can operate independently, and in coupled spaces where coordination is essential. ARC is probabilistically complete, can be used for any robot, and produces efficient cost solutions in reduced planning times. Through extensive evaluation across representative scenarios with different robots requiring various levels of coordination, ARC demonstrates its ability to provide simultaneous scalability and precise coordination. ARC is the only method capable of solving all the scenarios and is competitive with coupled, decoupled, and hybrid baselines.

@misc{mcbeth2023hypergraphbased,
title={Hypergraph-based Multi-robot Motion Planning with Topological Guidance},
author={Courtney McBeth and James Motes and Marco Morales and Nancy M. Amato},
year={2023},
eprint={2311.10176},
archivePrefix={arXiv},
primaryClass={cs.RO}
}

We present a multi-robot motion planning algorithm that efficiently finds paths for robot teams up to ten times larger than existing methods in congested settings with narrow passages in the environment. Narrow passages represent a source of difficulty for sampling-based motion planning algorithms. This problem is exacerbated for multi-robot systems where the planner must also avoid inter-robot collisions within these congested spaces, requiring coordination. Topological guidance, which leverages information about the robot's environment, has been shown to improve performance for mobile robot motion planning in single robot scenarios with narrow passages. Additionally, our prior work has explored using topological guidance in multi-robot settings where a high degree of coordination is required of the full robot group. This high level of coordination, however, is not always necessary and results in excessive computational overhead for large groups. Here, we propose a novel multi-robot motion planning method that leverages topological guidance to inform the planner when coordination between robots is necessary, leading to a significant improvement in scalability.

@misc{uwacu2023hierarchical,
title={Hierarchical Annotated Skeleton-Guided Tree-based Motion Planning},
author={Diane Uwacu and Ananya Yammanuru and Keerthana Nallamotu and Vasu Chalasani and Marco Morales and Nancy M. Amato},
year={2023},
eprint={2309.10801},
archivePrefix={arXiv},
primaryClass={cs.RO}
}

We present a hierarchical tree-based motion planning strategy, HAS-RRT, guided by the workspace skeleton to solve motion planning problems in robotics and computational biology. Relying on the information about the connectivity of the workspace and the ranking of available paths in the workspace, the strategy prioritizes paths indicated by the workspace guidance to find a valid motion plan for the moving object efficiently. In instances of suboptimal guidance, the strategy adapts its reliance on the guidance by hierarchically reverting to local exploration of the planning space. We offer an extensive comparative analysis against other tree-based planning strategies and demonstrate that HAS-RRT reliably and efficiently finds low-cost paths. In contrast to methods prone to inconsistent performance across different environments or reliance on specific parameters, HAS-RRT is robust to workspace variability.

@ARTICLE{10243143,
author={McBeth, Courtney and Motes, James and Uwacu, Diane and Morales, Marco and Amato, Nancy M.},
journal={IEEE Robotics and Automation Letters},
title={Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance},
year={2023},
volume={},
number={},
pages={1-8},
doi={10.1109/LRA.2023.3312980}}

Multi-robot motion planning (MRMP) is the problem of finding collision-free paths for a set of robots in a continuous state space. The difficulty of MRMP increases with the number of robots and is exacerbated in environments with narrow passages that robots must pass through, like warehouse aisles where coordination between robots is required. In single-robot settings, topology-guided motion planning methods have shown improved performance in these constricted environments. In this work, we extend an existing topology-guided single-robot motion planning method to the multi-robot domain to leverage the improved efficiency provided by topological guidance. We demonstrate our method's ability to efficiently plan paths in complex environments with many narrow passages, scaling to robot teams of size up to 25 times larger than existing methods in this class of problems. By leveraging knowledge of the topology of the environment, we also find higher-quality solutions than other methods.

@article{lee2021parallel,
title={Parallel hierarchical composition conflict-based search for optimal multi-agent pathfinding},
author={Lee, Hannah and Motes, James and Morales, Marco and Amato, Nancy M},
journal={IEEE Robotics and Automation Letters},
volume={6},
number={4},
pages={7001--7008},
year={2021},
publisher={IEEE}
}

In this article, we present a multi-robot task and motion planning method that, when applied to the rearrangement of objects by manipulators, results in solution times up to three orders of magnitude faster than the existing methods and successfully plans for problems with up to 20 objects, more than three times as many objects as comparable methods. We achieve this improvement by decomposing the planning space to consider manipulators alone, objects, and manipulators holding objects. We represent this decomposition with a hypergraph where vertices are decomposed elements of the planning spaces and hyperarcs are transitions between elements. The existing methods use graph-based representations where vertices are full composite spaces and edges are transitions between these. Using the hypergraph reduces the representation size of the planning space for multimanipulator object rearrangement, the number of hypergraph vertices scales linearly with the number of either robots or objects, while the number of hyperarcs scales quadratically with the number of robots and linearly with the number of objects. In contrast, the number of vertices and edges in graph-based representations scales exponentially in the number of robots and objects. We show that similar gains can be achieved for other multi-robot task and motion planning problems.

@ARTICLE{9851528,
author={Uwacu, Diane and Yammanuru, Ananya and Morales, Marco and Amato, Nancy M.},
journal={IEEE Robotics and Automation Letters},
title={Hierarchical Planning With Annotated Skeleton Guidance},
year={2022},
volume={7},
number={4},
pages={11055-11061},
doi={10.1109/LRA.2022.3196885}}

We present a hierarchical skeleton-guided motion planning algorithm to guide mobile robots. A good skeleton maps the connectivity of the subspace of c-space containing significant degrees of freedom and is able to guide the planner to find the desired solutions fast. However, sometimes the skeleton does not closely represent the free c-space, which often misleads current skeleton-guided planners. The hierarchical skeleton-guided planning strategy gradually relaxes its reliance on the workspace skeleton as C-space is sampled, thereby incrementally returning a sub-optimal path, a feature that is not guaranteed in the standard skeleton-guided algorithm. Experimental comparisons to the standard skeleton guided planners and other lazy planning strategies show significant improvement in roadmap construction run time while maintaining path quality for multi-query problems in cluttered environments.

@misc{https://doi.org/10.48550/arxiv.2210.08640,
doi = {10.48550/ARXIV.2210.08640},

url = {https://arxiv.org/abs/2210.08640},

author = {Attali, Amnon and Ashur, Stav and Love, Isaac Burton and McBeth, Courtney and Motes, James and Uwacu, Diane and Morales, Marco and Amato, Nancy M.},

keywords = {Robotics (cs.RO), Artificial Intelligence (cs.AI), FOS: Computer and information sciences, FOS: Computer and information sciences},

title = {Evaluating Guiding Spaces for Motion Planning},

publisher = {arXiv},

year = {2022},

copyright = {Creative Commons Attribution 4.0 International}
}

Randomized sampling based algorithms are widely used in robot motion planning due to the problem's intractability, and are experimentally effective on a wide range of problem instances. Most variants do not sample uniformly at random, and instead bias their sampling using various heuristics for determining which samples will provide more information, or are more likely to participate in the final solution. In this work, we define the motion planning guiding space, which encapsulates many seemingly distinct prior works under the same framework. In addition, we suggest an information theoretic method to evaluate guided planning which places the focus on the quality of the resulting biased sampling. Finally, we analyze several motion planning algorithms in order to demonstrate the applicability of our definition and its evaluation.

@article{chen2022insights,
title={Insights from an Industrial Collaborative Assembly Project: Lessons in Research and Collaboration},
author={Chen, Tan and Huang, Zhe and Motes, James and Geng, Junyi and Ta, Quang Minh and Dinkel, Holly and Abdul-Rashid, Hameed and Myers, Jessica and Mun, Ye-Ji and Lin, Wei-che and others},
journal={arXiv preprint arXiv:2205.14340},
year={2022}
}

Significant progress in robotics reveals new opportunities to advance manufacturing. Next-generation industrial automation will require both integration of distinct robotic technologies and their application to challenging industrial environments. This paper presents lessons from a collaborative assembly project between three academic research groups and an industry partner. The goal of the project is to develop a flexible, safe, and productive manufacturing cell for sub-centimeter precision assembly. Solving this problem in a high-mix, low-volume production line motivates multiple research thrusts in robotics. This work identifies new directions in collaborative robotics for industrial applications and offers insight toward strengthening collaborations between institutions in academia and industry on the development of new technologies.

@article{solis2019representation,
title={Representation-optimal multi-robot motion planning using conflict-based search},
author={Solis, Irving and Sandstr{\"o}m, Read and Motes, James and Amato, Nancy M},
journal={arXiv preprint arXiv:1909.13352},
year={2019}
}

Multi-Agent Motion Planning (MAMP) is the problem of computing feasible paths for a set of agents each with individual start and goal states within a continuous state space. Existing approaches can be split into coupled methods which provide optimal solutions but struggle with scalability or decoupled methods which provide scalable solutions but offer no optimality guarantees. Recent work has explored hybrid approaches that leverage the advantages of both coupled and decoupled approaches in an easier discrete subproblem, Multi-Agent Pathfinding (MAPF). In this work, we adapt recent developments in hybrid MAPF to the continuous domain of MAMP. We demonstrate the scalability of our method to manage groups of up to 32 agents, demonstrate the ability to handle up to 8 high-DOF manipulators, and plan for heterogeneous teams. In all scenarios, our approach plans significantly faster while providing higher quality solutions.

@ARTICLE{9144398,
author={R. {Sandström} and D. {Uwacu} and J. {Denny} and N. M. {Amato}},
journal={IEEE Robotics and Automation Letters},
title={Topology-Guided Roadmap Construction With Dynamic Region Sampling},
year={2020},
volume={5},
number={4},
pages={6161-6168},}

Many types of planning problems require discovery of multiple pathways through the environment, such as multi-robot coordination or protein ligand binding. The Probabilistic Roadmap (PRM) algorithm is a powerful tool for this case, but often cannot efficiently connect the roadmap in the presence of narrow passages. In this letter, we present a guidance mechanism that encourages the rapid construction of well-connected roadmaps with PRM methods. We leverage a topological skeleton of the workspace to track the algorithm's progress in both covering and connecting distinct neighborhoods, and employ this information to focus computation on the uncovered and unconnected regions. We demonstrate how this guidance improves PRM's efficiency in building a roadmap that can answer multiple queries in both robotics and protein ligand binding applications.

@inbook{10.1145/3388440.3414707,
author = {Uwacu, Diane and Ren, Abigail and Thomas, Shawna and Amato, Nancy M.},
title = {Using Guided Motion Planning to Study Binding Site Accessibility},
year = {2020},
isbn = {9781450379649},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3388440.3414707},
abstract = {Computational methods are commonly used to predict protein-ligand interactions. These methods typically search for regions with favorable energy that geometrically fit the ligand, and then rank them as potential binding sites. While this general strategy can provide good predictions in some cases, it does not do well when the binding site is not accessible to the ligand. In addition, recent research has shown that in some cases protein access tunnels play a major role in the activity and stability of the protein's binding interactions. Hence, to fully understand the binding behavior of such proteins, it is imperative to identify and study their access tunnels. In this work, we present a motion planning algorithm that scores protein binding site accessibility for a particular ligand. This method can be used to screen ligand candidates for a protein by eliminating those that cannot access the binding site. This method was tested on two case studies to analyze effects of modifying a protein's access tunnels to increase activity and/or stability as well as study how a ligand inhibitor blocks access to the protein binding site.},
booktitle = {Proceedings of the 11th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics},
articleno = {109},
numpages = {10}
}

Computational methods are commonly used to predict protein-ligand interactions. These methods typically search for regions with favorable energy that geometrically fit the ligand, and then rank them as potential binding sites. While this general strategy can provide good predictions in some cases, it does not do well when the binding site is not accessible to the ligand. In addition, recent research has shown that in some cases protein access tunnels play a major role in the activity and stability of the protein's binding interactions. Hence, to fully understand the binding behavior of such proteins, it is imperative to identify and study their access tunnels. In this work, we present a motion planning algorithm that scores protein binding site accessibility for a particular ligand. This method can be used to screen ligand candidates for a protein by eliminating those that cannot access the binding site. This method was tested on two case studies to analyze effects of modifying a protein's access tunnels to increase activity and/or stability as well as study how a ligand inhibitor blocks access to the protein binding site.

@article{denny-wafr-2016
, author = "Jory Denny and Read Sandstrom and Andrew Bregger and Nancy M. Amato"
, title = "Dynamic Region-biased Rapidly-exploring Random Trees"
, journal = "Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics (SPAR)"
, volume = "13"
, publisher = "Springer, Cham."
, pages = "640-655"
, year = "2020"
, doi = "10.1007/978-3-030-43089-4\_41"
, note = "Presented at the 2016 Workshop on the Algorithmic Foundations of Robotics (WAFR)."
}

Current state-of-the-art motion planners rely on samplingbased planning to explore the problem space for a solution. However, sampling valid configurations in narrow or cluttered workspaces remains a challenge. If a valid path for the robot correlates to a path in the workspace, then the planning process can employ a representation of the workspace that captures its salient topological features. Prior approaches have investigated exploiting geometric decompositions of the workspace to bias sampling; while beneficial in some environments, complex narrow passages remain challenging to navigate. In this work, we present Dynamic Region-biased RRT, a novel samplingbased planner that guides the exploration of a Rapidly-exploring Random Tree (RRT) by moving sampling regions along an embedded graph that captures the workspace topology. These sampling regions are dynamically created, manipulated, and destroyed to greedily bias sampling through unexplored passages that lead to the goal. We show that our approach reduces online planning time compared with related methods on a set of maze-like problems.

@article{ghosh-wafr-2018
, author = "Mukulika Ghosh and Shawna Thomas and Nancy M. Amato"
, title = "Fast Collision Detection for Motion Planning Using Shape Primitive Skeletons"
, journal = "Algorithmic Foundations of Robotics XIII. Springer Proceedings in Advanced Robotics (SPAR)"
, publisher = "Springer, Cham."
, volume = "14"
, pages = "36-51"
, year = "2020"
, doi = "10.1007/978-3-030-44051-0_3"
}

In many robotics applications, the environment (robots and obstacles) often have very complex geometries. These result in expensive primitive computations such as collision detection which in turn, affect the overall performance of these applications. Approximating the geometry is a common approach to optimize computation. Unlike other applications of geometric approximation where it is applied to one space (usually obstacle space), we approximate both obstacle and free workspace with a set of geometric shape primitives that are completely contained within the space and represent its topology (skeleton). We use these “shape primitive skeletons” to improve collision detection performance in motion planning algorithms. Our results show that the use of shape primitive skeletons improves the performance of standard collision detection methods in motion planning problems by 20–70% in our 2D and 3D test environments regardless of motion planning strategy. We also show how the same shape primitive skeletons can be used with robots of different sizes to improve the performance of collision detection operation.

@article{motes2020multi,
title={Multi-Robot Task and Motion Planning With Subtask Dependencies},
author={Motes, James and Sandstr{\"o}m, Read and Lee, Hannah and Thomas, Shawna and Amato, Nancy M},
journal={IEEE Robotics and Automation Letters},
volume={5},
number={2},
pages={3338--3345},
year={2020},
publisher={IEEE}
}

We present a multi-robot integrated task and motion method capable of handling sequential subtask dependencies within multiply decomposable tasks. We map the multi-robot pathfinding method, Conflict Based Search, to task planning and integrate this with motion planning to create TMP-CBS. TMP-CBS couples task decomposition, allocation, and planning to support cases where the optimal solution depends on robot availability and inter-team conflict avoidance. We show improved planning time for simpler task sets and generate optimal solutions w.r.t. the state space representation for a broader range of problems than prior methods.

@phdthesis{ghosh-phd-2019
, author = "Mukulika Ghosh"
, title = "Geometric Approximations and Their Application to Motion Planning"
, school = "Department of Computer Science and Engineering, Texas A\&M University"
, month = "August"
, year = "2019"
, note = "https://oaktrust.library.tamu.edu/handle/1969.1/187961"
}

Geometric approximation methods are a preferred solution to handle complexities (such as a large volume or complex features such as concavities) in geometric objects or environments containing them. Complexities often pose a computational bottleneck for applications such as motion planning. Exact resolution of these complexities might introduce other complexities such as unmanageable number of components. Hence, approximation methods provide a way to handle these complexities in a manageable state by trading off some accuracy. In this dissertation, two novel geometric approximation methods are studied: aggregation hierarchy and shape primitive skeleton. The aggregation hierarchy is a hierarchical clustering of polygonal or polyhedral objects. The shape primitive skeleton provides an approximation of bounded space as a skeleton of shape primitives. These methods are further applied to improve the performance of motion planning applications. We evaluate the methods in environments with 2D and 3D objects. The aggregation hierarchy groups nearby objects into individual objects. The hierarchy is created by varying the distance threshold that determines which objects are nearby. This creates levels of detail of the environment. The hierarchy of the obstacle space is then used to create a decom-position of the complementary space (i.e, free space) into a set of sampling regions to improve the efficiency and accuracy of the sampling operation of the sampling based motion planners. Our results show that the method can improve the efficiency (10 − 70% of planning time) of sampling based motion planning algorithms. The shape primitive skeleton inscribes a set of shape primitives (e.g., sphere, boxes) inside a bounded space such that they represent the skeleton or the connectivity of the space. We apply the shape primitive skeletons of the free space and obstacle space in motion planning problems to improve the collision detection operation. Our results also show the use of shape primitive skeleton in both spaces improves the performance of collision detectors (by 20 − 70% of collision detection time) used in motion planning algorithms. In summary, this dissertation evaluates how geometric approximation methods can be applied to improve the performance of motion planning methods, especially, sampling based motion planning methods

@article{motes2019interaction,
title={Interaction templates for multi-robot systems},
author={Motes, James and Sandstr{\"o}m, Read and Adams, Will and Ogunyale, Tobi and Thomas, Shawna and Amato, Nancy M},
journal={IEEE Robotics and Automation Letters},
volume={4},
number={3},
pages={2926--2933},
year={2019},
publisher={IEEE}
}

This letter describes a framework for multi-robot problems that require or utilize interactions between robots. Solutions consider interactions on a motion planning level to determine the feasibility and cost of the multi-robot team solution. Modeling these problems with current integrated task and motion planning (TMP) approaches typically requires reasoning about the possible interactions and checking many of the possible robot combinations when searching for a solution. We present a multi-robot planning method called Interaction Templates (ITs), which moves certain types of robot interactions from the task planner to the motion planner. ITs model interactions between a set of robots with a small roadmap. This roadmap is then tiled into the environment and connected to the robots’ individual roadmaps. The resulting combined roadmap allows interactions to be considered by the motion planner. We apply ITs to homogeneous and heterogeneous robot teams under both required and optional cooperation scenarios, which previously required a task planning method. We show improved performance over a current TMP planning approach.

@inproceedings{pattanshetti2019feasibility,
title={Feasibility Study of Robotic Needles with a Rotational Tip-Joint and Notch Patterns},
author={Pattanshetti, Shivanand and Sandstr{\"o}m, Read and Kottala, Abhishek and Amato, Nancy M and Ryu, Seok Chang},
booktitle={2019 International Conference on Robotics and Automation (ICRA)},
pages={1534--1540},
year={2019},
organization={IEEE}
}

In this paper, we present the design of a steerable needle with proximal notch patterns for compliance and an embedded rotational tip joint for articulation. The device is fabricated by laser machining NiTi tube so that an inner working channel exists (to enable delivery of fluids, drugs or microtools) and no assembly is required for the joints. We formulate its model based on the classical Cosserat Rod theory. This is extended with incremental state prediction and a simple spring model for tissue reaction to integrate into a planning algorithm based on Dynamic Region RRT which efficiently explores the needle's state space. The planner was initialized with a target zone and arbitrary anatomical obstacles before running simulations which propagated incremental state changes at every step while adhering to constraints based on the physical system. Finally, we demonstrate the steering capability of the needle through insertion tests into a phantom.

@article{mcmahon2018sampling,
title={Sampling-based motion planning with reachable volumes for high-degree-of-freedom manipulators},
author={McMahon, Troy and Thomas, Shawna and Amato, Nancy M},
journal={The International Journal of Robotics Research},
volume={37},
number={7},
pages={779--817},
year={2018},
publisher={SAGE Publications Sage UK: London, England}
}

Motion planning for constrained systems is a version of the motion planning problem in which the motion of a robot is limited by constraints. For example, one can require that a humanoid robot such as a PR2 remain upright by constraining its torso to be above its base or require that an object such as a bucket of water remain upright by constraining the vertices of the object to be parallel to the robot’s base. Grasping can be modeled by requiring that the end effectors of the robot be located at specified handle positions. Constraints might require that the robot remain in contact with a surface, or that certain joints of the robot remain in contact with each other (e.g., closed chains). Such problems are particularly difficult because the constraints form a manifold in C-space, and planning must be restricted to this manifold. High-degree-of-freedom motion planning and motion planning for constrained systems has applications in parallel robotics, grasping and manipulation, computational biology and molecular simulations, and animation. We introduce a new concept, reachable volumes, that are a geometric representation of the regions the joints and end effectors of a robot can reach, and use it to define a new planning space called RV-space where all points automatically satisfy a problem’s constraints. Visualizations of reachable volumes can enable operators to see the regions of workspace that different parts of the robot can reach. Samples and paths generated in RV-space naturally conform to constraints, making planning for constrained systems no more difficult than planning for unconstrained systems. Consequently, constrained motion planning problems that were previously difficult or unsolvable become manageable and in many cases trivial. We introduce tools and techniques to extend the state-of-the-art sampling-based motion planning algorithms to RV-space. We define a reachable volumes sampler, a reachable volumes local planner, and a reachable volumes distance metric. We showcase the effectiveness of RV-space by applying these tools to motion planning problems for robots with constraints on the end effectors and/or internal joints of the robot. We show that RV-based planners are more efficient than existing methods, particularly for higher-dimensional problems, solving problems with 1000 or more degrees of freedom for multi-loop and tree-like linkages.

@inproceedings{sandstrom-icra-2018
, author = "Read Sandstrom and Andrew Bregger and Ben Smith and Shawna Thomas and Nancy M. Amato"
, title = "Topological Nearest-Neighbor Filtering for Sampling-Based Planners"
, booktitle = "Proc. IEEE Int. Conf. Robot. Autom. (ICRA)"
, location = "Brisbane, Australia"
, month = "May"
, year = "2018"
, pages = "3053-3060"
, doi = "10.1109/ICRA.2018.8460896"
}

Nearest-neighbor finding is a major bottleneck for sampling-based motion planning algorithms. The cost of finding nearest neighbors grows with the size of the roadmap, leading to significant slowdowns for problems which require many configurations to find a solution. Prior work has investigated relieving this pressure with quicker computational techniques, such as kd-trees or locality-sensitive hashing. In this work, we investigate an alternative direction for expediting this process based on workspace connectivity. We present an algorithm called Topological Nearest-Neighbor Filtering, which employs a workspace decomposition to select a topologically relevant set of candidate neighbor configurations as a pre-processing step for a nearest-neighbor algorithm. We investigate the application of this filter to several varieties of RRT and demonstrate that the filter improves both nearest-neighbor time and overall planning performance.

@inproceedings{ebinger2018general,
title={A General and Flexible Search Framework for Disassembly Planning},
author={Ebinger, Timothy and Kaden, Sascha and Thomas, Shawna and Andre, Robert and Amato, Nancy M and Thomas, Ulrike},
booktitle={2018 IEEE International Conference on Robotics and Automation (ICRA)},
pages={1--8},
year={2018},
organization={IEEE}
}

We present a new general framework for disassembly sequence planning. This framework is versatile allowing different types of search schemes (exhaustive vs. preemptive), various part separation techniques, and the ability to group parts, or not, into subassemblies to improve the solution efficiency and parallelism. This enables a truly hierarchical approach to disassembly sequence planning. We demonstrate two different search strategies using this framework that can either yield a single solution quickly or provide a spectrum of solutions from which an optimal may be selected. We also develop a method for subassembly identification based on collision information. Our results show improved performance over an iterative motion planning based method for finding a single solution and greater functionality through hierarchical planning and optimal solution search.

@Inbook{Denny2018,
author="Denny, Jory
and Sandstr{\"o}m, Read
and Amato, Nancy M.",
editor="Bicchi, Antonio
and Burgard, Wolfram",
title="A General Region-Based Framework for Collaborative Planning",
bookTitle="Robotics Research: Volume 2",
year="2018",
publisher="Springer International Publishing",
address="Cham",
pages="563--579",
abstract="Sampling-based planning is a common method for solving motion planning problems. However, this paradigm falters in difficult scenarios, such as narrow passages. In contrast, humans can frequently identify these challenges and can sometimes propose an approximate solution. A recent method called Region Steering takes advantage of this intuition by allowing a user to define regions in the workspace to weight the search space for probabilistic roadmap planners. In this work, we extend Region Steering into a generalized Region-Based framework that is suitable for any sampling-based planning approach. We explore three variants of our framework for graph-based, tree-based, and hybrid planning methods. We evaluate these variants in simulations as a proof of concept. Our results demonstrate the benefits of our framework in reducing overall planning time.",
isbn="978-3-319-60916-4",
doi="10.1007/978-3-319-60916-4_32",
url="https://doi.org/10.1007/978-3-319-60916-4_32"
}

Sampling-based planning is a common method for solving motion planning problems. However, this paradigm falters in difficult scenarios, such as narrow passages. In contrast, humans can frequently identify these challenges and can sometimes propose an approximate solution. A recent method called Region Steering takes advantage of this intuition by allowing a user to define regions in the workspace to weight the search space for probabilistic roadmap planners. In this work, we extend Region Steering into a generalized Region-Based framework that is suitable for any sampling-based planning approach. We explore three variants of our framework for graph-based, tree-based, and hybrid planning methods. We evaluate these variants in simulations as a proof of concept. Our results demonstrate the benefits of our framework in reducing overall planning time.

@inproceedings{mcmahon2017manipulation,
title={Manipulation planning with directed reachable volumes},
author={McMahon, Troy and Sandstr{\"o}m, Read and Thomas, Shawna and Amato, Nancy M},
booktitle={2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
pages={4026--4033},
year={2017},
organization={IEEE}
}

Motion planning for manipulators with rotational joints is challenging because the actuation range for each link is constrained by the placement and orientation of other links. Thus, finding paths that avoid self-collision is non-trivial. However, rotational joints are often used in industrial robots. We develop a reparameterization of the planning problem called directed reachable volumes that provides an explicit representation of the workspace regions that the joints and end effectors can reach given the placement and orientation of other links. This formulation, while similar in spirit to prior reachable volume work, does not rely on the same restrictive assumptions that preclude prior work from handling rotational joints. We provide primitive planning operations that can be used in the context of state-of-the-art motion planning methods. We present experimental validation of directed reachable volumes by demonstrating a simulated pick-and-place scenario using realistic robots with rotational joints.

@INPROCEEDINGS{7759704,
author={J. {Denny} and J. {Colbert} and H. {Qin} and N. M. {Amato}},
booktitle={2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
title={On the theory of user-guided planning},
year={2016},
volume={},
number={},
pages={4794-4801},
doi={10.1109/IROS.2016.7759704}}

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.

@inproceedings{ghosh2016motion,
title={Motion planning using hierarchical aggregation of workspace obstacles},
author={Ghosh, Mukulika and Thomas, Shawna and Morales, Marco and Rodriguez, Sam and Amato, Nancy M},
booktitle={2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
pages={5716--5721},
year={2016},
organization={IEEE}
}

Sampling-based motion planning is the state-of-the-art technique for solving challenging motion planning problems in a wide variety of domains. While generally successful, their performance suffers from increasing problem complexity. In many cases, the full problem complexity is not needed for the entire solution. We present a hierarchical aggregation framework that groups and models sets of obstacles based on the currently needed level of detail. The hierarchy enables sampling to be performed using the simplest and most conservative representation of the environment possible in that region. Our results show that this scheme improves planner performance irrespective of the underlying sampling method and input problem. In many cases, improvement is significant, with running times often less than 60% of the original planning time.

@phdthesis{mcmahon2016sampling,
title={Sampling based motion planning with reachable volumes},
author={McMahon, Troy Anthony},
year={2016}
}

Motion planning for constrained systems is a version of the motion planning problem in which the motion of a robot is limited by constraints. For example, one can require that a humanoid robot such as a PR2 remain upright by constraining its torso to be above its base or require that an object such as a bucket of water remain upright by constraining the vertices of the object to be parallel to the robot’s base. Grasping can be modeled by requiring that the end effectors of the robot be located at specified handle positions. Constraints might require that the robot remain in contact with a surface, or that certain joints of the robot remain in contact with each other (e.g., closed chains). Such problems are particularly difficult because the constraints form a manifold in C-space, and planning must be restricted to this manifold. High degree of freedom motion planning and motion planning for constrained systems has applications in parallel robotics, grasping and manipulation, computational biology and molecular simulations, and animation. In this work, we introduce a new concept, reachable volumes, that are a geometric representation of the regions the joints and end effectors of a robot can reach, and use it to define a new planning space, called RV-space, where all points automatically satisfy a problem’s constraints. Visualizations of reachable volumes can enable operators to see the regions of workspace that different parts of the robot can reach. Samples and paths generated in RV-space naturally conform to constraints, making planning for constrained systems no more difficult than planning for unconstrained systems. Consequently, constrained motion planning problems that were previously difficult or unsolvable become manageable and in many cases trivial. We provide tools and techniques to extend the state of the art sampling based motion planning algorithms to RV-space. We define a reachable volume sampler, a reachable volume local planner and a reachable volume distance metric. We showcase the effectiveness of RV-space by applying these tools to motion planning problems for robots with constraints on the end effectors and/or internal joints of the robot. We show that RV-based planners are more efficient than existing methods, particularly for higher dimensional problems, solving problems with 1000+ degrees of freedom for multi-loop, and tree-like linkages.

@phdthesis{ekenna2016improved,
title={Improved sampling based motion planning through local learning},
author={Ekenna, Chinwe Pamela},
year={2016}
}

Every motion made by a moving object is either planned implicitly, e.g., human natural movement from one point to another, or explicitly, e.g., pre-planned information about where a robot should move in a room to effectively avoid colliding with obstacles. Motion planning is a well-studied concept in robotics and it involves moving an object from a start to goal configuration. Motion planning arises in many application domains such as robotics, computer animation (digital actors), intelligent CAD (virtual prototyping and training) and even computational biology (protein folding and drug design). Interestingly, a single class of planners, sampling-based planners have proven effective in all these domains. Probabilistic Roadmap Methods (PRMs) are one type of sampling-based planners that sample robot configurations (nodes) and connect them via viable local paths (edges) to form a roadmap containing representative feasible trajectories. The roadmap is then queried to find solution paths between start and goal configurations. Different PRM strategies perform differently given different input parameters, e.g., workspace environments and robot definitions. Motion planning, however, is computationally hard – it requires geometric path planning which has been shown to be PSPACE hard, complex representational issues for robots with known physical, geometric and temporal constraints, and challenging mapping/representing requirements for the workspace environment. Many important environments, e.g., houses, factories and airports, are heterogeneous, i.e., contain free, cluttered and narrow spaces. Heterogeneous environments, however, introduce a new set of problems for motion planning and PRM strategies because there is no ideal method suitable for all regions in the environment. In this work we introduce a technique that can adapt and apply PRM methods suitable for local regions in an environment. The basic strategy is to first identify a local region of the environment suitable for the current action based on identified neighbors. Next, based on past performance of methods in this region, adapt and pick a method to use at this time. This selection and adaptation is done by applying machine learning. By performing the local region creation in this dynamic fashion, we remove the need to explicitly partition the environment as was done in previous methods and which is difficult to do, slows down performance and includes the difficult process of determining what strategy to use even after making an explicit partitioning. Our method handles and removes these overheads. We show benefits of this approach in both planning robot motions and in protein folding simulations. We perform experiments on robots in simulation with different degrees of freedom and varying levels of heterogeneity in the environment and show an improvement in performance when our local learning method is applied. Protein folding simulations were performed on 23 proteins and we note an improvement in the quality of pathways produced with comparable performance in terms of time needed to build the roadmap.

@inproceedings{uwacu-wrlp-2016
, author = "Diane Uwacu and Chinwe Ekenna and Shawna Thomas and Nancy M. Amato"
, title = "The Impact of Approximate Methods on Local Learning in Motion Planning"
, booktitle = "1st International Workshop on Robot Learning and Planning (RLP 2016), in conjunction with RSS 2016"
, month = "June"
, year = "2016"
, note = "http://chitsazlab.org/robotics/rlp2016/RLP_2016_paper_11.html"
}

Machine learning methods have been applied to many motion planning algorithms including probabilistic roadmap methods (PRM). There are many variants of these methods and choosing the best one every time is hard and depends on local properties of the environment. A successful learning approach has been developed to offset this issue. This learning approach was applied to PRMs to help decide intelligently what method to utilize in dynamically created local regions of the environment or task space. It used exact neighbor finding approaches and removed the need to partition environments to get improved results. In this work we make further advances by introducing approximate neighbor finder methods. It has been established that approximate neighbor finding methods are faster than exact methods, still work well in connecting nodes to edges in PRMs, and that connection is robust to noise. We study what happens when noise is introduced into learning by using approximate methods instead of already studied exact methods. We show that the impact of noise on learning depends on how much learning needs to take place given the topology of the environment. Our results demonstrate a correlation between heterogeneity and the need for learning over a local region.

@inproceedings{Ghosh2015PlanningMF,
title={Planning motions for shape-memory alloy sheets},
author={Mukulika Ghosh and D. Tomkins and J. Denny and S. Rodr{\'i}guez and M. Morales and N. Amato},
year={2015}
}

Shape Memory Alloys (SMAs) are smart materials that can remember predefined shapes. A deformed SMA can transition to a trained shape by applying temperature changes to portions of the material. This reconfigurable property allows SMAs to be used in aeronautics, medicine, and other fields where dynamic re-engineering or actuation of components is required. In this work, we plan the motion of an SMA robot modeled as inflexible regions connected by flexible joints. In this work, we adapt an existing state-of-the-art motion planning algorithm to model the folding of an SMA robot from an unfolded flat state to a folded shape under feasibility constraints such as collision free motion and gravitational stability. Our results validate our model and algorithm by folding interesting 3D shapes using gravitationally stable motions, show flexibility in modeling various planning problems and significantly improved motions in comparable time to not using stability constraints.

@INPROCEEDINGS{7353825, author={C. {Ekenna} and D. {Uwacu} and S. {Thomas} and N. M. {Amato}}, booktitle={2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, title={Improved roadmap connection via local learning for sampling based planners}, year={2015}, volume={}, number={}, pages={3227-3234},}

Probabilistic Roadmap Methods (PRMs) solve the motion planing problem by constructing a roadmap (or graph) that models the motion space when feasible local motions exist. PRMs and variants contain several phases during roadmap generation i.e., sampling, connection, and query. Some work has been done to apply machine learning to the connection phase to decide which variant to employ, but it uses a global learning approach that is inefficient in heterogeneous situations. We present an algorithm that instead uses local learning: it only considers the performance history in the vicinity of the current connection attempt and uses this information to select good candidates for connection. It thus removes any need to explicitly partition the environment which is burdensome and typically difficult to do. Our results show that our method learns and adapts in heterogeneous environments, including a KUKA youBot with a fixed and mobile base. It finds solution paths faster for single and multi-query scenarios and builds roadmaps with better coverage and connectivity given a fixed amount of time in a wide variety of input problems. In all cases, our method outperforms the previous adaptive connection method and is comparable or better than the best individual method.

no bib for now.

Probabilistic Roadmap Methods (PRMs) solve the motion planning problem in two phases by sampling free configurations and connecting them together to build a map that is used to find a valid path. Existing algorithms are highly sensitive to the topology of the problem, and their efficiency depends on applying them to a compatible problem. Reinforcement learning has been applied to motion planning and rewards the action performed by planners during either sampling or connection, but not both. Previous work computed a global reward and action scheme, which saw a setback when heterogeneous environments were concerned. Local learning (connection) was recently introduced to offset this weakness identified during global learning, and there was some improvement in planner performance. These different learning schemes (global and local) have shown strengths and weaknesses individually. In this paper, we investigate local learning for sampling. We study what type of learning to apply when, and how the two phases of PRM roadmap construction interact, which has not been investigated before. We show the performance using each scheme on a KUKAyouBot, an 8 degree of freedom robot, and analyze what happens when they are all combined during roadmap construction

@INPROCEEDINGS{7139607, author={T. {McMahon} and S. {Thomas} and N. M. {Amato}}, booktitle={2015 IEEE International Conference on Robotics and Automation (ICRA)}, title={Reachable volume RRT}, year={2015}, volume={}, number={}, pages={2977-2984}, doi={10.1109/ICRA.2015.7139607}}

Reachable volumes are a new technique that allows one to efficiently restrict sampling to feasible/reachable regions of the planning space even for high degree of freedom and highly constrained problems. However, they have so far only been applied to graph-based sampling-based planners. In this paper we develop the methodology to apply reachable volumes to tree-based planners such as Rapidly-Exploring Random Trees (RRTs). In particular, we propose a reachable volume RRT called RVRRT that can solve high degree of freedom problems and problems with constraints. To do so, we develop a reachable volume stepping function, a reachable volume expand function, and a distance metric based on these operations. We also present a reachable volume local planner to ensure that local paths satisfy constraints for methods such as PRMs. We show experimentally that RVRRTs can solve constrained problems with as many as 64 degrees of freedom and unconstrained problems with as many as 134 degrees of freedom. RVRRTs can solve problems more efficiently than existing methods, requiring fewer nodes and collision detection calls. We also show that it is capable of solving difficult problems that existing methods cannot.

@INPROCEEDINGS{6942979, author={S. A. {Jacobs} and N. M. {Amato}}, booktitle={2014 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={The anatomy of a distributed motion planning roadmap}, year={2014}, volume={}, number={}, pages={3019-3026}, doi={10.1109/IROS.2014.6942979}}

In this paper, we evaluate and compare the quality and structure of roadmaps constructed from parallelizing sampling-based motion planning algorithms against that of roadmaps constructed using sequential planner. Also, we make an argument and provide experimental results that show that motion planning problems involving heterogenous environments (common in most realistic and large-scale motion planning) is a natural fit for spatial subdivision-based parallel processing. Spatial subdivision-based parallel processing approach is suited for heterogeneous environments because it allows for local adaption in solving a global problem while taking advantage of scalability that is possible with parallel processing.

@INPROCEEDINGS{6943082, author={T. {McMahon} and S. {Thomas} and N. M. {Amato}}, booktitle={2014 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={Sampling based motion planning with reachable volumes: Application to manipulators and closed chain systems}, year={2014}, volume={}, number={}, pages={3705-3712}, doi={10.1109/IROS.2014.6943082}}

Reachable volumes are a geometric representation of the regions the joints of a robot can reach. They can be used to generate constraint satisfying samples for problems including complicated linkage robots (e.g. closed chains and graspers). They can also be used to assist robot operators and to help in robot design.We show that reachable volumes have an O(1) complexity in unconstrained problems as well as in many constrained problems. We also show that reachable volumes can be computed in linear time and that reachable volume samples can be generated in linear time in problems without constraints. We experimentally validate reachable volume sampling, both with and without constraints on end effectors and/or internal joints. We show that reachable volume samples are less likely to be invalid due to self-collisions, making reachable volume sampling significantly more efficient for higher dimensional problems. We also show that these samples are easier to connect than others, resulting in better connected roadmaps. We demonstrate that our method can be applied to 262-dof, multi-loop, and tree-like linkages including combinations of planar, prismatic and spherical joints. In contrast, existing methods either cannot be used for these problems or do not produce good quality solutions.

@Inbook{Denny2015,
author="Denny, Jory
and Sandstr{\"o}m, Read
and Julian, Nicole
and Amato, Nancy M.",
editor="Akin, H. Levent
and Amato, Nancy M.
and Isler, Volkan
and van der Stappen, A. Frank",
title="A Region-Based Strategy for Collaborative Roadmap Construction",
bookTitle="Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics",
year="2015",
publisher="Springer International Publishing",
address="Cham",
pages="125--141",
abstract="Motion planningMotion planninghasDenny, JoryseenJulian, NicolemuchAmato, NancyattentionSandstrom, Readover the past two decades. A great deal of progress has been made in sampling-based planningSampling-based planning, whereby a planner builds an approximate representation of the planning space. While these planners have demonstrated success in many scenarios, there are still difficult problems where they lack robustness or efficiency, e.g., certain types of narrow spaces. Conversely, human intuition can often determine an approximate solution to these problems quite effectively, but humans lack the speed and precision necessary to perform the corresponding low-level tasks (such as collision checking) in a timely manner. In this work, we introduce a novel strategy called Region Steering in which the user and a PRM planner work cooperatively to map the space while maintaining the probabilistic completeness property of the PRM planner. Region Steering utilizes two-way communication to integrate the strengths of both the user and the planner, thereby overcoming the weaknesses inherent to relying on either one alone. In one communication direction, a user can input regions, or bounding volumes in the workspace, to bias sampling towards or away from these areas. In the other direction, the planner displays its progress to the user and colors the regions based on their perceived usefulness. We demonstrate that Region Steering provides roadmap customizability, reduced mapping time, and smaller roadmap sizes compared with fully automated PRMs, e.g., Gaussian PRM.",
isbn="978-3-319-16595-0",
doi="10.1007/978-3-319-16595-0_8",
url="https://doi.org/10.1007/978-3-319-16595-0_8"
}

Motion planning has seen much attention over the past two decades. A great deal of progress has been made in sampling-based planning, whereby a planner builds an approximate representation of the planning space. While these planners have demonstrated success in many scenarios, there are still difficult problems where they lack robustness or efficiency, e.g., certain types of narrow spaces. Conversely, human intuition can often determine an approximate solution to these problems quite effectively, but humans lack the speed and precision necessary to perform the corresponding low-level tasks (such as collision checking) in a timely manner. In this work, we introduce a novel strategy called Region Steering in which the user and a PRM planner work cooperatively to map the space while maintaining the probabilistic completeness property of the PRM planner. Region Steering utilizes two-way communication to integrate the strengths of both the user and the planner, thereby overcoming the weaknesses inherent to relying on either one alone. In one communication direction, a user can input regions, or bounding volumes in the workspace, to bias sampling towards or away from these areas. In the other direction, the planner displays its progress to the user and colors the regions based on their perceived usefulness. We demonstrate that Region Steering provides roadmap customizability, reduced mapping time, and smaller roadmap sizes compared with fully automated PRMs, e.g., Gaussian PRM.

@INPROCEEDINGS{6907820, author={T. {McMahon} and S. {Thomas} and N. M. {Amato}}, booktitle={2014 IEEE International Conference on Robotics and Automation (ICRA)}, title={Sampling-based motion planning with reachable volumes: Theoretical foundations}, year={2014}, volume={}, number={}, pages={6514-6521}, doi={10.1109/ICRA.2014.6907820}}

We introduce a new concept, reachable volumes, that denotes the set of points that the end effector of a chain or linkage can reach. We show that the reachable volume of a chain is equivalent to the Minkowski sum of the reachable volumes of its links, and give an efficient method for computing reachable volumes. We present a method for generating configurations using reachable volumes that is applicable to various types of robots including open and closed chain robots, tree-like robots, and complex robots including both loops and branches. We also describe how to apply constraints (both on end effectors and internal joints) using reachable volumes. Unlike previous methods, reachable volumes work for spherical and prismatic joints as well as planar joints. Visualizations of reachable volumes can allow an operator to see what positions the robot can reach and can guide robot design. We present visualizations of reachable volumes for representative robots including closed chains and graspers as well as for examples with joint and end effector constraints.

@INPROCEEDINGS{6906594, author={J. {Denny} and E. {Greco} and S. {Thomas} and N. M. {Amato}}, booktitle={2014 IEEE International Conference on Robotics and Automation (ICRA)}, title={MARRT: Medial Axis biased rapidly-exploring random trees}, year={2014}, volume={}, number={}, pages={90-97}, doi={10.1109/ICRA.2014.6906594}}

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.

@inproceedings{shi-icra-2014
, author = "Kensen Shi and Jory Denny and Nancy M. Amato"
, title = "Spark PRM: Using RRTs within PRMs to efficiently explore narrow passages"
, booktitle = "IEEE International Conference on Robotics and Automation (ICRA)"
, location = "Hong Kong"
, month = "May"
, year = "2014"
, pages = "4659-4666"
, doi =10.1109/ICRA.2014.6907540"
}

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.

@INPROCEEDINGS{6907711, author={H. C. {Yeh} and J. {Denny} and A. {Lindsey} and S. {Thomas} and N. M. {Amato}}, booktitle={2014 IEEE International Conference on Robotics and Automation (ICRA)}, title={UMAPRM: Uniformly sampling the medial axis}, year={2014}, volume={}, number={}, pages={5798-5803}, doi={10.1109/ICRA.2014.6907711}}

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.

@INPROCEEDINGS{6907324, author={A. {Giese} and D. {Latypov} and N. M. {Amato}}, booktitle={2014 IEEE International Conference on Robotics and Automation (ICRA)}, title={Reciprocally-Rotating Velocity Obstacles}, year={2014}, volume={}, number={}, pages={3234-3241}, doi={10.1109/ICRA.2014.6907324}}

Modern multi-agent systems frequently use high-level planners to extract basic paths for agents and then rely on local collision avoidance to ensure that the agents reach their destinations without colliding with one another or dynamic obstacles. One state-of-the-art local collision avoidance technique is Optimal Reciprocal Collision Avoidance (ORCA). Despite being fast and efficient for circular-shaped agents, ORCA may deadlock when polygonal shapes are used. To address this shortcoming, we introduce Reciprocally-Rotating Velocity Obstacles (RRVO). RRVO generalizes ORCA by introducing a notion of rotation for polygonally-shaped agents. This generalization permits more realistic motion than ORCA and does not suffer from as much deadlock. In this paper, we present the theory of RRVO and show empirically that it does not suffer from the deadlock issue ORCA has, permits agents to reach goals faster, and has a comparable collision rate at the cost of performance overhead quadratic in the (typically small) user-defined parameter δ.

@INPROCEEDINGS{6877290, author={A. {Fidel} and S. A. {Jacobs} and S. {Sharma} and N. M. {Amato} and L. {Rauchwerger}}, booktitle={2014 IEEE 28th International Parallel and Distributed Processing Symposium}, title={Using Load Balancing to Scalably Parallelize Sampling-Based Motion Planning Algorithms}, year={2014}, volume={}, number={}, pages={573-582}, doi={10.1109/IPDPS.2014.66}}

Motion planning, which is the problem of computing feasible paths in an environment for a movable object, has applications in many domains ranging from robotics, to intelligent CAD, to protein folding. The best methods for solving this PSPACE-hard problem are so-called sampling-based planners. Recent work introduced uniform spatial subdivision techniques for parallelizing sampling-based motion planning algorithms that scaled well. However, such methods are prone to load imbalance, as planning time depends on region characteristics and, for most problems, the heterogeneity of the sub problems increases as the number of processors increases. In this work, we introduce two techniques to address load imbalance in the parallelization of sampling-based motion planning algorithms: an adaptive work stealing approach and bulk-synchronous redistribution. We show that applying these techniques to representatives of the two major classes of parallel sampling-based motion planning algorithms, probabilistic roadmaps and rapidly-exploring random trees, results in a more scalable and load-balanced computation on more than 3,000 cores.

@MISC{Ekenna_adaptiveneighbor,
author = {Chinwe Ekenna and Shawna Thomas and Nancy M. Amato},
title = {Adaptive Neighbor Connection using Node Characterization},
year = {}
}

Abstract. Sampling-based motion planning has been successful in plan-ning the motion for a wide variety of robot types. An important primitive of these methods involves connecting nodes by selecting candidate neigh-bors and checking the path between them. Recently, an approach called Adaptive Neighbor Connection (ANC) was proposed to automate neigh-bor selection using machine learning techniques. It adaptively selects a neighbor connection strategy from a candidate set of options and learns which strategy to use by examining their success rates and costs. In this work, we extend ANC’s reward function by characterizing the types of nodes added (including information about their connectivity) after each connection attempt. In doing so, we gain insight into the na-ture of these nodes and their ability to improve roadmap quality. We also refine ANC’s cost function by considering the computation time spent during each connection attempt so as to potentially learn faster and more efficient connectors. We show improved performance over selecting a sin-gle connection strategy and over ignoring node characterization during learning. We present results in a variety of 2D and 3D environments and are able to solve queries in half the time on average compared to the best single connection strategy and to the original ANC work. 1

@article{denny-wafr-2012
, author = "Jory Denny and Nancy M. Amato"
, title = "Toggle PRM: A Coordinated Mapping of C-Free and C-Obstacle in Arbitrary Dimension"
, journal = "Algorithmic Foundations of Robotics X. Springer Tracts in Advanced Robotics (STAR)"
, volume = "86"
, publisher = "Springer, Berlin, Heidelberg."
, pages = "297-312"
, year = "2013"
, doi = "doi.org/10.1007/978-3-642-36279-8_18"
, note = "Presented at the 2012 Workshop on the Algorithmic Foundations of Robotics (WAFR)."
}

Motion planning has received much attention over the past 40 years. More than 15 years have passed since the introduction of the successful sampling-based approach known as the Probabilistic RoadMap Method (PRM). PRM and its many variants have demonstrated great success for some high-dimensional problems, but they all have some level of difficulty in the presence of narrow passages. Recently, an approach called Toggle PRM has been introduced whose performance does not degrade for 2-dimensional problems with narrow passages. In Toggle PRM, a simultaneous, coordinated mapping of both C-free and C-obst is performed and every connection attempt augments one of the maps – either validating an edge in the current space or adding a configuration ’witnessing’ the connection failure to the other space. In this paper, we generalize Toggle PRM to d-dimensions and show that the benefits of mapping both C-free and C-obst continue to hold in higher dimensions. In particular, we introduce a new narrow passage characterization, alpha-epsilon-separable narrow passages, which describes the types of passages that can be successfully mapped by Toggle PRM. Intuitively,alpha-epsilson-separable narrow passages are arbitrarily narrow regions of C-free that separate regions of C-obst , at least locally, such as hallways in an office building. We experimentally compare Toggle PRM with other methods in a variety of scenarios with different types of narrow passages and robots with up to 16 dof.

@article{doi:10.1177/0278364913501564,
author = {Ali-akbar Agha-mohammadi and Suman Chakravorty and Nancy M Amato},
title ={FIRM: Sampling-based feedback motion-planning under motion uncertainty and imperfect measurements},
journal = {The International Journal of Robotics Research},
volume = {33},
number = {2},
pages = {268-304},
year = {2014},
doi = {10.1177/0278364913501564},

URL = {
https://doi.org/10.1177/0278364913501564

},
eprint = {
https://doi.org/10.1177/0278364913501564

}
,
abstract = { In this paper we present feedback-based information roadmap (FIRM), a multi-query approach for planning under uncertainty which is a belief-space variant of probabilistic roadmap methods. The crucial feature of FIRM is that the costs associated with the edges are independent of each other, and in this sense it is the first method that generates a graph in belief space that preserves the optimal substructure property. From a practical point of view, FIRM is a robust and reliable planning framework. It is robust since the solution is a feedback and there is no need for expensive replanning. It is reliable because accurate collision probabilities can be computed along the edges. In addition, FIRM is a scalable framework, where the complexity of planning with FIRM is a constant multiplier of the complexity of planning with PRM. In this paper, FIRM is introduced as an abstract framework. As a concrete instantiation of FIRM, we adopt stationary linear quadratic Gaussian (SLQG) controllers as belief stabilizers and introduce the so-called SLQG-FIRM. In SLQG-FIRM we focus on kinematic systems and then extend to dynamical systems by sampling in the equilibrium space. We investigate the performance of SLQG-FIRM in different scenarios. }
}

In this paper we present feedback-based information roadmap (FIRM), a multi-query approach for planning under uncertainty which is a belief-space variant of probabilistic roadmap methods. The crucial feature of FIRM is that the costs associated with the edges are independent of each other, and in this sense it is the first method that generates a graph in belief space that preserves the optimal substructure property. From a practical point of view, FIRM is a robust and reliable planning framework. It is robust since the solution is a feedback and there is no need for expensive replanning. It is reliable because accurate collision probabilities can be computed along the edges. In addition, FIRM is a scalable framework, where the complexity of planning with FIRM is a constant multiplier of the complexity of planning with PRM. In this paper, FIRM is introduced as an abstract framework. As a concrete instantiation of FIRM, we adopt stationary linear quadratic Gaussian (SLQG) controllers as belief stabilizers and introduce the so-called SLQG-FIRM. In SLQG-FIRM we focus on kinematic systems and then extend to dynamical systems by sampling in the equilibrium space. We investigate the performance of SLQG-FIRM in different scenarios.

@INPROCEEDINGS{6696587, author={C. {Rodriguez} and J. {Denny} and S. A. {Jacobs} and S. {Thomas} and N. M. {Amato}}, booktitle={2013 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={Blind RRT: A probabilistically complete distributed RRT}, year={2013}, volume={}, number={}, pages={1758-1765}, doi={10.1109/IROS.2013.6696587}}

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.

@INPROCEEDINGS{6696589, author={J. {Denny} and M. {Morales} and S. {Rodriguez} and N. M. {Amato}}, booktitle={2013 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={Adapting RRT growth for heterogeneous environments}, year={2013}, volume={}, number={}, pages={1772-1778}, doi={10.1109/IROS.2013.6696589}}

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.

@INPROCEEDINGS{6580545, author={A. {Agha-mohammadi} and S. {Chakravorty} and N. M. {Amato}}, booktitle={2013 American Control Conference}, title={Graph-based stochastic control with constraints: A unified approach with perfect and imperfect measurements}, year={2013}, volume={}, number={}, pages={4581-4586}, doi={10.1109/ACC.2013.6580545}}

This paper is concerned with the problem of stochastic optimal control (possibly with imperfect measurements) in the presence of constraints. We propose a computationally tractable framework to address this problem. The method lends itself to sampling-based methods where we construct a graph in the state space of the problem, on which a Dynamic Programming (DP) is solved and a closed-loop feedback policy is computed. The constraints are seamlessly incorporated to the control policy selection by including their effect on the transition probabilities of the graph edges. We present a unified framework that is applicable both in the state space (with perfect measurements) and in the information space (with imperfect measurements).

@INPROCEEDINGS{6631304,
author={S. A. {Jacobs} and N. {Stradford} and C. {Rodriguez} and S. {Thomas} and N. M. {Amato}},
booktitle={2013 IEEE International Conference on Robotics and Automation},
title={A scalable distributed RRT for motion planning},
year={2013},
volume={},
number={},
pages={5088-5095},
doi={10.1109/ICRA.2013.6631304}}

Rapidly-exploring Random Tree (RRT), like other sampling-based motion planning methods, has been very successful in solving motion planning problems. Even so, sampling-based planners cannot solve all problems of interest efficiently, so attention is increasingly turning to parallelizing them. However, one challenge in parallelizing RRT is the global computation and communication overhead of nearest neighbor search, a key operation in RRTs. This is a critical issue as it limits the scalability of previous algorithms. We present two parallel algorithms to address this problem. The first algorithm extends existing work by introducing a parameter that adjusts how much local computation is done before a global update. The second algorithm radially subdivides the configuration space into regions, constructs a portion of the tree in each region in parallel, and connects the subtrees,i removing cycles if they exist. By subdividing the space, we increase computation locality enabling a scalable result. We show that our approaches are scalable. We present results demonstrating almost linear scaling to hundreds of processors on a Linux cluster and a Cray XE6 machine.

@inproceedings{denny-icra-2013
, author = "Jory Denny and Kensen Shi and Nancy M. Amato"
, title = "Lazy Toggle PRM: A single-query approach to motion planning"
, booktitle = "IEEE International Conference on Robotics and Automation"
, location = "Karlsruhe, Germany"
, month = "May"
, year - "2013"
, pages = "2407-2414"
, doi = "10.1109/ICRA.2013.6630904"
}

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.

N/A

Motion planning is the problem of computing valid paths through an environment. However, because computing exact solutions is intractable, sampling-based algorithms, such as Probabilistic RoadMaps (PRMs), have gained popularity. PRMs compute an approximate mapping of the planning space by sacrificing completeness in favor of efficiency. However, these algorithms have certain bottlenecks that hinder performance which causes difficulty mapping narrow or crowded regions, and the cost of nearest-neighbor queries, which is the asymptotic bottleneck of these algorithms. Thus, roadmaps may fail to efficiently capture the connectivity of the planning space. In this paper, we present a set of connected component (CC) expansion algorithms, each with different biases (random expand, expand to the nearest CC, expand away from the host CC, and expand along the medial-axis) and expansion node selection policies (random, farthest from CC’s centroid, and difficult nodes), that create a linked-chain of configurations designed to enable efficient connection of CCs. Given an a priori roadmap quality requirement in terms of roadmap connectivity, we show that when our expansion methods augment PRMs, we reach the required roadmap connectivity in less time.

@INPROCEEDINGS{6385875,
author={Yeh, Hsin-Yi and Thomas, Shawna and Eppstein, David and Amato, Nancy M.},
booktitle={2012 IEEE/RSJ International Conference on Intelligent Robots and Systems},
title={UOBPRM: A uniformly distributed obstacle-based PRM},
year={2012},
volume={},
number={},
pages={2655-2662},
doi={10.1109/IROS.2012.6385875}}

This paper presents a new sampling method for motion planning that can generate configurations more uniformly distributed on C-obstacle surfaces than prior approaches. Here, roadmap nodes are generated from the intersections between C-obstacles and a set of uniformly distributed fixed-length segments in C-space. The results show that this new sampling method yields samples that are more uniformly distributed than previous obstacle-based methods such as OBPRM, Gaussian sampling, and Bridge test sampling. UOBPRM is shown to have nodes more uniformly distributed near C-obstacle surfaces and also requires the fewest nodes and edges to solve challenging motion planning problems with varying narrow passages.

TODO: Ghosh, Mukulika (2012). Fast Approximate Convex Decomposition. Master's thesis, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /ETD -TAMU -2012 -08 -11873.

Approximate convex decomposition (ACD) is a technique that partitions an input object into "approximately convex" components. Decomposition into approximately convex pieces is both more efficient to compute than exact convex decomposition and can also generate a more manageable number of components. It can be used as a basis of divide-and-conquer algorithms for applications such as collision detection, skeleton extraction and mesh generation. In this paper, we propose a new method called Fast Approximate Convex Decomposition (FACD) that improves the quality of the decomposition and reduces the cost of computing it for both 2D and 3D models. In particular, we propose a new strategy for evaluating potential cuts that aims to reduce the relative concavity, rather than absolute concavity. As shown in our results, this leads to more natural and smaller decompositions that include components for small but important features such as toes or fingers while not decomposing larger components, such as the torso that may have concavities due to surface texture. Second, instead of decomposing a component into two pieces at each step, as in the original ACD, we propose a new strategy that uses a dynamic programming approach to select a set of n_c non-crossing (independent) cuts that can be simultaneously applied to decompose the component into n_c + 1 components. This reduces the depth of recursion and, together with a more efficient method for computing the concavity measure, leads to significant gains in efficiency. We provide comparative results for 2D and 3D models illustrating the improvements obtained by FACD over ACD and we compare with the segmentation methods given in the Princeton Shape Benchmark.

@inproceedings{denny-icra-2012
, author = "Jory Denny and Nancy M. Amato"
, title = "The Toggle Local Planner for sampling-based motion planning"
, booktitle = "IEEE International Conference on Robotics and Automation (ICRA)"
, location = "Saint Paul, MN, USA"
, month = "May"
, year - "2012"
, pages = "1779-1786"
, doi = "10.1109/ICRA.2012.6225212"
}

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.

@proceedings{denny-iros-2011
, author = "Jory Denny and Nancy Amato"
, title = "Toggle PRM: Simultaneous mapping of C-free and C-obstacle - A study in 2D"
, booktitle = "Proc. IEEE/RSJ Int. Conf. Intel. Rob. Syst. (IROS)"
, location = "San Francisco, CA, USA"
, month = "September"
, year = "2011"
, pages = "2632-2639"
, doi = "10.1109/IROS.2011.6095102"
}

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.

@inproceedings{agha2011firm,
title={FIRM: Feedback controller-based Information-state RoadMap-a framework for motion planning under uncertainty},
author={Agha-Mohammadi, Ali-Akbar and Chakravorty, Suman and Amato, Nancy M},
booktitle={2011 IEEE/RSJ International Conference on Intelligent Robots and Systems},
pages={4284--4291},
year={2011},
organization={IEEE}
}

Direct transformation of sampling-based motion planning methods to the Information-state (belief) space is a challenge. The main bottleneck for roadmap-based techniques in belief space is that the incurred costs on different edges of the graph are not independent of each other. In this paper, we generalize the Probabilistic RoadMap (PRM) framework to obtain a Feedback controller-based Information-state RoadMap (FIRM) that takes into account motion and sensing uncertainty in planning. The FIRM nodes and edges lie in belief space and the crucial feature of FIRM is that the costs associated with different edges of FIRM are independent of each other. Therefore, this construct essentially breaks the “curse of history” in the original Partially Observable Markov Decision Process (POMDP), which models the planning problem. Further, we show how obstacles can be rigorously incorporated into planning on FIRM. All these properties stem from utilizing feedback controllers in the construction of FIRM.

@inproceedings{rodriguez2011toward,
title={Toward realistic pursuit-evasion using a roadmap-based approach},
author={Rodriguez, Samuel and Denny, Jory and Burgos, Juan and Mahadevan, Aditya and Manavi, Kasra and Murray, Luke and Kodochygov, Anton and Zourntos, Takis and Amato, Nancy M},
booktitle={2011 IEEE International Conference on Robotics and Automation},
pages={1738--1745},
year={2011},
organization={IEEE}
}

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.

@article{rodriguez2011utilizing,
title={Utilizing roadmaps in evacuation planning},
author={Rodriguez, Samuel and Amato, Nancy M},
journal={International Journal of Virtual Reality},
volume={10},
number={1},
pages={67--73},
year={2011}
}

In this paper we describe utilization of roadmaps in a general evacuation planning system for complex 3D environments. The problem consists of heterogeneous groups of agents whose behaviors and properties affect usage of the environment when creating evacuation plans. This planning system includes behaviors for those agents evacuating and directors that may be guiding the agents to improve evacuation. One aspect we focus on is modeling different forms of direction and communication between agents.

@inproceedings{rodriguez2011roadmap,
title={Roadmap-based pursuit-evasion in 3d structures},
author={Rodriguez, Samuel and Denny, Jory and Mahadevan, Aditya and Vu, Jeremy and Burgos, Juan and Zourntos, Takis and Amato, Nancy M},
booktitle={24th Intern. Conf. on Computer Animation and Social Agents (CASA)},
year={2011},
organization={Citeseer}
}

We present an approach to the pursuit-evasion problem which is applicable to complex, multi-level environments. Studying each aspect of this problem in 3D structured environments is a distinct extension over many previous approaches. We also utilize our roadmap-based approach to multi-agent behavior when tracking agents of interest. Results are presented in three multi-level environments to highlight the search, pursuit and evasion components of the problem.

@inproceedings{rodriguez2010toward,
title={Toward simulating realistic pursuit-evasion using a roadmap-based approach},
author={Rodriguez, Samuel and Denny, Jory and Zourntos, Takis and Amato, Nancy M},
booktitle={International Conference on Motion in Games},
pages={82--93},
year={2010},
organization={Springer}
}

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. We demonstrate the utility of this approach for a variety of scenarios including pursuit-evasion on terrains, in multi-level buildings, and in crowds.

@article{denny2010region,
title={Region Identification Methods for Efficient and Automated Motion Planning},
author={Denny, Jory and Agrawal, Anshul and Greco, Evan and Tapia, Lydia and Amato, Nancy M},
year={2010},
publisher={Citeseer}
}

Realistic environments for motion planning problems typically consist of multiple areas, e.g., in a house there are rooms, hallways, and doorways. Decomposition of the environment into smaller areas, or regions, has been shown to impact the quality of planning for adaptive methods. Also other complex problems, such as planning for groups of agents with environmental preferences, can be aided with automated region identification. However, despite the advantages of regions, automatic region identification is not always easy, inexpensive, or consistent. In this paper we explore and compare three methods of automatic region identification and quantify the effects of the resulting regions on planning. The three strategies used for region identification are the statistical methods: k-means clustering, PG-means clustering, and Hierarchical clustering. First, we explore the differences in the regions produced by these three methods in a variety of rigid body and articulated linkage environments. Then, we quantitatively compare the usefulness of the region methods in automated motion planning through the application of the regions within the Unsupervised Adaptive Strategy for Motion Planning (UAS). Our results indicate both regions that seem intuitive and non-intuitive to the problems solve motion planning problems with increased efficiency and automation. That is, we found that planning generally benefitted from using regions, and the benefit was not tied to the naturalness of the region.

@article{tang2010reachable,
title={Reachable distance space: Efficient sampling-based planning for spatially constrained systems},
author={Tang, Xinyu and Thomas, Shawna and Coleman, Phillip and Amato, Nancy M},
journal={The international journal of robotics research},
volume={29},
number={7},
pages={916--934},
year={2010},
publisher={SAGE Publications Sage UK: London, England}
}

Motion planning for spatially constrained robots is difficult due to additional constraints placed on the robot, such as closure constraints for closed chains or requirements on end-effector placement for articulated linkages. It is usually computationally too expensive to apply sampling-based planners to these problems since it is difficult to generate valid configurations. We overcome this challenge by redefining the robot’s degrees of freedom and constraints into a new set of parameters, called reachable distance space (RD-space), in which all configurations lie in the set of constraint-satisfying subspaces. This enables us to directly sample the constrained subspaces with complexity linear in the number of the robot’s degrees of freedom. In addition to supporting efficient sampling of configurations, we show that the RD-space formulation naturally supports planning and, in particular, we design a local planner suitable for use by sampling-based planners. We demonstrate the effectiveness and efficiency of our approach for several systems including closed chain planning with multiple loops, restricted end-effector sampling, and on-line planning for drawing/sculpting. We can sample single-loop closed chain systems with 1,000 links in time comparable to open chain sampling, and we can generate samples for 1,000-link multi-loop systems of varying topologies in less than a second.

@inproceedings{rodriguez2010behavior,
title={Behavior-based evacuation planning},
author={Rodriguez, Samuel and Amato, Nancy M},
booktitle={2010 IEEE International Conference on Robotics and Automation},
pages={350--355},
year={2010},
organization={IEEE}
}

In this work, we present a formulation of an evacuation planning problem that is inspired by motion planning and describe an integrated behavioral agent-based and roadmap-based motion planning approach to solve it. Our formulation allows users to test the effect on evacuation of a number of different environmental factors. One of our main focuses is to provide a mechanism to investigate how the interaction between agents influences the resulting evacuation plans. Specifically, we explore how various types of control provided by a set of directing agents effects the overall evacuation planning strategies of the evacuating agents.

@article{tapia-cis-2010-j
, author = "Lydia Tapia and Shawna Thomas and Nancy M. Amato"
, title = "A Motion Planning Approach to Studying Molecular Motions"
, journal = "Communications in Information and Systems"
, volume = "10"
, issue = "1"
, year = "2010"
, pages = "52-68"
, doi = "10.4310/CIS.2010.v10.n1.a4"
, note = "Special Issue in honor of Michael Waterman. Open Access. https://projecteuclid.org/euclid.cis/1268143373"
}

While structurally very different, protein and RNA molecules share an important attribute. The motions they undergo are strongly related to the function they perform. For example, many diseases such as Mad Cow disease or Alzheimer’s disease are associated with protein misfolding and aggregation. Similarly, RNA folding velocity may regulate the plasmid copy number, and RNA folding kinetics can regulate gene expression at the translational level. Knowledge of the stability, folding, kinetics and detailed mechanics of the folding process may help provide insight into how proteins and RNAs fold. In this paper, we present an overview of our work with a computational method we have adapted from robotic motion planning to study molecular motions. We have validated against experimental data and have demonstrated that our method can capture biological results such as stochastic folding pathways, population kinetics of various conformations, and relative folding rates. Thus, our method provides both a detailed view (e.g., individual pathways) and a global view (e.g., population kinetics, relative folding rates, and reaction coordinates) of energy landscapes of both proteins and RNAs. We have validated these techniques by showing that we observe the same relative folding rates as shown in experiments for structurally similar protein molecules that exhibit different folding behaviors. Our analysis has also been able to predict the same relative gene expression rate for wild-type MS2 phage RNA and three of its mutants.

@Inbook{Rodriguez2008,
author="Rodriguez, Samuel
and Thomas, Shawna
and Pearce, Roger
and Amato, Nancy M.",
editor="Akella, Srinivas
and Amato, Nancy M.
and Huang, Wesley H.
and Mishra, Bud",
title="RESAMPL: A Region-Sensitive Adaptive Motion Planner",
bookTitle="Algorithmic Foundation of Robotics VII: Selected Contributions of the Seventh International Workshop on the Algorithmic Foundations of Robotics",
year="2008",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="285--300",
isbn="978-3-540-68405-3",
doi="10.1007/978-3-540-68405-3_18",
url="https://doi.org/10.1007/978-3-540-68405-3_18"
}

Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. While randomized planners, such as probabilistic roadmap methods (PRMs) or rapidly-exploring random trees (RRT), have been highly successful in solving many high degree of freedom problems, there are still many scenarios in which we need better methods, e.g., problems involving narrow passages or which contain multiple regions that are best suited to different planners. In this work, we present RESAMPL, a motion planning strategy that uses local region information to make intelligent decisions about how and where to sample, which samples to connect together, and to find paths through the environment. Briefly, RESAMPL classifies regions based on the entropy of the samples in it, and then uses these classifications to further refine the sampling. Regions are placed in a region graph that encodes relationships between regions, e.g., edges correspond to overlapping regions. The strategy for connecting samples is guided by the region graph, and can be exploited in both multi-query and single-query scenarios. Our experimental results comparing RESAMPL to previous multi-query and single-query methods show that RESAMPL is generally significantly faster and also usually requires fewer samples to solve the problem.

@Inbook{Xie2008,
author="Xie, Dawen
and Morales, Marco
and Pearce, Roger
and Thomas, Shawna
and Lien, Jyh-Ming
and Amato, Nancy M.",
editor="Akella, Srinivas
and Amato, Nancy M.
and Huang, Wesley H.
and Mishra, Bud",
title="Incremental Map Generation (IMG)",
bookTitle="Algorithmic Foundation of Robotics VII: Selected Contributions of the Seventh International Workshop on the Algorithmic Foundations of Robotics",
year="2008",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="53--68",
isbn="978-3-540-68405-3",
doi="10.1007/978-3-540-68405-3_4",
url="https://doi.org/10.1007/978-3-540-68405-3_4"
}

Probabilistic roadmap methods (prms) have been highly successful in solving many high degree of freedom motion planning problems arising in diverse application domains such as traditional robotics, computer-aided design, and computational biology and chemistry. One important practical issue with prms is that they do not provide an automated mechanism to determine how large a roadmap is needed for a given problem. Instead, users typically determine this by trial and error and as a consequence often construct larger roadmaps than are needed. In this paper, we propose a new prm-based framework called Incremental Map Generation (img) to address this problem. Our strategy is to break the map generation into several processes, each of which generates samples and connections, and to continue adding the next increment of samples and connections to the evolving roadmap until it stops improving. In particular, the process continues until a set of evaluation criteria determine that the planning strategy is no longer effective at improving the roadmap. We propose some general evaluation criteria and show how to apply them to construct different types of roadmaps, e.g., roadmaps that coarsely or more finely map the space. In addition, we show how img can be integrated with previously proposed adaptive strategies for selecting sampling methods. We provide results illustrating the power of img.

@inproceedings{10.1145/1236246.1236265,
author = {Lien, Jyh-Ming and Amato, Nancy M.},
title = {Approximate Convex Decomposition of Polyhedra},
year = {2007},
isbn = {9781595936660},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1236246.1236265},
doi = {10.1145/1236246.1236265},
abstract = {Decomposition is a technique commonly used to partition complex models into simpler components. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we explore an alternative partitioning strategy that decomposes a given model into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition (ACD) can more accurately represent the important structural features of the model by providing a mechanism for ignoring less significant features, such as surface texture. We describe a technique for computing ACDs of three-dimensional polyhedral solids and surfaces of arbitrary genus. We provide results illustrating that our approach results in high quality decompositions with very few components and applications showing that comparable or better results can be obtained using ACD decompositions in place of exact convex decompositions (ECD) that are several orders of magnitude larger.},
booktitle = {Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling},
pages = {121–131},
numpages = {11},
keywords = {concavity measurement, convex decomposition},
location = {Beijing, China},
series = {SPM '07}
}

Decomposition is a technique commonly used to partition complex models into simpler components. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we explore an alternative partitioning strategy that decomposes a given model into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition (ACD) can more accurately represent the important structural features of the model by providing a mechanism for ignoring less significant features, such as surface texture. We describe a technique for computing ACDs of three-dimensional polyhedral solids and surfaces of arbitrary genus. We provide results illustrating that our approach results in high quality decompositions with very few components and applications showing that comparable or better results can be obtained using ACD decompositions in place of exact convex decompositions (ECD) that are several orders of magnitude larger.

@INPROCEEDINGS{4209224,
author={Morales, Marco and Pearce, Roger and Amato, Nancy M.},
booktitle={Proceedings 2007 IEEE International Conference on Robotics and Automation},
title={Analysis of the Evolution of C-Space Models built through Incremental Exploration},
year={2007},
volume={},
number={},
pages={1029-1034},
doi={10.1109/ROBOT.2007.363120}}

Many sampling methods for motion planning explore the robot's configuration space (C-space) starting from a set of configuration(s) and incrementally explore surrounding areas to produce a growing model of the space. Although there is a common understanding of the strengths and weaknesses of these techniques, metrics for analyzing the incremental exploration process and for evaluating the performance of incremental samplers have been lacking. We propose the use of local metrics that provide insight into the complexity of the different regions in the model and global metrics that describe the process as a whole. These metrics only require local information and can be efficiently computed. We illustrate the use of our proposed metrics to analyze representative incremental strategies including the rapidly-exploring random trees, expansive space trees, and the original randomized path planner. We show how these metrics model the efficiency of C-space exploration and help to identify different modeling stages. In addition, these metrics are ideal for adapting space exploration to improve performance.

@INPROCEEDINGS{4209320,

author={S. {Thomas} and M. {Morales} and X. {Tang} and N. M. {Amato}},

booktitle={Proceedings 2007 IEEE International Conference on Robotics and Automation},

title={Biasing Samplers to Improve Motion Planning Performance},

year={2007},

volume={},

number={},

pages={1625-1630},

doi={10.1109/ROBOT.2007.363556}}

With the success of randomized sampling-based motion planners such as probabilistic roadmap methods, much work has been done to design new sampling techniques and distributions. To date, there is no sampling technique that outperforms all other techniques for all motion planning problems. Instead, each proposed technique has different strengths and weaknesses. However, little work has been done to combine these techniques to create new distributions. In this paper, we propose to bias one sampling distribution with another such that the resulting distribution out-performs either of its parent distributions. We present a general framework for biasing samplers that is easily extendable to new distributions and can handle an arbitrary number of parent distributions by chaining them together. Our experimental results show that by combining distributions, we can out-perform existing planners. Our results also indicate that not one single distribution combination performs the best in all problems, and we identify which perform better for the specific application domains studied.

@INPROCEEDINGS{4209490, author={X. {Tang} and S. {Thomas} and N. M. {Amato}}, booktitle={Proceedings 2007 IEEE International Conference on Robotics and Automation}, title={Planning with Reachable Distances: Fast Enforcement of Closure Constraints}, year={2007}, volume={}, number={}, pages={2694-2699}, doi={10.1109/ROBOT.2007.363872}}

Motion planning for closed-chain systems is particularly difficult due to additional closure constraints placed on the system. In fact, the probability of randomly selecting a set of joint angles that satisfy the closure constraints is zero. We propose planning with reachable distance (PRD) to overcome this challenge by first precomputing the subspace satisfying the closure constraints, then directly sampling in it. To do so, we represent the chain as a hierarchy of sub-chains. Then we calculate the "closure" sub-space as appropriate reachable distance ranges of sub-chains satisfying the closure constraints. This provides two distinct advantages over traditional approaches: (1) configurations are quickly sampled and converted to joint angles using basic trigonometry functions instead of more expensive inverse kinematics solvers, and (2) configurations are guaranteed to be closed. In this paper, we describe this hierarchical chain representation and give a sampling algorithm with complexity linear in the number of links. We provide the necessary motion planning primitives for most sampling-based motion planners. Our experimental results show our method is fast, making sampling closed configurations comparable to sampling open chain configurations that ignore closure constraints. Our method is general, easy to implement, and also extends to other distance-related constraints besides the ones demonstrated here

@phdthesis{lien2006approximate,
title={Approximate convex decomposition and its applications},
author={Lien, Jyh-Ming},
volume={69},
number={01},
year={2006}
}

Geometric computations are essential in many real-world problems. One important issue in geometric computations is that the geometric models in these problems can be so large that computations on them have infeasible storage or computation time requirements. Decomposition is a technique commonly used to partition complex models into simpler components. Whereas decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this work, we have developed an approximate technique, called Approximate Convex Decomposition (ACD), which decomposes a given polygon or polyhedron into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficently. Indeed, for many applications, an ACD can represent the important structural features of the model more accurately by providing a mechanism for ignoring less significant features, such as wrinkles and surface texture. Our study of a wide range of applications shows that in addition to providing computational efficiency, ACD also provides natural multi-resolution or hierarchical representations. In this dissertation, we provide some examples of ACD's many potential applications, such as particle simulation, mesh generation, motion planning, and skeleton extraction.

@inproceedings{10.1145/1128888.1128919,
author = {Lien, Jyh-Ming and Keyser, John and Amato, Nancy M.},
title = {Simultaneous Shape Decomposition and Skeletonization},
year = {2006},
isbn = {1595933581},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1128888.1128919},
doi = {10.1145/1128888.1128919},
booktitle = {Proceedings of the 2006 ACM Symposium on Solid and Physical Modeling},
pages = {219–228},
numpages = {10},
keywords = {skeletonization, convex decomposition, multi-resolution skeleton},
location = {Cardiff, Wales, United Kingdom},
series = {SPM '06}
}

Shape decomposition and skeletonization share many common properties and applications. However, they are generally treated as independent computations. In this paper, we propose an iterative approach that simultaneously generates a hierarchical shape decomposition and a corresponding set of multi-resolution skeletons. In our method, a skeleton of a model is extracted from the components of its decomposition --- that is, both processes and the qualities of their results are interdependent. In particular, if the quality of the extracted skeleton does not meet some user specified criteria, then the model is decomposed into finer components and a new skeleton is extracted from these components. The process of simultaneous shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory. We provide evidence that the proposed framework is efficient and robust under perturbation and. deformation. We also demonstrate that our results can readily be used in problems including skeletal deformations and virtual reality navigation.

@INPROCEEDINGS{1641883,
author={Morales A, M.A. and Pearce, R. and Amato, N.M.},
booktitle={Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006.},
title={Metrics for analyzing the evolution of C-space models},
year={2006},
volume={},
number={},
pages={1268-1273},
doi={10.1109/ROBOT.2006.1641883}}

There are many sampling-based motion planning methods that model the connectivity of a robot's configuration space (C-space) with a graph whose nodes are valid configurations and whose edges represent valid transitions between nodes. One of the biggest challenges faced by users of these methods is selecting the right planner for their problem. While researchers have tried to compare different planners, most accepted metrics for comparing planners are based on efficiency, e.g., number of collision detection calls or samples needed to solve a particular set of queries, and there is still a lack of useful and efficient quantitative metrics that can be used to measure the suitability of a planner for solving a problem. That is, although there is great interest in determining which planners should be used in which situations, there are still many questions we cannot answer about the relative performance of different planning methods. In this paper we make some progress towards this goal. We propose a metric that can be applied to each new sample considered by a sampling-based planner to characterize how that sample improves, or not, the planner's current C-space model. This characterization requires only local information and can be computed quite efficiently, so that it can be applied to every sample. We show how this characterization can be used to analyze and compare how different planning strategies explore the configuration space. In particular, we show that it can be used to identify three phases that planners go through when building C-space models: quick learning (rapidly building a coarse model), model enhancement (refining the model), and learning decay (oversampling - most samples do not provide additional information). Hence, our work can also provide the basis for determining when a particular planning strategy has 'converged' on the best C-space model that it is capable of building.

@INPROCEEDINGS{1641796,
author={A. V. {Estrada} and {Jyh-Ming Lien} and N. M. {Amato}},
booktitle={Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006.},
title={VIZMO++: a visualization, authoring, and educational tool for motion planning},
year={2006},
volume={},
number={},
pages={727-732},
doi={10.1109/ROBOT.2006.1641796}}

Comprehension of concepts and algorithms involved in the robotics field can be improved through the use of an interactive visualization tool. In this paper we present an interactive tool for visualizing and editing motion planning environments, problem instances, and their solutions. Teachers can take advantage of visualization tools to help their students to better understand motion planning and its complexity as well as the different strategies that have been developed to solve the motion planning problem. While the tool we present allows the animation, manipulation, and evaluation of solution paths found by any motion planner, it is specialized for sampling-based randomized planners such as probabilistic roadmap (PRM) and rapidly-exploring random tree (RRT) methods.

@INPROCEEDINGS{1642072, author={S. {Rodriguez} and {Jyh-Ming Lien} and N. M. {Amato}}, booktitle={Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006.}, title={Planning motion in completely deformable environments}, year={2006}, volume={}, number={}, pages={2466-2471}, doi={10.1109/ROBOT.2006.1642072}}

Though motion planning has been studied extensively for rigid and articulated robots, motion planning for deformable objects is an area that has received far less attention. In this paper we present a framework for planning paths in completely deformable, elastic environments. We apply a deformable model to the robot and obstacles in the environment and present a kinodynamic planning algorithm suited for this type of deformable motion planning. The planning algorithm is based on the rapidly-exploring random tree (RRT) path planning algorithm. To the best of our knowledge, this is the first work that plans paths in totally deformable environments

@INPROCEEDINGS{1641823, author={ {Rodriguez} and {Xinyu Tang} and {Jyh-Ming Lien} and N. M. {Amato}}, booktitle={Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006.}, title={An obstacle-based rapidly-exploring random tree}, year={2006}, volume={}, number={}, pages={895-900}, doi={10.1109/ROBOT.2006.1641823}}

Tree-based path planners have been shown to be well suited to solve various high dimensional motion planning problems. Here we present a variant of the Rapidly-Exploring Random Tree (RRT) path planning algorithm that is able to explore narrow passages or difficult areas more effectively. We show that both workspace obstacle information and C-space information can be used when deciding which direction to grow. The method includes many ways to grow the tree, some taking into account the obstacles in the environment. This planner works best in difficult areas when planning for free flying rigid or articulated robots. Indeed, whereas the standard RRT can face difficulties planning in a narrow passage, the tree based planner presented here works best in these areas

@article{Thomas_2005,
doi = {10.1088/1478-3975/2/4/s09},
url = {https://doi.org/10.1088%2F1478-3975%2F2%2F4%2Fs09},
year = 2005,
month = {nov},
publisher = {{IOP} Publishing},
volume = {2},
number = {4},
pages = {S148--S155},
author = {Shawna Thomas and Guang Song and Nancy M Amato},
title = {Protein folding by motion planning},
journal = {Physical Biology},
abstract = {We investigate a novel approach for studying protein folding that has evolved from robotics motion planning techniques called probabilistic roadmap methods (PRMs). Our focus is to study issues related to the folding process, such as the formation of secondary and tertiary structures, assuming we know the native fold. A feature of our PRM-based framework is that the large sets of folding pathways in the roadmaps it produces, in just a few hours on a desktop PC, provide global information about the protein\'s energy landscape. This is an advantage over other simulation methods such as molecular dynamics or Monte Carlo methods which require more computation and produce only a single trajectory in each run. In our initial studies, we obtained encouraging results for several small proteins. In this paper, we investigate more sophisticated techniques for analyzing the folding pathways in our roadmaps. In addition to more formally revalidating our previous results, we present a case study showing that our technique captures known folding differences between the structurally similar proteins G and L.}
}

We investigate a novel approach for studying protein folding that has evolved from robotics motion planning techniques called probabilistic roadmap methods (PRMs). Our focus is to study issues related to the folding process, such as the formation of secondary and tertiary structures, assuming we know the native fold. A feature of our PRM-based framework is that the large sets of folding pathways in the roadmaps it produces, in just a few hours on a desktop PC, provide global information about the protein\'s energy landscape. This is an advantage over other simulation methods such as molecular dynamics or Monte Carlo methods which require more computation and produce only a single trajectory in each run. In our initial studies, we obtained encouraging results for several small proteins. In this paper, we investigate more sophisticated techniques for analyzing the folding pathways in our roadmaps. In addition to more formally revalidating our previous results, we present a case study showing that our technique captures known folding differences between the structurally similar proteins G and L.

@INPROCEEDINGS{1545045,
author={O. B. {Bayazit} and {Dawen Xie} and N. M. {Amato}},
booktitle={2005 IEEE/RSJ International Conference on Intelligent Robots and Systems}, title={Iterative relaxation of constraints: a framework for improving automated motion planning},
year={2005},
volume={},
number={},
pages={3433-3440},
doi={10.1109/IROS.2005.1545045}}

This paper presents a technique for improving the efficiency of automated motion planners. Motion planning has application in many areas such as robotics, virtual reality systems, computer-aided design, and even computational biology. Although there have been steady advances in motion planning algorithms, especially in randomized approaches such as probabilistic roadmap methods (PRMs) or rapidly-exploring random trees (RRTs), there are still some classes of problems that cannot be solved efficiently using these state-of-the-art motion planners. In this paper, we suggest an iterative strategy addressing this problem where we first simplify the problem by relaxing some feasibility constraints, solve the easier version of the problem, and then use that solution to help us find a solution for the harder problem. We show how this strategy can be applied to rigid bodies and to linkages with high degrees of freedom, including both open and closed chain systems. Experimental results are presented for linkages composed of 9-98 links. Although we use PRMs as the automated planner, the framework is general and can be applied with other motion planning techniques as well.

@INPROCEEDINGS{1570589,
author={M. A. {Morales A.} and L. {Tapia} and R. {Pearce} and S. {Rodriguez} and N. M. {Amato}},
booktitle={Proceedings of the 2005 IEEE International Conference on Robotics and Automation},
title={C-space Subdivision and Integration in Feature-Sensitive Motion Planning},
year={2005},
volume={},
number={},
pages={3114-3119},
doi={10.1109/ROBOT.2005.1570589}}

There are many randomized motion planning techniques, but it is often difficult to determine what planning method to apply to best solve a problem. Planners have their own strengths and weaknesses, and each one is best suited to a specific type of problem. In previous work, we proposed a meta-planner that, through analysis of the problem features, subdivides the instance into regions and determines which planner to apply in each region. The results obtained with our prototype system were very promising even though it utilized simplistic strategies for all components. Even so, we did determine that strategies for problem subdivision and for combination of partial regional solutions have a crucial impact on performance. In this paper, we propose new methods for these steps to improve the performance of the meta-planner. For problem subdivision, we propose two new methods: a method based on ‘ gaps’ and a method based on information theory. For combining partial solutions, we propose two new methods that concentrate on neighboring areas of the regional solutions. We present results that show the performance gain achieved by utilizing these new strategies.

@article{10.1007/978-3-540-30552-1_10,
author ={O. Burçhan {Bayazıt}, Jyh-Ming {Lien}, Nancy M. {Amato}},
title ={Swarming Behavior Using Probabilistic Roadmap Techniques},
journal ={Lecture Notes in Computer Science},
volume ={3342},
year ={2003},
number ={},
pages ={112--125},
doi={10.1007/978-3-540-30552-1_10}
}

While techniques exist for simulating swarming behaviors, these methods usually provide only simplistic navigation and planning capabilities. In this review, we explore the benefits of integrating roadmap-based path planning methods with flocking techniques to achieve different behaviors. We show how group behaviors such as exploring can be facilitated by using dynamic roadmaps (e.g., modifying edge weights) as an implicit means of communication between flock members. Extending ideas from cognitive modeling, we embed behavior rules in individual flock members and in the roadmap. These behavior rules enable the flock members to modify their actions based on their current location and state. We propose new techniques for several distinct group behaviors: homing, exploring (covering and goal searching), passing through narrow areas and shepherding. We present results that show that our methods provide significant improvement over methods that utilize purely local knowledge and moreover, that we achieve performance approaching that which could be obtained by an ideal method that has complete global knowledge. Animations of these behaviors can be viewed on our webpages.

@INPROCEEDINGS{10.1007/10991541_25,
author={Marco {Morales}, Lydia {Tapia}, Roger {Pearce}, Samuel {Rodriguez}, Nancy M. {Amato}},
booktitle={In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR)},
title={A Machine Learning Approach for Feature-Sensitive Motion Planning},
year={2004},
volume={}, number={}, pages={361--376},
doi={10.1007/10991541_25}
}

Although there are many motion planning techniques, there is no method that outperforms all others for all problem instances. Rather, each technique has different strengths and weaknesses which makes it best-suited for certain types of problems. Moreover, since an environment can contain vastly different regions, there may not be a single planner that will perform well in all its regions. Ideally, one would use a suite of planners in concert and would solve the problem by applying the best-suited planner in each region. In this paper, we propose an automated framework for feature-sensitive motion planning. We use a machine learning approach to characterize and partition C-space into regions that are well suited to one of the methods in our library of roadmap-based motion planners. After the best-suited method is applied in each region, the resulting region roadmaps are combined to form a roadmap of the entire planning space. Over a range of problems, we demonstrate that our simple prototype system reliably outperforms any of the planners on their own.

@article{10.1089/10665270360688002,
author ={Nancy M. {Amato}, Ken {Dill}, Guang {Song}},
title ={Using Motion Planning to Map Protein Folding Landscapes and Analyze Folding Kinetics of Known Native Structures},
journal ={Journal of Computational Biology},
volume ={10},year ={2004},number ={3-4},pages ={239-255},
doi={10.1089/10665270360688002}
}

We investigate a novel approach for studying the kinetics of protein folding. Our framework has evolved from robotics motion planning techniques called probabilistic roadmap methods (PRMs) that have been applied in many diverse fields with great success. In our previous work, we presented our PRM-based technique and obtained encouraging results studying protein folding pathways for several small proteins. In this paper, we describe how our motion planning framework can be used to study protein folding kinetics. In particular, we present a refined version of our PRM-based framework and describe how it can be used to produce potential energy landscapes, free energy landscapes, and many folding pathways all from a single roadmap which is computed in a few hours on a desktop PC. Results are presented for 14 proteins. Our ability to produce large sets of unrelated folding pathways may potentially provide crucial insight into some aspects of folding kinetics, such as proteins that exhibit both two-state and three-state kinetics that are not captured by other theoretical techniques.

@inproceedings{ la-acd-04
, author = "J.-M. Lien and N. M. Amato"
, title = "Approximate Convex Decomposition"
, booktitle = "Proc.\ 20th Annual {ACM} Symp.\ Computat.\ Geom.\ (SoCG)"
, year = "2004"
, month = "June"
, note = "Video Abstract."
, pages = "457--458"
}

Not applicable (it is a video abstract)

@inproceedings{ la-acdp-04
, author = "J.-M. Lien and N. M. Amato"
, title = "Approximate Convex Decomposition of Polygons"
, booktitle = "Proc.\ 20th Annual {ACM} Symp.\ Computat.\ Geom.\ (SoCG)"
, year = "2004"
, month="June"
, pages = "17--26"
}

We propose a strategy to decompose a polygon, containing zero or more holes, into ``approximately convex'' pieces. For many applications, the approximately convex components of this decomposition provide similar benefits as convex components, while the resulting decomposition is significantly smaller and can be computed more efficiently. Moreover, our approximate convex decomposition (ACD) provides a mechanism to focus on key structural features and ignore less significant artifacts such as wrinkles and surface texture a user specified tolerance determines allowable concavity. We propose a simple algorithm that computes an ACD of a polygon by iteratively removing (resolving) the most significant non-convex feature (notch). As a by product, it produces an elegant hierarchical representation that provides a series of `increasingly convex' decompositions. Our algorithm computes an ACD of a simple polygon with n vertices and r notches in O(nr) time. In contrast, exact convex decomposition is NP-hard or,if the polygon has no holes, takes O(nr2) time.

@INPROCEEDINGS{1308924,
author={ {Jyh-Ming Lien} and O. B. {Bayazit} and R. T. {Sowell} and S. {Rodriguez} and N. M. {Amato}},
booktitle={IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004}, title={Shepherding behaviors},
year={2004},
volume={4},
number={},
pages={4159-4164 Vol.4},
doi={10.1109/ROBOT.2004.1308924}}

Shepherding behaviors are a type of flocking behavior in which outside agents guide or control members of a flock. Shepherding behaviors can be found in various forms in nature. For example, herding, covering, patrolling and collecting are common types of shepherding behaviors. In this work, we investigate ways to simulate these types of behaviors. A shepherd uses roadmaps to steer the flock and to re-group separated flock members. This paper focuses on improving the shepherd's movements to gain better control of the flock's motion and use this improved control to demonstrate a wider variety of shepherding behaviors.

@inproceedings{10.1145/974614.974648,
author = {Tang, Xinyu and Kirkpatrick, Bonnie and Thomas, Shawna and Song, Guang and Amato, Nancy M.},
title = {Using Motion Planning to Study RNA Folding Kinetics},
year = {2004},
isbn = {1581137559},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/974614.974648},
doi = {10.1145/974614.974648},
abstract = {We propose a novel, motion planning based approach to approximately map the energy landscape of an RNA molecule. Our method is based on the successful probabilistic roadmap motion planners that we have previously successfully applied to protein folding. The key advantage of our method is that it provides a sparse map that captures the main features of the landscape and which can be analyzed to compute folding kinetics. In this paper, we provide evidence that this approach is also well suited to RNA. We compute population kinetics and transition rates on our roadmaps using the master equation for a few moderately sized RNA and show that our results compare favorably with results of other existing methods.},
booktitle = {Proceedings of the Eighth Annual International Conference on Resaerch in Computational Molecular Biology},
pages = {252–261},
numpages = {10},
keywords = {motion planning, RNA, folding kinetics},
location = {San Diego, California, USA},
series = {RECOMB \'04}
}

We propose a novel, motion planning based approach to approximately map the energy landscape of an RNA molecule. Our method is based on the successful probabilistic roadmap motion planners that we have previously successfully applied to protein folding. The key advantage of our method is that it provides a sparse map that captures the main features of the landscape and which can be analyzed to compute folding kinetics. In this paper, we provide evidence that this approach is also well suited to RNA. We compute population kinetics and transition rates on our roadmaps using the master equation for a few moderately sized RNA and show that our results compare favorably with results of other existing methods.

@INPROCEEDINGS{1242288,
author={ {Jyh-Ming Lien} and S. L. {Thomas} and N. M. {Amato}},
booktitle={2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422)}, title={A general framework for sampling on the medial axis of the free space},
year={2003},
volume={3},
number={},
pages={4439-4444 vol.3},
doi={10.1109/ROBOT.2003.1242288}}

We propose a general framework for sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. Generalizing our previous work, this framework provides a template encompassing all possible retraction approaches. It also removes the requirement of exactly computing distance metrics thereby enabling application to more realistic high dimensional problems. In particular, our framework supports methods that retract a given configuration exactly or approximately onto the medial axis. As in our previous work, exact methods provide fast and accurate retraction in low (2 or 3) dimensional space. We also propose new approximate methods that can be applied to high dimensional problems, such as many DOF articulated robots. Theoretical and experimental results show improved performance on problems requiring traversal of narrow passages. We also study tradeoffs between accuracy and efficiency for different levels of approximation, and how the level of approximation effects the quality of the resulting roadmap.

@INPROCEEDINGS{1241956,
author={ {Jinsuck Kim} and R. A. {Pearce} and N. M. {Amato}},
booktitle={2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422)}, title={Extracting optimal paths from roadmaps for motion planning},
year={2003},
volume={2},
number={},
pages={2424-2429 vol.2},
doi={10.1109/ROBOT.2003.1241956}}

We present methods for extracting optimal paths from motion planning roadmaps. Our system enables any combination of optimization criteria, such as collision detection, kinematic/dynamic constraints, or minimum clearance, and relaxed definitions of the goal state, to be used when selecting paths from roadmaps. Our algorithm is an augmented version of Dijkstra's shortest path algorithm which allows edge weights to be defined relative to the current path. We present simulation results maximizing minimum path clearance, minimizing localization effort, and enforcing kinematic/dynamic constraints.

@INPROCEEDINGS{1242286,
author={M. {Morales} and S. {Rodriguez} and N. M. {Amato}},
booktitle={2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422)}, title={Improving the connectivity of PRM roadmaps},
year={2003},
volume={3},
number={},
pages={4427-4432 vol.3},
doi={10.1109/ROBOT.2003.1242286}}

In this paper we investigate how the coverage and connectedness of PRM roadmaps can be improved by adding a connected component (CC) connection step to the general PRM framework. We provide experimental results establishing that significant roadmap improvements can be obtained relatively efficiently by utilizing a suite of CC connection methods, which include variants of existing methods such as RRT and a new ray tracing based method. The coordinated application of these techniques is enabled by methods for selecting and scheduling pairs of nodes in different CCs for connection attempts. In addition to identifying important and/or promising regions of C-space for exploration, these methods also provide a mechanism for controlling the cost of the connection attempts. In our experiments, the time required by the improvement phase was on the same order as the time used to generate the initial roadmap.

@INPROCEEDINGS{1242289,
author={ {Guang Song} and S. {Thomas} and N. M. {Amato}},
booktitle={2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422)}, title={A general framework for PRM motion planning},
year={2003},
volume={3},
number={},
pages={4445-4450 vol.3},
doi={10.1109/ROBOT.2003.1242289}}

An important property of PRM roadmaps is that they provide a good approximation of the connectivity of the free C-space. We present a general framework for building and querying probabilistic roadmaps that includes all previous PRM variants as special cases. In particular, it supports no, complete, or partial node and edge validation and various evaluation schedules for path validation, and it enables path customization for variable, adaptive query requirements. While each of the above features is present in some PRM variant, the general framework proposed here is the only one to include them all. Our framework enables users to choose the best approximation level for their problem. Our experimental evidence shows this can result in significant performance gains.

@article{LIEN2003191,
title = "Neuron PRM: a framework for constructing cortical networks",
journal = "Neurocomputing",
volume = "52-54",
pages = "191 - 197",
year = "2003",
note = "Computational Neuroscience: Trends in Research 2003",
issn = "0925-2312",
doi = "https://doi.org/10.1016/S0925-2312(02)00728-2",
url = "http://www.sciencedirect.com/science/article/pii/S0925231202007282",
author = "Jyh-Ming Lien and Marco Morales and Nancy M. Amato",
keywords = "Cortical networks, PRM, BTS, L-system, Rectangle tree",
abstract = "The brain's extraordinary computational power to represent and interpret complex natural environments is essentially determined by the topology and geometry of the brain's architectures. We present a framework to construct cortical networks which borrows from probabilistic roadmap methods developed for robotic motion planning. We abstract the network as a large-scale directed graph, and use L-systems and statistical data to ‘grow’ neurons that are morphologically indistinguishable from real neurons. We detect connections (synapses) between neurons using geometric proximity tests."
}

The brain's extraordinary computational power to represent and interpret complex natural environments is essentially determined by the topology and geometry of the brain's architectures. We present a framework to construct cortical networks which borrows from probabilistic roadmap methods developed for robotic motion planning. We abstract the network as a large-scale directed graph, and use L-systems and statistical data to ‘grow’ neurons that are morphologically indistinguishable from real neurons. We detect connections (synapses) between neurons using geometric proximity tests.

@INPROCEEDINGS{Song_2003,
author={Guang {Song}, Shawna {Thomas}, Ken A. {Dill}, J. Martin {Scholtz}, Nancy M. {Amato}},
booktitle={In Proc. Pac. Symp. of Biocomputing (PSB)},
title={A Path Planning-based Study of Protein Folding With a Case Study of Hairpin Formation in Protein G and L},
year={2003}, volume={8}, number={}, pages={240-251},
doi={}
}

We investigate a novel approach for studying protein folding that has evolvedfrom robotics motion planning techniques calledprobabilistic roadmapmethods(prms). Our focus is to study issues related to the folding process, such as theformation of secondary and tertiary structure,assumingweknowthenativefold.A feature of ourprm-based framework is that the large sets of folding pathwaysin the roadmaps it produces, in a few hours on a desktop PC, provide globalinformation about the protein’s energy landscape. This is an advantage over othersimulation methods such as molecular dynamics or Monte Carlo methods whichrequire more computation and produce only a single trajectory in each run. Inour initial studies, we obtained encouraging results for several small proteins. Inthis paper, we investigate more sophisticated techniques for analyzing the foldingpathways in our roadmaps. In addition to more formally revalidating our previousresults, we present a case study showing our technique captures known foldingdifferences between the structurally similar proteins G and L.

@INPROCEEDINGS{10.1007/978-3-540-45058-0_7,
author={Osman Burçhan {Bayazit}, Jyh-Ming {Lien}, Nancy M. {Amato}},
booktitle={In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR)},
title={Better Group Behaviors Using Rule-Based Roadmaps},
year={2002}, volume={7}, number={}, pages={95-111},
doi={10.1007/978-3-540-45058-0_7}}

While techniques exist for simulating group behaviors, these methods usually only provide simplistic navigation and planning capabilities. In this work, we explore the benefits of integrating roadmap-based path planning methods with flocking techniques. We show how group behaviors such as exploring can be facilitated by using dynamic roadmaps (e.g., modifying edge weights) as an implicit means of communication between flock members. Extending ideas from cognitive modeling, we embed behavior rules in individual flock members and in the roadmap. These behavior rules enable the flock members to modify their actions based on their current location and state. We propose new techniques for three distinct group behaviors: homing, exploring (covering and goal searching) and passing through narrow areas. Animations of these behaviors can be viewed at http://parasol.tamu.edu/dsmft.

@INPROCEEDINGS{932524,
author={Vallejo, D. and Remmler, I. and Amato, N.M.},
booktitle={Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164)},
title={An adaptive framework for 'single shot' motion planning: a self-tuning system for rigid and articulated robots},
year={2001},
volume={1},
number={},
pages={21-26 vol.1},
doi={10.1109/ROBOT.2001.932524}}

Describes an enhanced version of an adaptive framework for single shot motion planning (Vallejo et al., 2000). This framework is versatile, and particularly suitable for crowded environments. Our iterative strategy analyzes the characteristics of the query and adaptively selects planners whose strengths match the current situation. Contributions in the paper include an automatic method for setting and adaptively tuning planner characterizations, and reducing the reliance on programmer expertise present in the original framework. The adaptive refinement enables the system to evolve parameters specifically suited for particular classes of applications. The system now supports articulated robots, which were not supported previously. Our experimental results in complex 3D CAD environments show that our strategy solves queries that none of the planners could solve on their own.

@INPROCEEDINGS{932672,
author={ {Guang Song} and N. M. {Amato}},
booktitle={Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164)}, title={A motion planning approach to folding: from paper craft to protein folding},
year={2001},
volume={1},
number={},
pages={948-953 vol.1},
doi={10.1109/ROBOT.2001.932672}}

We present a framework for studying folding problems from a motion planning perspective. Modeling foldable objects as tree-like multi-link objects allows one to apply motion planning techniques to folding problems. An important feature of this approach is that it not only allows one to study foldability questions, such as, can an object be folded (or unfolded) into another object, but also provides one with another tool for investigating the dynamic folding process itself. The framework proposed here has application to traditional motion planning areas such as automation and animation, and presents a novel approach for studying protein folding pathways. Preliminary experimental results with traditional paper crafts (e.g., box folding) and small proteins (approximately 60 residues) are quite encouraging.

@inproceedings{song2001customizing,
title={Customizing PRM roadmaps at query time},
author={Song, Guang and Miller, Shawna and Amato, Nancy M},
booktitle={Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164)},
volume={2},
pages={1500--1505},
year={2001},
organization={IEEE}
}

We propose an approach for building and querying probabilistic roadmaps. In the roadmap construction stage, we build coarse roadmaps by performing only an approximate validation of the roadmap nodes and/or edges. In the query stage, the roadmap is validated and refined only in the area of interest for the query, and moreover is customized in accordance with any specified query preferences. This approach, which postpones some of the validation checks (e.g., collision checks) to the query phase, yields more efficient solutions to many problems. An important benefit of our approach is that it gives one the ability to customize the same roadmap in accordance with multiple, variable, query preferences. For example our approach enables one to find a path which maintains a particular clearance, or makes at most some specified number of sharp turns. Our preliminary results on problems drawn from diverse application domains show that this new approach dramatically improves performance, and shows remarkable flexibility when adapting to different query requirements.

@inproceedings{son2001hybrid,
title={Hybrid dynamic simulation of rigid-body contact with Coulomb friction},
author={Son, Wookho and Trinkle, Jeffrey C and Amato, Nancy M},
booktitle={Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164)},
volume={2},
pages={1376--1381},
year={2001},
organization={IEEE}
}

@INPROCEEDINGS{932818, author={S. {Sundaram} and I. {Remmler} and N. M. {Amato}}, booktitle={Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164)}, title={Disassembly sequencing using a motion planning approach}, year={2001}, volume={2}, number={}, pages={1475-1480 vol.2}, doi={10.1109/ROBOT.2001.932818}}

Our motion planning based approach treats the parts in the assembly as robots and operates in the composite configuration space of the parts' individual configuration spaces. Randomized techniques inspired by recent motion planning methods are used to sample configurations in this space. Since typical assemblies consist of many parts, the corresponding composite C-spaces have high dimensionality. Also, since many important configurations for the disassembly sequence will involve closely packed parts, the disassembly problem suffers from the so-called narrow passage problem. We bias the sampling by computing potential movement directions based on the geometric characteristics of configurations known to be reachable from the assembled configuration. We construct a disassembly tree which is rooted at the starting assembled configuration. Our experimental results with several non-trivial puzzle-like assemblies show the potential of this approach.

@INPROCEEDINGS{932892, author={L. K. {Dale} and N. M. {Amato}}, booktitle={Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164)}, title={Probabilistic roadmaps-putting it all together}, year={2001}, volume={2}, number={}, pages={1940-1947 vol.2}, doi={10.1109/ROBOT.2001.932892}}

Given a robot and a workspace, probabilistic roadmap planners (PRMs) build a roadmap of paths sampled from the workspace. A roadmap node is a single collision-free robot configuration, randomly generated. A roadmap edge is a sequence of collision-free robot configurations which interpolate the path from one roadmap node to another. Queries to the roadmap are (start, goal) pairs. If both the start and goal of a pair can be connected to the same connected component of the roadmap, the query is solved. Many promising variants of the PRM have been proposed, each with their own strengths and weaknesses. We propose a meta-planner for using many PRMs in such a way that the strengths are combined and the weaknesses offset. Our meta-planner will perform the combination in the following manner: i) provide a framework in which different motion planners are available and to which new ones are easily added; ii) characterize subregions (possibly overlapping) based on sample characteristics and connection results; iii) assign subregions to one or more planners which are judged promising; and iv) provide stopping criteria for roadmap construction. We present experimental results for four characterization measures. A general technique we call 'filtering' is presented for keeping roadmaps compact.

@article{bayazit2001enhancing,
title={Enhancing randomized motion planners: Exploring with haptic hints},
author={Bayazit, O Burchan and Song, Guang and Amato, Nancy M},
journal={Autonomous Robots},
volume={10},
number={2},
pages={163--174},
year={2001},
publisher={Springer}
}

In this paper, we investigate methods for enabling a human operator and an automatic motion planner to cooperatively solve a motion planning query. Our work is motivated by our experience that automatic motion planners sometimes fail due to the difficulty of discovering ‘critical’ configurations of the robot that are often naturally apparent to a human observer. Our goal is to develop techniques by which the automatic planner can utilize (easily generated) user-input, and determine ‘natural’ ways to inform the user of the progress made by the motion planner. We show that simple randomized techniques inspired by probabilistic roadmap methods are quite useful for transforming approximate, user-generated paths into collision-free paths, and describe an iterative transformation method which enables one to transform a solution for an easier version of the problem into a solution for the original problem. We also illustrate that simple visualization techniques can provide meaningful representations of the planner's progress in a 6-dimensional C-space. We illustrate the utility of our methods on difficult problems involving complex 3D CAD Models.

@INPROCEEDINGS{932823,
author={Guang Song and Miller, S. and Amato, N.M.},
booktitle={Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164)},
title={Customizing PRM roadmaps at query time},
year={2001},
volume={2},
number={},
pages={1500-1505 vol.2},
doi={10.1109/ROBOT.2001.932823}}

We propose an approach for building and querying probabilistic roadmaps. In the roadmap construction stage, we build coarse roadmaps by performing only an approximate validation of the roadmap nodes and/or edges. In the query stage, the roadmap is validated and refined only in the area of interest for the query, and moreover is customized in accordance with any specified query preferences. This approach, which postpones some of the validation checks (e.g., collision checks) to the query phase, yields more efficient solutions to many problems. An important benefit of our approach is that it gives one the ability to customize the same roadmap in accordance with multiple, variable, query preferences. For example our approach enables one to find a path which maintains a particular clearance, or makes at most some specified number of sharp turns. Our preliminary results on problems drawn from diverse application domains show that this new approach dramatically improves performance, and shows remarkable flexibility when adapting to different query requirements.

@phdthesis{dale-phd-2000
, author = "Lucia K. Dale"
, title = "Optimization Techniques for Probabilistic Roadmaps"
, school = "Department of Computer Science and Engineering, Texas A\&M University"
, year = "2000"
, month = "December"
}

Recently, a new class of randomized path planning methods, known as Probabilistic Roadmap Methods (PRMs) have shown great potential for solving complicated high-dimensional problems. PRMs use randomization (usually during preprocessing) to construct a graph (a roadmap) of representative paths in the robot's configuration space. Vertices correspond to collision-free configurations of the robot. An edge exists between two vertices if a path between the two corresponding configurations can be found by a local planning method. PRMs solve many high degree of freedom (dof) motion planning problems. Unfortunately, for some problems running times may still be unacceptably large and solutions sub-optimal. We provide speed and quality optimization strategies applicable in cluttered 3-dimensional workspaces. Speed improvements for roadmap construction are accomplished by parallel processing and faster failure detection techniques. Quality improvements for the roadmap constructed are accomplished by new roadmap building methods which result in roadmaps that better represent the connectivity of the free configuration space. Quality is also improved by building roadmaps iteratively using information gained at each iteration to control and drive following iterations. Since there is no single generally accepted way of judging roadmap quality, several measures are considered.

@phdthesis{vallejo-phd-2000
, author = "Daniel Vallejo Rodriguez"
, title = "An Adaptive Framework for Single Shot Motion Planning"
, school = "Department of Computer Science and Engineering, Texas A\&M University"
, year = "2000"
, month = "December"
}

Given a set of fixed objects (called obstacles) distributed in three-dimensional space, and a moving object (called the robot ), the most basic motion planning problem consists of moving the robot from a given initial or start position to a given final or goal position without colliding with the obstacles. The question of whether such a path exists is called a query. If multiple queries need to be solved, then a popular approach is to construct a graph ( roadmap) of representative feasible paths. Queries are solved by connecting the start and the goal to the roadmap and extracting a path between the two connection points. This approach is very good when many queries must be solved in the same static environment because after the roadmap is constructed, usually during preprocessing, queries can often be answered quickly. However, the cost of constructing the roadmap can be very large if the robot or the environment is very complex. If only one or a very few queries need to be solved, then a more direct approach might lead to faster solutions. In this work we concentrate on this situation which is often referred to as single shot motion planning. We propose an adaptive framework for single shot motion planning, i.e., planning without preprocessing. This framework can be used in any situation, and in particular, is suitable for crowded environments in which the solution path must pass through narrow corridors such as maintainability studies in complex three-dimensional CAD models. Our iterative strategy adaptively selects a planning algorithm whose strengths match the current situation, and then, on-line, switches to a different planner when circumstances change. This requires techniques to evaluate the characteristics of the current query, and a set of planners which are characterized so that we can match the query with the best planner for it. Our experimental results with rigid and articulated robots in complex three-dimensional CAD environments show that our strategy solves queries that none of the planners could solve on their own.

@INPROCEEDINGS{895220,
author={Vallejo, D.R. and Jones, C. and Amato, N.M.},
booktitle={Proceedings. 2000 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2000) (Cat. No.00CH37113)},
title={An adaptive framework for 'single shot' motion planning},
year={2000},
volume={3},
number={},
pages={1722-1727 vol.3},
doi={10.1109/IROS.2000.895220}}

This paper proposes an adaptive framework for single shot motion planning, i.e., planning without preprocessing. This framework can be used in any situation, and in particular, is suitable for crowded environments in which the robot's free C-space has narrow corridors such as maintainability studies in complex 3D CAD models. Our iterative strategy adaptively selects a planner whose strengths match the current situation, and then, online, switches to a different planner when circumstances change. This requires techniques to evaluate the characteristics of the current query, and a set of planners which are characterized so that we can match the query with the best planner for it. Our experimental results in complex 3D CAD environments show that our strategy solves queries that none of the planners could solve on their own.

@MISC{Bayazit00ligandbinding,
author = {O. Burchan Bayazit and Guang Song and Nancy M. Amato},
title = {Ligand Binding with OBPRM and Haptic User Input: Enhancing Automatic Motion Planning with Virtual Touch},
year = {2000}
}

In this paper, we present a framework for studying ligand binding which is based on techniques recently developed in the robotics motion planning community. We are especially interested in locating binding sites on the protein for a ligand molecule. Our work investigates the performance of a fully automated motion planner, as well improvements obtained when supplementary user input is collected using a haptic device. Our results applying an obstacle-based probabilistic roadmap motion planning algorithm (obprm) to some known protein-ligand pairs are very encouraging. In particular, we were able to automatically generate congurations close to, and correctly identify, the true binding site in the three protein-ligand complexes we tested. We nd that user input helps the planner, and a haptic device helps the user to understand the protein structure by enabling them to feel the forces which are hard to visualize.

@ARTICLE{864240,
author={Amato, N.M. and Bayazit, O.B. and Dale, L.K. and Jones, C. and Vallejo, D.},
journal={IEEE Transactions on Robotics and Automation},
title={Choosing good distance metrics and local planners for probabilistic roadmap methods},
year={2000},
volume={16},
number={4},
pages={442-447},
doi={10.1109/70.864240}}

This paper presents a comparative evaluation of different distance metrics and local planners within the context of probabilistic roadmap methods for planning the motion of rigid objects in three-dimensional workspaces. The study concentrates on cluttered three-dimensional workspaces typical of, for example, virtual prototyping applications such as maintainability studies in mechanical CAD designs. Our results include recommendations for selecting appropriate combinations of distance metrics and local planners for such applications. Our study of distance metrics shows that the importance of the translational distance increases relative to the rotational distance as the environment becomes more crowded. We find that each local planner makes some connections that none of the others does-indicating that better connected roadmaps will be constructed using multiple local planners. We propose a new local planning method we call rotate-at-s that often outperforms the common straight-line in C-space method in crowded environments.

@phdthesis{wilmarth-phd-1999
, author = "Steven A. Wilmarth"
, title = "A Probabilistic Method for Rigid-Body Motion Planning Using Sampling from the Medial Axis of the Free Space"
, school = "Department of Mathematics, Texas A\&M University"
, year = "1999"
, month = "December"
}

Motion planning in the presence of obstacles is an important problem in robotics with numerous applications in other areas. While complete motion planning algorithms do exist, they are rarely used in practice since they are computationally infeasible in all but the simplest cases. For this reason, many recent efforts have focused on probabilistic methods, which sacrifice completeness in favor of computational feasibility and applicability. In particular, several algorithms, known as probabilistic roadmap planners, have been shown to perform well in a number of practical situations; however, their performance degrades when paths are required to pass through narrow passages in the free space. In this dissertation we present a method of sampling the configuration space of a rigid body moving in three dimensions in which randomly generated configurations are retracted onto the medial axis of the free space. We develop some theory of the medial axis on the configuration space SE(3) and present algorithms that perform the retraction while avoiding explicit computation of the medial axis. Finally, we give some preliminary experimental results demonstrating the performance of the algorithm.

@INPROCEEDINGS{was-mprb-99,
author={Steven A. Wilmarth and and Nancy M. Amato and Peter F. Stiller},
booktitle={Proceedings of the Annual Symposium on Computational Geometry}
title={Motion Planning for a Rigid Body Using Random Networks on the Medial Axis of the Free Space},
year={1999},
pages={173-180},
doi={10.1145/304893.304967}}

Several motion planning methods using networks of randomly generated nodes in the free space have been shown to perform well in a number of cases, however their performance degrades when paths are required to pass through narrow passages in the,jree space. In [16] we proposed MAPRM, a method of sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space without having to first compute the medial axis; this was shown to increase sampling in narrow passages. In this paper we give details of the MAPRM algorithm for the case of a free-flying rigid body moving in three dimensions, and show that the retraction may be carried out without explicitly computing the C-obstacles or the medial axis. We give theoretical arguments to show that this improves sampling in narrow corridors, and present preliminary experimental results comparing the performance to uniform random sampling from the free space.

@INPROCEEDINGS{772448,
author={Wilmarth, S.A. and Amato, N.M. and Stiller, P.F.},
booktitle={Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C)},
title={MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space},
year={1999},
volume={2},
number={},
pages={1024-1031 vol.2},
doi={10.1109/ROBOT.1999.772448}}

Probabilistic roadmap planning methods have been shown to perform well in a number of practical situations, but their performance degrades when paths are required to pass through narrow passages in the free space. We propose a new method of sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. We give algorithms that perform this retraction while avoiding explicit computation of the medial axis, and we show that sampling and retracting in this manner increases the number of nodes found in small volume corridors in a way that is independent of the volume of the corridor and depends only on the characteristics of the obstacles bounding it. Theoretical and experimental results are given to show that this improves performance on problems requiring traversal of narrow passages.

@INPROCEEDINGS{770055,
author={Amato, N.M. and Dale, L.K.},
booktitle={Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C)},
title={Probabilistic roadmap methods are embarrassingly parallel},
year={1999},
volume={1},
number={},
pages={688-694 vol.1},
doi={10.1109/ROBOT.1999.770055}}

In this paper we report on our experience in parallelizing probabilistic roadmap motion planning methods (PRMs). We show that significant, scalable speed-ups can be obtained with relatively little effort on the part of the developer. Our experience is not limited to PRMs. In particular, we outline general techniques for parallelizing types of computations commonly performed in motion planning algorithms, and identify potential difficulties that might be faced in other efforts to parallelize sequential motion planning methods.

@INPROCEEDINGS{677043,
author={Amato, N.M. and Bayazit, O.B. and Dale, L.K. and Jones, C. and Vallejo, D.},
booktitle={Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No.98CH36146)},
title={Choosing good distance metrics and local planners for probabilistic roadmap methods},
year={1998},
volume={1},
number={},
pages={630-637 vol.1},
doi={10.1109/ROBOT.1998.677043}}

This paper presents a comparative evaluation of different distance metrics and local planners within the content of probabilistic roadmap methods for motion planning. Both C-space and workspace distance metrics and local planners are considered. The study concentrates on cluttered 3D workspaces, typical of mechanical designs. Our results include recommendations for selecting appropriate combinations of distance metrics and local planners for use in motion planning methods, particularly probabilistic roadmap methods. We find that each local planner makes some connections than none of the others do indicating that better connected roadmaps will be constructed using multiple local planners. We propose a new local planning method, we call rotate-at-s, that outperforms the common straight-line in C-space method in crowded environments.

@INPROCEEDINGS{503582,
author={Amato, N.M. and Wu, Y.},
booktitle={Proceedings of IEEE International Conference on Robotics and Automation},
title={A randomized roadmap method for path and manipulation planning},
year={1996},
volume={1},
number={},
pages={113-120 vol.1},
doi={10.1109/ROBOT.1996.503582}}

This paper presents a new randomized roadmap method for motion planning for many DOF robots that can be used to obtain high quality roadmaps even when C-space is crowded. The main novelty in the authors' approach is that roadmap candidate points are chosen on C-obstacle surfaces. As a consequence, the roadmap is likely to contain difficult paths, such as those traversing long, narrow passages in C-space. The approach can be used for both collision-free path planning and for manipulation planning of contact tasks. Experimental results with a planar articulated 6 DOF robot show that, after preprocessing, difficult path planning operations can often be carried out in less than a second.

@phdthesis{amato-phd-1995
, author = "Nancy M. Amato"
, title = "Parallel Algorithms for Convex Hulls and Proximity Problems"
, school = "Department of Computer Science, University of Illinois at Urbana-Champaign"
, year = "1995"
, month = "January"
, note = "https://search.proquest.com/openview/a46d67f1f648ab5badf409ac3ed51894/1?pq-origsite=gscholar&cbl=18750&diss=y"
}

Computational geometry is concerned with the algorithmic aspects of solving geometric problems. The problems are motivated from and have application to such diverse areas as computer graphics, robotics, computer vision, and operations research. Problems arising from these areas of application are good candidates for parallelization since they often have both intense computational needs and stringent response time requirements. Motivated by these concerns, this thesis investigates parallel algorithms for some basic geometric problems. The model of parallel computation used in our studies is the Parallel Random Access Machine (CREW PRAM).