-
Extended Reality System for Robotic Learning from Human Demonstration
Authors:
Isaac Ngui,
Courtney McBeth,
Grace He,
André Corrêa Santos,
Luciano Soares,
Marco Morales,
Nancy M. Amato
Abstract:
Many real-world tasks are intuitive for a human to perform, but difficult to encode algorithmically when utilizing a robot to perform the tasks. In these scenarios, robotic systems can benefit from expert demonstrations to learn how to perform each task. In many settings, it may be difficult or unsafe to use a physical robot to provide these demonstrations, for example, considering cooking tasks s…
▽ More
Many real-world tasks are intuitive for a human to perform, but difficult to encode algorithmically when utilizing a robot to perform the tasks. In these scenarios, robotic systems can benefit from expert demonstrations to learn how to perform each task. In many settings, it may be difficult or unsafe to use a physical robot to provide these demonstrations, for example, considering cooking tasks such as slicing with a knife. Extended reality provides a natural setting for demonstrating robotic trajectories while bypassing safety concerns and providing a broader range of interaction modalities. We propose the Robot Action Demonstration in Extended Reality (RADER) system, a generic extended reality interface for learning from demonstration. We additionally present its application to an existing state-of-the-art learning from demonstration approach and show comparable results between demonstrations given on a physical robot and those given using our extended reality system.
△ Less
Submitted 19 September, 2024;
originally announced September 2024.
-
Encoding Reusable Multi-Robot Planning Strategies as Abstract Hypergraphs
Authors:
Khen Elimelech,
James Motes,
Marco Morales,
Nancy M. Amato,
Moshe Y. Vardi,
Lydia E. Kavraki
Abstract:
Multi-Robot Task Planning (MR-TP) is the search for a discrete-action plan a team of robots should take to complete a task. The complexity of such problems scales exponentially with the number of robots and task complexity, making them challenging for online solution. To accelerate MR-TP over a system's lifetime, this work looks at combining two recent advances: (i) Decomposable State Space Hyperg…
▽ More
Multi-Robot Task Planning (MR-TP) is the search for a discrete-action plan a team of robots should take to complete a task. The complexity of such problems scales exponentially with the number of robots and task complexity, making them challenging for online solution. To accelerate MR-TP over a system's lifetime, this work looks at combining two recent advances: (i) Decomposable State Space Hypergraph (DaSH), a novel hypergraph-based framework to efficiently model and solve MR-TP problems; and \mbox{(ii) learning-by-abstraction,} a technique that enables automatic extraction of generalizable planning strategies from individual planning experiences for later reuse. Specifically, we wish to extend this strategy-learning technique, originally designed for single-robot planning, to benefit multi-robot planning using hypergraph-based MR-TP.
△ Less
Submitted 16 September, 2024;
originally announced September 2024.
-
SPITE: Simple Polyhedral Intersection Techniques for modified Environments
Authors:
Stav Ashur,
Maria Lusardi,
Marta Markowicz,
James Motes,
Marco Morales,
Sariel Har-Peled,
Nancy M. Amato
Abstract:
Motion planning in modified environments is a challenging task, as it
compounds the innate difficulty of the motion planning problem with a changing
environment. This renders some algorithmic methods such as probabilistic
roadmaps less viable, as nodes and edges may become invalid as a result of these
changes.
In this paper, we present a method of transforming any configuration
space g…
▽ More
Motion planning in modified environments is a challenging task, as it
compounds the innate difficulty of the motion planning problem with a changing
environment. This renders some algorithmic methods such as probabilistic
roadmaps less viable, as nodes and edges may become invalid as a result of these
changes.
In this paper, we present a method of transforming any configuration
space graph, such as a roadmap, to a dynamic data structure capable of updating
the validity of its nodes and edges in response to discrete changes in obstacle positions.
We use methods from computational geometry to compute 3D swept volume
approximations of configuration space points and curves to achieve 10-40
percent faster updates and up to 60 percent faster motion planning queries than previous algorithms while requiring a
significantly shorter pre-processing phase, requiring minutes instead of
hours needed by the competing method to achieve somewhat similar update times.
△ Less
Submitted 28 June, 2024;
originally announced July 2024.
-
A Framework for Guided Motion Planning
Authors:
Amnon Attali,
Stav Ashur,
Isaac Burton Love,
Courtney McBeth,
James Motes,
Marco Morales,
Nancy M. Amato
Abstract:
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 bias their sampling using various heuristics related to the known underlying structure of the search space. In this work, we formalize the intuitive notion of guided search by defining the concept of…
▽ More
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 bias their sampling using various heuristics related to the known underlying structure of the search space. In this work, we formalize the intuitive notion of guided search by defining the concept of a guiding space. This new language encapsulates many seemingly distinct prior methods under the same framework, and allows us to reason about guidance, a previously obscured core contribution of different algorithms. We suggest an information theoretic method to evaluate guidance, which experimentally matches intuition when tested on known algorithms in a variety of environments. The language and evaluation of guidance suggests improvements to existing methods, and allows for simple hybrid algorithms that combine guidance from multiple sources.
△ Less
Submitted 6 October, 2024; v1 submitted 3 April, 2024;
originally announced April 2024.
-
Adaptive Robot Coordination: A Subproblem-based Approach for Hybrid Multi-Robot Motion Planning
Authors:
Irving Solis,
James Motes,
Mike Qin,
Marco Morales,
Nancy M. Amato
Abstract:
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…
▽ More
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.
△ Less
Submitted 13 December, 2023;
originally announced December 2023.
-
Scalable Multi-Robot Motion Planning Using Guidance-Informed Hypergraphs
Authors:
Courtney McBeth,
James Motes,
Isaac Ngui,
Marco Morales,
Nancy M. Amato
Abstract:
In this work, we present a multi-robot planning framework that leverages guidance about the problem to efficiently search the planning space. This guidance captures when coordination between robots is necessary, allowing us to decompose the intractably large multi-robot search space while limiting risk of inter-robot conflicts by composing relevant robot groups together while planning. Our framewo…
▽ More
In this work, we present a multi-robot planning framework that leverages guidance about the problem to efficiently search the planning space. This guidance captures when coordination between robots is necessary, allowing us to decompose the intractably large multi-robot search space while limiting risk of inter-robot conflicts by composing relevant robot groups together while planning. Our framework additionally supports planning with kinodynamic constraints through our conflict resolution structure. This structure also improves the scalability of our approach by eliminating unnecessary work during the construction of motion solutions. We also provide an application of this framework to multiple mobile robot motion planning in congested environments using topological guidance. Our previous work has explored using topological guidance, which utilizes information about the robots' environment, in these multi-robot settings where a high degree of coordination is required of the full robot group. In real-world scenarios, this high level of coordination is not always necessary and results in excessive computational overhead. Here, we leverage our novel framework to achieve a significant improvement in scalability and show that our method efficiently finds paths for robot teams up to an order of magnitude larger than existing state-of-the-art methods in congested settings with narrow passages in the environment.
△ Less
Submitted 28 June, 2024; v1 submitted 16 November, 2023;
originally announced November 2023.
-
Hierarchical Annotated Skeleton-Guided Tree-based Motion Planning
Authors:
Diane Uwacu,
Ananya Yammanuru,
Keerthana Nallamotu,
Vasu Chalasani,
Marco Morales,
Nancy M. Amato
Abstract:
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…
▽ More
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.
△ Less
Submitted 19 September, 2023;
originally announced September 2023.
-
Evaluating Guiding Spaces for Motion Planning
Authors:
Amnon Attali,
Stav Ashur,
Isaac Burton Love,
Courtney McBeth,
James Motes,
Diane Uwacu,
Marco Morales,
Nancy M. Amato
Abstract:
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…
▽ More
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 \emph{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.
△ Less
Submitted 16 October, 2022;
originally announced October 2022.
-
Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance
Authors:
Courtney McBeth,
James Motes,
Diane Uwacu,
Marco Morales,
Nancy M. Amato
Abstract:
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 plann…
▽ More
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.
△ Less
Submitted 25 May, 2023; v1 submitted 13 October, 2022;
originally announced October 2022.
-
Hypergraph-based Multi-Robot Task and Motion Planning
Authors:
James Motes,
Tan Chen,
Timothy Bretl,
Marco Morales,
Nancy M. Amato
Abstract:
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 existing methods and successfully plans for problems with up to twenty objects, more than three times as many objects as comparable methods. We achieve this improvement by decomposing the planning space to…
▽ More
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 existing methods and successfully plans for problems with up to twenty 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. 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 multi-manipulator 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.
△ Less
Submitted 19 April, 2023; v1 submitted 9 October, 2022;
originally announced October 2022.
-
Hierarchical Planning with Annotated Skeleton Guidance
Authors:
Diane Uwacu,
Ananya Yammanuru,
Marco Morales,
Nancy M. Amato
Abstract:
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.…
▽ More
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.
△ Less
Submitted 23 June, 2022;
originally announced June 2022.
-
Discrete State-Action Abstraction via the Successor Representation
Authors:
Amnon Attali,
Pedro Cisneros-Velarde,
Marco Morales,
Nancy M. Amato
Abstract:
While the difficulty of reinforcement learning problems is typically related to the complexity of their state spaces, Abstraction proposes that solutions often lie in simpler underlying latent spaces. Prior works have focused on learning either a continuous or dense abstraction, or require a human to provide one. Information-dense representations capture features irrelevant for solving tasks, and…
▽ More
While the difficulty of reinforcement learning problems is typically related to the complexity of their state spaces, Abstraction proposes that solutions often lie in simpler underlying latent spaces. Prior works have focused on learning either a continuous or dense abstraction, or require a human to provide one. Information-dense representations capture features irrelevant for solving tasks, and continuous spaces can struggle to represent discrete objects. In this work we automatically learn a sparse discrete abstraction of the underlying environment. We do so using a simple end-to-end trainable model based on the successor representation and max-entropy regularization. We describe an algorithm to apply our model, named Discrete State-Action Abstraction (DSAA), which computes an action abstraction in the form of temporally extended actions, i.e., Options, to transition between discrete abstract states. Empirically, we demonstrate the effects of different exploration schemes on our resulting abstraction, and show that it is efficient for solving downstream tasks.
△ Less
Submitted 18 October, 2022; v1 submitted 7 June, 2022;
originally announced June 2022.
-
Insights from an Industrial Collaborative Assembly Project: Lessons in Research and Collaboration
Authors:
Tan Chen,
Zhe Huang,
James Motes,
Junyi Geng,
Quang Minh Ta,
Holly Dinkel,
Hameed Abdul-Rashid,
Jessica Myers,
Ye-Ji Mun,
Wei-che Lin,
Yuan-yung Huang,
Sizhe Liu,
Marco Morales,
Nancy M. Amato,
Katherine Driggs-Campbell,
Timothy Bretl
Abstract:
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 projec…
▽ More
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.
△ Less
Submitted 28 May, 2022;
originally announced May 2022.
-
Annotated-skeleton Biased Motion Planning for Faster Relevant Region Discovery
Authors:
Diane Uwacu,
Regina Rex,
Bonnie Wang,
Shawna Thomas,
Nancy M. Amato
Abstract:
Motion planning algorithms often leverage topological information about the environment to improve planner performance. However, these methods often focus only on the environment's connectivity while ignoring other properties such as obstacle clearance, terrain conditions, and resource accessibility. We present a method that augments a skeleton representing the workspace topology with such informa…
▽ More
Motion planning algorithms often leverage topological information about the environment to improve planner performance. However, these methods often focus only on the environment's connectivity while ignoring other properties such as obstacle clearance, terrain conditions, and resource accessibility. We present a method that augments a skeleton representing the workspace topology with such information to guide a sampling-based motion planner to rapidly discover regions most relevant to the problem at hand. Our approach decouples guidance and planning, making it possible for basic planning algorithms to find desired paths earlier in the planning process. We demonstrate the efficacy of our approach in both robotics problems and applications in drug design. Our method is able to produce desirable paths quickly with no change to the underlying planner.
△ Less
Submitted 4 March, 2020;
originally announced March 2020.
-
Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search
Authors:
Irving Solis,
Read Sandström,
James Motes,
Nancy M. Amato
Abstract:
Multi-Agent Motion Planning (MAMP) is the problem of computing feasible paths for a set of agents given individual start and goal states. Given the hardness of MAMP, most of the research related to multi-agent systems has focused on multi-agent pathfinding (MAPF), which simplifies the problem by assuming a shared discrete representation of the space for all agents. The Conflict-Based Search algori…
▽ More
Multi-Agent Motion Planning (MAMP) is the problem of computing feasible paths for a set of agents given individual start and goal states. Given the hardness of MAMP, most of the research related to multi-agent systems has focused on multi-agent pathfinding (MAPF), which simplifies the problem by assuming a shared discrete representation of the space for all agents. The Conflict-Based Search algorithm (CBS) has proven a tractable means of generating optimal solutions in discrete spaces. However, neither CBS nor other discrete MAPF techniques can be directly applied to solve MAMP problems because of the assumption of the shared discrete representation of the agents' state space. In this work, we solve MAMP problems by adapting the techniques discovered in the MAPF scenario by CBS to the more general problem with heterogeneous agents in a continuous space. We demonstrate the scalability teams 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.
△ Less
Submitted 3 March, 2020; v1 submitted 29 September, 2019;
originally announced September 2019.
-
Provably Optimal Parallel Transport Sweeps on Semi-Structured Grids
Authors:
Michael P. Adams,
Marvin L. Adams,
W. Daryl Hawkins,
Timmie Smith,
Lawrence Rauchwerger,
Nancy M. Amato,
Teresa S. Bailey,
Robert D. Falgout,
Adam Kunen,
Peter Brown
Abstract:
We have found provably optimal algorithms for full-domain discrete-ordinate transport sweeps on a class of grids in 2D and 3D Cartesian geometry that are regular at a coarse level but arbitrary within the coarse blocks. We describe these algorithms and show that they always execute the full eight-octant (or four-quadrant if 2D) sweep in the minimum possible number of stages for a given Px x Py x P…
▽ More
We have found provably optimal algorithms for full-domain discrete-ordinate transport sweeps on a class of grids in 2D and 3D Cartesian geometry that are regular at a coarse level but arbitrary within the coarse blocks. We describe these algorithms and show that they always execute the full eight-octant (or four-quadrant if 2D) sweep in the minimum possible number of stages for a given Px x Py x Pz partitioning. Computational results confirm that our optimal scheduling algorithms execute sweeps in the minimum possible stage count. Observed parallel efficiencies agree well with our performance model. Our PDT transport code has achieved approximately 68% parallel efficiency with > 1.5M parallel threads, relative to 8 threads, on a simple weak-scaling problem with only three energy groups, 10 direction per octant, and 4096 cells/core. We demonstrate similar efficiencies on a much more realistic set of nuclear-reactor test problems, with unstructured meshes that resolve fine geometric details. These results demonstrate that discrete-ordinates transport sweeps can be executed with high efficiency using more than 106 parallel processes.
△ Less
Submitted 7 June, 2019;
originally announced June 2019.
-
SLAP: Simultaneous Localization and Planning Under Uncertainty for Physical Mobile Robots via Dynamic Replanning in Belief Space: Extended version
Authors:
Ali-akbar Agha-mohammadi,
Saurav Agarwal,
Sung-Kyun Kim,
Suman Chakravorty,
Nancy M. Amato
Abstract:
Simultaneous localization and Planning (SLAP) is a crucial ability for an autonomous robot operating under uncertainty. In its most general form, SLAP induces a continuous POMDP (partially-observable Markov decision process), which needs to be repeatedly solved online. This paper addresses this problem and proposes a dynamic replanning scheme in belief space. The underlying POMDP, which is continu…
▽ More
Simultaneous localization and Planning (SLAP) is a crucial ability for an autonomous robot operating under uncertainty. In its most general form, SLAP induces a continuous POMDP (partially-observable Markov decision process), which needs to be repeatedly solved online. This paper addresses this problem and proposes a dynamic replanning scheme in belief space. The underlying POMDP, which is continuous in state, action, and observation space, is approximated offline via sampling-based methods, but operates in a replanning loop online to admit local improvements to the coarse offline policy. This construct enables the proposed method to combat changing environments and large localization errors, even when the change alters the homotopy class of the optimal trajectory. It further outperforms the state-of-the-art FIRM (Feedback-based Information RoadMap) method by eliminating unnecessary stabilization steps. Applying belief space planning to physical systems brings with it a plethora of challenges. A key focus of this paper is to implement the proposed planner on a physical robot and show the SLAP solution performance under uncertainty, in changing environments and in the presence of large disturbances, such as a kidnapped robot situation.
△ Less
Submitted 12 May, 2018; v1 submitted 26 October, 2015;
originally announced October 2015.