Publications:
2025 |
Marougkas, I; Ramesh, D; Doerr, J; Granados, E; Sivaramakrishnan, A; Boularias, A; Bekris, K Integrating Model-based Control and RL for Sim2Real Transfer of Tight Insertion Policies Conference IEEE International Conference on Robotics and Automation (ICRA), 2025. @conference{marougkas2025integration, title = {Integrating Model-based Control and RL for Sim2Real Transfer of Tight Insertion Policies}, author = {I Marougkas and D Ramesh and J Doerr and E Granados and A Sivaramakrishnan and A Boularias and K Bekris}, year = {2025}, date = {2025-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, abstract = {Object insertion under tight tolerances (<1mm) is an important but challenging assembly task as even slight errors can result in undesirable contacts. Recent efforts have focused on using Reinforcement Learning (RL) and often depend on careful definition of dense reward functions. This work proposes an effective strategy for such tasks that integrates traditional model-based control with RL to achieve improved accuracy given training of the policy exclusively in simulation and zero- shot transfer to the real system. It employs a potential field- based controller to acquire a model-based policy for inserting a plug into a socket given full observability in simulation. This policy is then integrated with a residual RL one, which is trained in simulation given only a sparse, goal-reaching reward. A curriculum scheme over observation noise and action magnitude is used for training the residual RL policy. Both policy components use as input the SE(3) poses of both the plug and the socket and return the plug's SE(3) pose transform, which is executed by a robotic arm using a controller. The integrated policy is deployed on the real system without further training or fine-tuning, given a visual SE(3) object tracker. The proposed solution and alternatives are evaluated across a variety of objects and conditions in simulation and reality. The proposed approach outperforms recent RL methods in this domain and prior efforts for hybrid policies. Ablations highlight the impact of each component of the approach}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Object insertion under tight tolerances (<1mm) is an important but challenging assembly task as even slight errors can result in undesirable contacts. Recent efforts have focused on using Reinforcement Learning (RL) and often depend on careful definition of dense reward functions. This work proposes an effective strategy for such tasks that integrates traditional model-based control with RL to achieve improved accuracy given training of the policy exclusively in simulation and zero- shot transfer to the real system. It employs a potential field- based controller to acquire a model-based policy for inserting a plug into a socket given full observability in simulation. This policy is then integrated with a residual RL one, which is trained in simulation given only a sparse, goal-reaching reward. A curriculum scheme over observation noise and action magnitude is used for training the residual RL policy. Both policy components use as input the SE(3) poses of both the plug and the socket and return the plug's SE(3) pose transform, which is executed by a robotic arm using a controller. The integrated policy is deployed on the real system without further training or fine-tuning, given a visual SE(3) object tracker. The proposed solution and alternatives are evaluated across a variety of objects and conditions in simulation and reality. The proposed approach outperforms recent RL methods in this domain and prior efforts for hybrid policies. Ablations highlight the impact of each component of the approach |
2024 |
Bekris, K; Doerr, J; Meng, P; Tangirala, S The State of Robot Motion Generation Inproceedings International Symposium of Robotics Research (ISRR), Long Beach, California, 2024. @inproceedings{Bekris:2024aa, title = {The State of Robot Motion Generation}, author = {K Bekris and J Doerr and P Meng and S Tangirala}, url = {https://arxiv.org/abs/2410.12172 https://pracsys.cs.rutgers.edu/papers/the-state-of-robot-motion-generation/}, year = {2024}, date = {2024-12-01}, booktitle = {International Symposium of Robotics Research (ISRR)}, address = {Long Beach, California}, abstract = {This paper first reviews the large spectrum of methods for generating robot motion proposed over the 50 years of robotics research culminating to recent developments. It crosses the boundaries of methodologies, which are typically not surveyed together, from those that operate over explicit models to those that learn implicit ones. The paper concludes with a discussion of the current state-of-the-art and the properties of the varying methodologies highlighting opportunities for integration.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } This paper first reviews the large spectrum of methods for generating robot motion proposed over the 50 years of robotics research culminating to recent developments. It crosses the boundaries of methodologies, which are typically not surveyed together, from those that operate over explicit models to those that learn implicit ones. The paper concludes with a discussion of the current state-of-the-art and the properties of the varying methodologies highlighting opportunities for integration. |
Sivaramakrishnan, A; Tangirala, S; Granados, E; Carver, N; Bekris, K Roadmaps with Gaps Over Controllers: Achieving Efficiency in Planning under Dynamics Inproceedings IEEE/RSJ Intern. Conference on Intelligent Robots and Systems (IROS), Abu Dhabi, United Arab Emirates, 2024. @inproceedings{Sivaramakrishnan:2024aa, title = {Roadmaps with Gaps Over Controllers: Achieving Efficiency in Planning under Dynamics}, author = {A Sivaramakrishnan and S Tangirala and E Granados and N Carver and K Bekris}, url = {https://arxiv.org/abs/2310.03239}, year = {2024}, date = {2024-10-01}, booktitle = {IEEE/RSJ Intern. Conference on Intelligent Robots and Systems (IROS)}, address = {Abu Dhabi, United Arab Emirates}, abstract = {This paper aims to improve the computational efficiency of motion planning for mobile robots with non-trivial dynamics through the use of learned controllers. It adopts a decoupled strategy, where a system-specific controller is first trained offline in an empty environment to deal with the robot's dynamics. For a target environment, the proposed approach constructs offline a data structure, a ``Roadmap with Gaps,'' to approximately learn how to solve planning queries in this environment using the learned controller. The nodes of the roadmap correspond to local regions. Edges correspond to applications of the learned control policy that approximately connect these regions. Gaps arise because the controller does not perfectly connect pairs of individual states along edges. Online, given a query, a tree sampling-based motion planner uses the roadmap so that the tree's expansion is informed towards the goal region. The tree expansion selects local subgoals given a wavefront on the roadmap that guides towards the goal. When the controller cannot reach a subgoal region, the planner resorts to random exploration to maintain probabilistic completeness and asymptotic optimality. The accompanying experimental evaluation shows that the approach significantly improves the computational efficiency of motion planning on various benchmarks, including physics-based vehicular models on uneven and varying friction terrains as well as a quadrotor under air pressure effects.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } This paper aims to improve the computational efficiency of motion planning for mobile robots with non-trivial dynamics through the use of learned controllers. It adopts a decoupled strategy, where a system-specific controller is first trained offline in an empty environment to deal with the robot's dynamics. For a target environment, the proposed approach constructs offline a data structure, a ``Roadmap with Gaps,'' to approximately learn how to solve planning queries in this environment using the learned controller. The nodes of the roadmap correspond to local regions. Edges correspond to applications of the learned control policy that approximately connect these regions. Gaps arise because the controller does not perfectly connect pairs of individual states along edges. Online, given a query, a tree sampling-based motion planner uses the roadmap so that the tree's expansion is informed towards the goal region. The tree expansion selects local subgoals given a wavefront on the roadmap that guides towards the goal. When the controller cannot reach a subgoal region, the planner resorts to random exploration to maintain probabilistic completeness and asymptotic optimality. The accompanying experimental evaluation shows that the approach significantly improves the computational efficiency of motion planning on various benchmarks, including physics-based vehicular models on uneven and varying friction terrains as well as a quadrotor under air pressure effects. |
Vieira, E; Sivaramakrishnan, A; Tangirala, S; Granados, E; Mischaikow, K; Bekris, K MORALS: Analysis of High-Dimensional Robot Controllers Via Topological Tools in a Latent Space Conference IEEE International Conference on Robotics and Automation (ICRA), Yokohama, Japan (Nominated for Best Paper Award in Automation), 2024. @conference{Vieira:2024aa, title = {MORALS: Analysis of High-Dimensional Robot Controllers Via Topological Tools in a Latent Space}, author = {E Vieira and A Sivaramakrishnan and S Tangirala and E Granados and K Mischaikow and K Bekris}, url = {https://arxiv.org/abs/2310.03246}, year = {2024}, date = {2024-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Yokohama, Japan (Nominated for Best Paper Award in Automation)}, abstract = {Estimating the region of attraction (πππ°) for a robotic system's controller is essential for safe application and controller composition. Many existing methods require access to a closed-form expression that limit applicability to data-driven controllers. Methods that operate only over trajectory rollouts tend to be data-hungry. In prior work, we have demonstrated that topological tools based on Morse Graphs offer data-efficient πππ° estimation without needing an analytical model. They struggle, however, with high-dimensional systems as they operate over a discretization of the state space. This paper presents Morse Graph-aided discovery of Regions of Attraction in a learned Latent Space (πΌπΎππ°π»π). The approach combines autoencoding neural networks with Morse Graphs. πΌπΎππ°π»π shows promising predictive capabilities in estimating attractors and their πππ°s for data-driven controllers operating over high-dimensional systems, including a 67-dim humanoid robot and a 96-dim 3-fingered manipulator. It first projects the dynamics of the controlled system into a learned latent space. Then, it constructs a reduced form of Morse Graphs representing the bistability of the underlying dynamics, i.e., detecting when the controller results in a desired versus an undesired behavior. The evaluation on high-dimensional robotic datasets indicates the data efficiency of the approach in πππ° estimation.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Estimating the region of attraction (πππ°) for a robotic system's controller is essential for safe application and controller composition. Many existing methods require access to a closed-form expression that limit applicability to data-driven controllers. Methods that operate only over trajectory rollouts tend to be data-hungry. In prior work, we have demonstrated that topological tools based on Morse Graphs offer data-efficient πππ° estimation without needing an analytical model. They struggle, however, with high-dimensional systems as they operate over a discretization of the state space. This paper presents Morse Graph-aided discovery of Regions of Attraction in a learned Latent Space (πΌπΎππ°π»π). The approach combines autoencoding neural networks with Morse Graphs. πΌπΎππ°π»π shows promising predictive capabilities in estimating attractors and their πππ°s for data-driven controllers operating over high-dimensional systems, including a 67-dim humanoid robot and a 96-dim 3-fingered manipulator. It first projects the dynamics of the controlled system into a learned latent space. Then, it constructs a reduced form of Morse Graphs representing the bistability of the underlying dynamics, i.e., detecting when the controller results in a desired versus an undesired behavior. The evaluation on high-dimensional robotic datasets indicates the data efficiency of the approach in πππ° estimation. |
2023 |
Nakhimovich, D; Miao, Y; Bekris, K Resolution Complete In-Place Object Retrieval Given Known Object Models Inproceedings IEEE International Conference on Robotics and Automatics (ICRA), London, UK, 2023. @inproceedings{Nakhimovich:2023aa, title = {Resolution Complete In-Place Object Retrieval Given Known Object Models}, author = {D Nakhimovich and Y Miao and K Bekris}, url = {https://arxiv.org/abs/2303.14562}, year = {2023}, date = {2023-01-01}, booktitle = {IEEE International Conference on Robotics and Automatics (ICRA)}, address = {London, UK}, abstract = {This work proposes a robot task planning framework for retrieving a target object in a confined workspace among multiple stacked objects that obstruct the target. The robot can use prehensile picking and in-workspace placing actions. The method assumes access to 3D models for the visible objects in the scene. The key contribution is in achieving desirable properties, i.e., to provide (a) safety, by avoiding collisions with sensed obstacles, objects, and occluded regions, and (b) resolution completeness (RC) - or probabilistic completeness (PC) depending on implementation - which indicates a solution will be eventually found (if it exists) as the resolution of algorithmic parameters increases. A heuristic variant of the basic RC algorithm is also proposed to solve the task more efficiently while retaining the desirable properties. Simulation results compare using random picking and placing operations against the basic RC algorithm that reasons about object dependency as well as its heuristic variant. The success rate is higher for the RC approaches given the same amount of time. The heuristic variant is able to solve the problem even more efficiently than the basic approach. The integration of the RC algorithm with perception, where an RGB-D sensor detects the objects as they are being moved, enables real robot demonstrations of safely retrieving target objects from a cluttered shelf.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } This work proposes a robot task planning framework for retrieving a target object in a confined workspace among multiple stacked objects that obstruct the target. The robot can use prehensile picking and in-workspace placing actions. The method assumes access to 3D models for the visible objects in the scene. The key contribution is in achieving desirable properties, i.e., to provide (a) safety, by avoiding collisions with sensed obstacles, objects, and occluded regions, and (b) resolution completeness (RC) - or probabilistic completeness (PC) depending on implementation - which indicates a solution will be eventually found (if it exists) as the resolution of algorithmic parameters increases. A heuristic variant of the basic RC algorithm is also proposed to solve the task more efficiently while retaining the desirable properties. Simulation results compare using random picking and placing operations against the basic RC algorithm that reasons about object dependency as well as its heuristic variant. The success rate is higher for the RC approaches given the same amount of time. The heuristic variant is able to solve the problem even more efficiently than the basic approach. The integration of the RC algorithm with perception, where an RGB-D sensor detects the objects as they are being moved, enables real robot demonstrations of safely retrieving target objects from a cluttered shelf. |
2022 |
McMahon, T; Sivaramakrishnan, A; Kedia, K; Granados, E; Bekris, K Terrain-Aware Learned Controllers for Sampling-Based Kinodynamic Planning Over Physically Simulated Terrains Inproceedings IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2022. @inproceedings{McMahon:2022ab, title = {Terrain-Aware Learned Controllers for Sampling-Based Kinodynamic Planning Over Physically Simulated Terrains}, author = {T McMahon and A Sivaramakrishnan and K Kedia and E Granados and K Bekris}, url = {https://ieeexplore.ieee.org/document/9982136}, year = {2022}, date = {2022-06-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, abstract = {This paper explores learning an effective controller for improving the efficiency of kinodynamic planning for vehicular systems navigating uneven terrains. It describes the pipeline for training the corresponding controller and using it for motion planning purposes. The training process uses a soft actor-critic approach with hindsight experience replay to train a model, which is parameterized by the incline of the robot's local terrain. This trained model is then used during the expansion process of an asymptotically optimal kinodynamic planner to generate controls that allow the robot to reach desired local states. It is also used to define a heuristic cost-to-go function for the planner via a wavefront operation that estimates the cost of reaching the global goal. The cost-to-go function is used both for selecting nodes for expansion as well as for generating local goals for the controller to expand towards. The accompanying experimental section applies the integrated planning solution on models of all-terrain robots in a variety of physically simulated terrains. It shows that the proposed terrain-aware controller and the proposed wavefront function based on the cost-to-go model enable motion planners to find solutions in less time and with lower cost than alternatives. An ablation study emphasizes the benefits of a learned controller that is parameterized by the incline of the robot's local terrain as well as of an incremental training process for the controller.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } This paper explores learning an effective controller for improving the efficiency of kinodynamic planning for vehicular systems navigating uneven terrains. It describes the pipeline for training the corresponding controller and using it for motion planning purposes. The training process uses a soft actor-critic approach with hindsight experience replay to train a model, which is parameterized by the incline of the robot's local terrain. This trained model is then used during the expansion process of an asymptotically optimal kinodynamic planner to generate controls that allow the robot to reach desired local states. It is also used to define a heuristic cost-to-go function for the planner via a wavefront operation that estimates the cost of reaching the global goal. The cost-to-go function is used both for selecting nodes for expansion as well as for generating local goals for the controller to expand towards. The accompanying experimental section applies the integrated planning solution on models of all-terrain robots in a variety of physically simulated terrains. It shows that the proposed terrain-aware controller and the proposed wavefront function based on the cost-to-go model enable motion planners to find solutions in less time and with lower cost than alternatives. An ablation study emphasizes the benefits of a learned controller that is parameterized by the incline of the robot's local terrain as well as of an incremental training process for the controller. |
Vieira, E; Granados, E; Sivaramakrishnan, A; Gameiro, M; Mischaikow, K; Bekris, K Morse Graphs: Topological Tools for Analyzing the Global Dynamics of Robot Controllers Inproceedings Workshop on the Algorithmic Foundations of Robotics (WAFR), 2022. @inproceedings{Vieira:2022aa, title = {Morse Graphs: Topological Tools for Analyzing the Global Dynamics of Robot Controllers}, author = {E Vieira and E Granados and A Sivaramakrishnan and M Gameiro and K Mischaikow and K Bekris}, url = {https://arxiv.org/abs/2202.08383}, year = {2022}, date = {2022-06-01}, booktitle = {Workshop on the Algorithmic Foundations of Robotics (WAFR)}, abstract = {Understanding the global dynamics of a robot controller, such as identifying attractors and their regions of attraction (RoA), is important for safe deployment and synthesizing more effective hybrid controllers. This paper proposes a topological framework to analyze the global dynamics of robot controllers, even data-driven ones, in an effective and explainable way. It builds a combinatorial representation representing the underlying system's state space and non-linear dynamics, which is summarized in a directed acyclic graph, the Morse graph. The approach only probes the dynamics locally by forward propagating short trajectories over a state-space discretization, which needs to be a Lipschitz-continuous function. The framework is evaluated given either numerical or data-driven controllers for classical robotic benchmarks. It is compared against established analytical and recent machine learning alternatives for estimating the RoAs of such controllers. It is shown to outperform them in accuracy and efficiency. It also provides deeper insights as it describes the global dynamics up to the discretization's resolution. This allows to use the Morse graph to identify how to synthesize controllers to form improved hybrid solutions or how to identify the physical limitations of a robotic system.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Understanding the global dynamics of a robot controller, such as identifying attractors and their regions of attraction (RoA), is important for safe deployment and synthesizing more effective hybrid controllers. This paper proposes a topological framework to analyze the global dynamics of robot controllers, even data-driven ones, in an effective and explainable way. It builds a combinatorial representation representing the underlying system's state space and non-linear dynamics, which is summarized in a directed acyclic graph, the Morse graph. The approach only probes the dynamics locally by forward propagating short trajectories over a state-space discretization, which needs to be a Lipschitz-continuous function. The framework is evaluated given either numerical or data-driven controllers for classical robotic benchmarks. It is compared against established analytical and recent machine learning alternatives for estimating the RoAs of such controllers. It is shown to outperform them in accuracy and efficiency. It also provides deeper insights as it describes the global dynamics up to the discretization's resolution. This allows to use the Morse graph to identify how to synthesize controllers to form improved hybrid solutions or how to identify the physical limitations of a robotic system. |
McMahon, T; Sivaramakrishnan, A; Granados, E; Bekris, K A Survey on the Integration of Machine Learning with Sampling-Based Motion Planning Journal Article Forthcoming Foundations and Trends in Robotics, Forthcoming. @article{McMahon:2022aa, title = {A Survey on the Integration of Machine Learning with Sampling-Based Motion Planning}, author = {T McMahon and A Sivaramakrishnan and E Granados and K Bekris}, url = {https://arxiv.org/abs/2211.08368}, year = {2022}, date = {2022-06-01}, journal = {Foundations and Trends in Robotics}, abstract = {Sampling-based methods are widely adopted solutions for robot motion planning. The methods are straightforward to implement, effective in practice for many robotic systems. It is often possible to prove that they have desirable properties, such as probabilistic completeness and asymptotic optimality. Nevertheless, they still face challenges as the complexity of the underlying planning problem increases, especially under tight computation time constraints, which impact the quality of returned solutions or given inaccurate models. This has motivated machine learning to improve the computational efficiency and applicability of Sampling-Based Motion Planners (SBMPs). This survey reviews such integrative efforts and aims to provide a classification of the alternative directions that have been explored in the literature. It first discusses how learning has been used to enhance key components of SBMPs, such as node sampling, collision detection, distance or nearest neighbor computation, local planning, and termination conditions. Then, it highlights planners that use learning to adaptively select between different implementations of such primitives in response to the underlying problem's features. It also covers emerging methods, which build complete machine learning pipelines that reflect the traditional structure of SBMPs. It also discusses how machine learning has been used to provide data-driven models of robots, which can then be used by a SBMP. Finally, it provides a comparative discussion of the advantages and disadvantages of the approaches covered, and insights on possible future directions of research. An online version of this survey can be found at: https://prx-kinodynamic.github.io}, keywords = {}, pubstate = {forthcoming}, tppubtype = {article} } Sampling-based methods are widely adopted solutions for robot motion planning. The methods are straightforward to implement, effective in practice for many robotic systems. It is often possible to prove that they have desirable properties, such as probabilistic completeness and asymptotic optimality. Nevertheless, they still face challenges as the complexity of the underlying planning problem increases, especially under tight computation time constraints, which impact the quality of returned solutions or given inaccurate models. This has motivated machine learning to improve the computational efficiency and applicability of Sampling-Based Motion Planners (SBMPs). This survey reviews such integrative efforts and aims to provide a classification of the alternative directions that have been explored in the literature. It first discusses how learning has been used to enhance key components of SBMPs, such as node sampling, collision detection, distance or nearest neighbor computation, local planning, and termination conditions. Then, it highlights planners that use learning to adaptively select between different implementations of such primitives in response to the underlying problem's features. It also covers emerging methods, which build complete machine learning pipelines that reflect the traditional structure of SBMPs. It also discusses how machine learning has been used to provide data-driven models of robots, which can then be used by a SBMP. Finally, it provides a comparative discussion of the advantages and disadvantages of the approaches covered, and insights on possible future directions of research. An online version of this survey can be found at: https://prx-kinodynamic.github.io |
Granados, E; Boularias, A; Bekris, K; Aanjaneya, M Model Identification and Control of a Mobile Robot with Omnidirectional Wheels Using Differentiable Physics Inproceedings IEEE International Conference on Robotics and Automation (ICRA), 2022. @inproceedings{Granados:2022aa, title = {Model Identification and Control of a Mobile Robot with Omnidirectional Wheels Using Differentiable Physics}, author = {E Granados and A Boularias and K Bekris and M Aanjaneya}, url = {https://orionquest.github.io/papers/MICLCMR/paper.html}, year = {2022}, date = {2022-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, abstract = {We present a new data-driven technique for predicting the motion of a low-cost omnidirectional mobile robot under the influence of motor torques and friction forces. Our method utilizes a novel differentiable physics engine for analytically computing the gradient of the deviation between predicted motion trajectories and real-world trajectories. This allows to automatically learn and fine-tune the unknown friction coefficients on-the-fly, by minimizing a carefully designed loss function using gradient descent. Experiments show that the predicted trajectories are in excellent agreement with their real-world counterparts. Our proposed approach is computationally superior to existing black-box optimization methods, requiring very few real-world samples for accurate trajectory prediction compared to physics-agnostic techniques, such as neural networks. Experiments also demonstrate that the proposed method allows the robot to quickly adapt to changes in the terrain. Our proposed approach combines the data-efficiency of classical analytical models that are derived from first principles, with the flexibility of data-driven methods, which makes it appropriate for low-cost mobile robots.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We present a new data-driven technique for predicting the motion of a low-cost omnidirectional mobile robot under the influence of motor torques and friction forces. Our method utilizes a novel differentiable physics engine for analytically computing the gradient of the deviation between predicted motion trajectories and real-world trajectories. This allows to automatically learn and fine-tune the unknown friction coefficients on-the-fly, by minimizing a carefully designed loss function using gradient descent. Experiments show that the predicted trajectories are in excellent agreement with their real-world counterparts. Our proposed approach is computationally superior to existing black-box optimization methods, requiring very few real-world samples for accurate trajectory prediction compared to physics-agnostic techniques, such as neural networks. Experiments also demonstrate that the proposed method allows the robot to quickly adapt to changes in the terrain. Our proposed approach combines the data-efficiency of classical analytical models that are derived from first principles, with the flexibility of data-driven methods, which makes it appropriate for low-cost mobile robots. |
Wang, R; Miao, Y; Bekris, K Efficient and High-Quality Prehensile Rearrangement in Cluttered and Confined Spaces Inproceedings IEEE International Conference on Robotics and Automation (ICRA), 2022. @inproceedings{Wang:2022ab, title = {Efficient and High-Quality Prehensile Rearrangement in Cluttered and Confined Spaces}, author = {R Wang and Y Miao and K Bekris}, url = {https://arxiv.org/abs/2110.02814}, year = {2022}, date = {2022-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, abstract = {Prehensile object rearrangement in cluttered and confined spaces has broad applications but is also challenging. For instance, rearranging products in a grocery shelf means that the robot cannot directly access all objects and has limited free space. This is harder than tabletop rearrangement where objects are easily accessible with top-down grasps, which simplifies robot-object interactions. This work focuses on problems where such interactions are critical for completing tasks. It proposes a new efficient and complete solver under general constraints for monotone instances, which can be solved by moving each object at most once. The monotone solver reasons about robot-object constraints and uses them to effectively prune the search space. The new monotone solver is integrated with a global planner to solve non-monotone instances with high-quality solutions fast. Furthermore, this work contributes an effective pre-processing tool to significantly speed up online motion planning queries for rearrangement in confined spaces. Experiments further demonstrate that the proposed monotone solver, equipped with the pre-processing tool, results in 57.3% faster computation and 3 times higher success rate than state-of-the-art methods. Similarly, the resulting global planner is computationally more efficient and has a higher success rate, while producing high-quality solutions for non-monotone instances (i.e., only 1.3 additional actions are needed on average).}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Prehensile object rearrangement in cluttered and confined spaces has broad applications but is also challenging. For instance, rearranging products in a grocery shelf means that the robot cannot directly access all objects and has limited free space. This is harder than tabletop rearrangement where objects are easily accessible with top-down grasps, which simplifies robot-object interactions. This work focuses on problems where such interactions are critical for completing tasks. It proposes a new efficient and complete solver under general constraints for monotone instances, which can be solved by moving each object at most once. The monotone solver reasons about robot-object constraints and uses them to effectively prune the search space. The new monotone solver is integrated with a global planner to solve non-monotone instances with high-quality solutions fast. Furthermore, this work contributes an effective pre-processing tool to significantly speed up online motion planning queries for rearrangement in confined spaces. Experiments further demonstrate that the proposed monotone solver, equipped with the pre-processing tool, results in 57.3% faster computation and 3 times higher success rate than state-of-the-art methods. Similarly, the resulting global planner is computationally more efficient and has a higher success rate, while producing high-quality solutions for non-monotone instances (i.e., only 1.3 additional actions are needed on average). |
Morgan, A; Hang, K; Wen, B; Bekris, K; Dollar, A Complex In-Hand Manipulation Via Compliance-Enabled Finger Gaiting and Multi-Modal Planning Journal Article IEEE Robotics and Automation Letters (also at ICRA), 2022. @article{Morgan:2022aa, title = {Complex In-Hand Manipulation Via Compliance-Enabled Finger Gaiting and Multi-Modal Planning}, author = {A Morgan and K Hang and B Wen and K Bekris and A Dollar}, url = {https://arxiv.org/abs/2201.07928}, year = {2022}, date = {2022-05-01}, journal = {IEEE Robotics and Automation Letters (also at ICRA)}, abstract = {Constraining contacts to remain fixed on an object during manipulation limits the potential workspace size, as motion is subject to the hand's kinematic topology. Finger gaiting is one way to alleviate such restraints. It allows contacts to be freely broken and remade so as to operate on different manipulation manifolds. This capability, however, has traditionally been difficult or impossible to practically realize. A finger gaiting system must simultaneously plan for and control forces on the object while maintaining stability during contact switching. This work alleviates the traditional requirement by taking advantage of system compliance, allowing the hand to more easily switch contacts while maintaining a stable grasp. Our method achieves complete SO(3) finger gaiting control of grasped objects against gravity by developing a manipulation planner that operates via orthogonal safe modes of a compliant, underactuated hand absent of tactile sensors or joint encoders. During manipulation, a low-latency 6D pose object tracker provides feedback via vision, allowing the planner to update its plan online so as to adaptively recover from trajectory deviations. The efficacy of this method is showcased by manipulating both convex and non-convex objects on a real robot. Its robustness is evaluated via perturbation rejection and long trajectory goals. To the best of the authors' knowledge, this is the first work that has autonomously achieved full SO(3) control of objects within-hand via finger gaiting and without a support surface, elucidating a valuable step towards realizing true robot in-hand manipulation capabilities.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Constraining contacts to remain fixed on an object during manipulation limits the potential workspace size, as motion is subject to the hand's kinematic topology. Finger gaiting is one way to alleviate such restraints. It allows contacts to be freely broken and remade so as to operate on different manipulation manifolds. This capability, however, has traditionally been difficult or impossible to practically realize. A finger gaiting system must simultaneously plan for and control forces on the object while maintaining stability during contact switching. This work alleviates the traditional requirement by taking advantage of system compliance, allowing the hand to more easily switch contacts while maintaining a stable grasp. Our method achieves complete SO(3) finger gaiting control of grasped objects against gravity by developing a manipulation planner that operates via orthogonal safe modes of a compliant, underactuated hand absent of tactile sensors or joint encoders. During manipulation, a low-latency 6D pose object tracker provides feedback via vision, allowing the planner to update its plan online so as to adaptively recover from trajectory deviations. The efficacy of this method is showcased by manipulating both convex and non-convex objects on a real robot. Its robustness is evaluated via perturbation rejection and long trajectory goals. To the best of the authors' knowledge, this is the first work that has autonomously achieved full SO(3) control of objects within-hand via finger gaiting and without a support surface, elucidating a valuable step towards realizing true robot in-hand manipulation capabilities. |
Miao, Y; Wang, R; Bekris, K Safe, Occlusion-Aware Manipulation for Online Object Reconstruction in Confined Space Inproceedings International Symposium on Robotics Research (ISRR), 2022. @inproceedings{Miao:2022aa, title = {Safe, Occlusion-Aware Manipulation for Online Object Reconstruction in Confined Space}, author = {Y Miao and R Wang and K Bekris}, url = {https://arxiv.org/abs/2205.11719}, year = {2022}, date = {2022-01-01}, booktitle = {International Symposium on Robotics Research (ISRR)}, abstract = {Recent work in robotic manipulation focuses on object retrieval in cluttered space under occlusion. Nevertheless, the majority of efforts lack an analysis of conditions for the completeness of the approaches or the methods apply only when objects can be removed from the workspace. This work formulates the general, occlusion-aware manipulation task, and focuses on safe object reconstruction in a confined space with in-place relocation. A framework that ensures safety with completeness guarantees is proposed. Furthermore, an algorithm, which is an instantiation of this framework for monotone instances, is developed and evaluated empirically by comparing against a random and a greedy baseline on randomly generated experiments in simulation. Even for cluttered scenes with realistic objects, the proposed algorithm significantly outperforms the baselines and maintains a high success rate across experimental conditions.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Recent work in robotic manipulation focuses on object retrieval in cluttered space under occlusion. Nevertheless, the majority of efforts lack an analysis of conditions for the completeness of the approaches or the methods apply only when objects can be removed from the workspace. This work formulates the general, occlusion-aware manipulation task, and focuses on safe object reconstruction in a confined space with in-place relocation. A framework that ensures safety with completeness guarantees is proposed. Furthermore, an algorithm, which is an instantiation of this framework for monotone instances, is developed and evaluated empirically by comparing against a random and a greedy baseline on randomly generated experiments in simulation. Even for cluttered scenes with realistic objects, the proposed algorithm significantly outperforms the baselines and maintains a high success rate across experimental conditions. |
2021 |
Sivaramakrishnan, A; Granados, E; Karten, S; McMahon, T; Bekris, K Improving Kinodynamic Planners for Vehicular Navigation with Learned Goal-Reaching Controllers Inproceedings IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2021. @inproceedings{Sivaramakrishnan:2021aa, title = {Improving Kinodynamic Planners for Vehicular Navigation with Learned Goal-Reaching Controllers}, author = {A Sivaramakrishnan and E Granados and S Karten and T McMahon and K Bekris}, url = {https://arxiv.org/pdf/2110.04238}, year = {2021}, date = {2021-09-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, abstract = {This paper aims to improve the path quality and computational efficiency of sampling-based kinodynamic planners for vehicular navigation. It proposes a learning framework for identifying promising controls during the expansion process of sampling-based planners. Given a dynamics model, a reinforcement learning process is trained offline to return a low-cost control that reaches a local goal state (i.e., a waypoint) in the absence of obstacles. By focusing on the system's dynamics and not knowing the environment, this process is data-efficient and takes place once for a robotic system. In this way, it can be reused in different environments. The planner generates online local goal states for the learned controller in an informed manner to bias towards the goal and consecutively in an exploratory, random manner. For the informed expansion, local goal states are generated either via (a) medial axis information in environments with obstacles, or (b) wavefront information for setups with traversability costs. The learning process and the resulting planning framework are evaluated for a first and second-order differential drive system, as well as a physically simulated Segway robot. The results show that the proposed integration of learning and planning can produce higher quality paths than sampling-based kinodynamic planning with random controls in fewer iterations and computation time.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } This paper aims to improve the path quality and computational efficiency of sampling-based kinodynamic planners for vehicular navigation. It proposes a learning framework for identifying promising controls during the expansion process of sampling-based planners. Given a dynamics model, a reinforcement learning process is trained offline to return a low-cost control that reaches a local goal state (i.e., a waypoint) in the absence of obstacles. By focusing on the system's dynamics and not knowing the environment, this process is data-efficient and takes place once for a robotic system. In this way, it can be reused in different environments. The planner generates online local goal states for the learned controller in an informed manner to bias towards the goal and consecutively in an exploratory, random manner. For the informed expansion, local goal states are generated either via (a) medial axis information in environments with obstacles, or (b) wavefront information for setups with traversability costs. The learning process and the resulting planning framework are evaluated for a first and second-order differential drive system, as well as a physically simulated Segway robot. The results show that the proposed integration of learning and planning can produce higher quality paths than sampling-based kinodynamic planning with random controls in fewer iterations and computation time. |
Shome, R; Solovey, K; Yu, J; Bekris, K; Halperin, D Fast, High-Quality Two-Arm Rearrangement in Synchronous, Monotone Tabletop Setups Journal Article IEEE Transactions on Automation Science and Engineering, 2021. @article{Shome:2021aa, title = {Fast, High-Quality Two-Arm Rearrangement in Synchronous, Monotone Tabletop Setups}, author = {R Shome and K Solovey and J Yu and K Bekris and D Halperin}, url = {https://arxiv.org/abs/1810.12202}, year = {2021}, date = {2021-03-01}, journal = {IEEE Transactions on Automation Science and Engineering}, abstract = {Rearranging objects on a planar surface arises in a variety of robotic applications, such as product packaging. Using two arms can improve efficiency but introduces new computational challenges. This paper studies the problem structure of object rearrangement using two arms in synchronous, monotone tabletop setups and develops an optimal mixed integer model. It then describes an efficient and scalable algorithm, which first minimizes the cost of object transfers and then of moves between objects. This is motivated by the fact that, asymptotically, object transfers dominate the cost of solutions. Moreover, a lazy strategy minimizes the number of motion planning calls and results in significant speedups. Theoretical arguments support the benefits of using two arms and indicate that synchronous execution, in which the two arms perform together either transfers or moves, introduces only a small overhead. Experiments support these claims and show that the scalable method can quickly compute solutions close to the optimal for the considered setup.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Rearranging objects on a planar surface arises in a variety of robotic applications, such as product packaging. Using two arms can improve efficiency but introduces new computational challenges. This paper studies the problem structure of object rearrangement using two arms in synchronous, monotone tabletop setups and develops an optimal mixed integer model. It then describes an efficient and scalable algorithm, which first minimizes the cost of object transfers and then of moves between objects. This is motivated by the fact that, asymptotically, object transfers dominate the cost of solutions. Moreover, a lazy strategy minimizes the number of motion planning calls and results in significant speedups. Theoretical arguments support the benefits of using two arms and indicate that synchronous execution, in which the two arms perform together either transfers or moves, introduces only a small overhead. Experiments support these claims and show that the scalable method can quickly compute solutions close to the optimal for the considered setup. |
2020 |
Mitash, C; Shome, R; Wen, B; Boularias, A; Bekris, K Task-Driven Perception and Manipulation for Constrained Placement of Unknown Objects Journal Article IEEE Robotics and Automation Letters (RA-L) (also appearing at IEEE/RSJ IROS 2020), 2020. @article{Mitash:2020ab, title = {Task-Driven Perception and Manipulation for Constrained Placement of Unknown Objects}, author = {C Mitash and R Shome and B Wen and A Boularias and K Bekris}, url = {https://arxiv.org/abs/2006.15503}, year = {2020}, date = {2020-10-01}, journal = {IEEE Robotics and Automation Letters (RA-L) (also appearing at IEEE/RSJ IROS 2020)}, abstract = {Recent progress in robotic manipulation has dealt with the case of no prior object models in the context of relatively simple tasks, such as bin-picking. Existing methods for more constrained problems, however, such as deliberate placement in a tight region, depend more critically on shape information to achieve safe execution. This work introduces a possibilistic object representation for solving constrained placement tasks without shape priors. A perception method is proposed to track and update the object representation during motion execution, which respects physical and geometric constraints. The method operates directly over sensor data, modeling the seen and unseen parts of the object given observations. It results in a dynamically updated conservative representation, which can be used to plan safe manipulation actions. This task-driven perception process is integrated with manipulation task planning architecture for a dual-arm manipulator to discover efficient solutions for the constrained placement task with minimal sensing. The planning process can make use of handoff operations when necessary for safe placement given the conservative representation. The pipeline is evaluated with data from over 240 real-world experiments involving constrained placement of various unknown objects using a dual-arm manipulator. While straightforward pick-sense-and-place architectures frequently fail to solve these problems, the proposed integrated pipeline achieves more than 95% success and faster execution times.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Recent progress in robotic manipulation has dealt with the case of no prior object models in the context of relatively simple tasks, such as bin-picking. Existing methods for more constrained problems, however, such as deliberate placement in a tight region, depend more critically on shape information to achieve safe execution. This work introduces a possibilistic object representation for solving constrained placement tasks without shape priors. A perception method is proposed to track and update the object representation during motion execution, which respects physical and geometric constraints. The method operates directly over sensor data, modeling the seen and unseen parts of the object given observations. It results in a dynamically updated conservative representation, which can be used to plan safe manipulation actions. This task-driven perception process is integrated with manipulation task planning architecture for a dual-arm manipulator to discover efficient solutions for the constrained placement task with minimal sensing. The planning process can make use of handoff operations when necessary for safe placement given the conservative representation. The pipeline is evaluated with data from over 240 real-world experiments involving constrained placement of various unknown objects using a dual-arm manipulator. While straightforward pick-sense-and-place architectures frequently fail to solve these problems, the proposed integrated pipeline achieves more than 95% success and faster execution times. |
Mitash, C Scalable, Physics-Aware 6d Pose Estimation for Robot Manipulation PhD Thesis Rutgers University, 2020. @phdthesis{Mitash:2020aa, title = {Scalable, Physics-Aware 6d Pose Estimation for Robot Manipulation}, author = {C Mitash}, url = {https://rucore.libraries.rutgers.edu/rutgers-lib/64961/}, year = {2020}, date = {2020-09-01}, school = {Rutgers University}, abstract = {Robot manipulation often depend on some form of pose estimation to represent the state of the world and allow decision making both at the task-level and for motion or grasp planning. Recent progress in deep learning gives hope for a pose estimation solution that could generalize over textured and texture-less objects, objects with or without distinctive shape properties, and under different lighting conditions and clutter scenarios. Nevertheless, it gives rise to a new set of challenges such as the painful task of acquiring large-scale labeled training datasets and of dealing with their stochastic output over unforeseen scenarios that are not captured by the training. This restricts the scalability of such pose estimation solutions in robot manipulation tasks that often deal with a variety of objects and changing environments. The thesis first describes an automatic data generation and learning framework to address the scalability challenge. Learning is bootstrapped by generating labeled data via physics simulation and rendering. Then it self-improves over time by acquiring and labeling real-world images via a search-based pose estimation process. The thesis proposes algorithms to generate and validate object poses online based on the objects' geometry and based on the physical consistency of their scene-level interactions. These algorithms provide robustness even when there exists a domain gap between the synthetic training and the real test scenarios. Finally, the thesis proposes a manipulation planning framework that goes beyond model-based pose estimation. By utilizing a dynamic object representation, this integrated perception and manipulation framework can efficiently solve the task of picking unknown objects and placing them in a constrained space. The algorithms are evaluated over real-world robot manipulation experiments and over large-scale public datasets. The results indicate the usefulness of physical constraints in both the training and the online estimation phase. Moreover, the proposed framework, while only utilizing simulated data can obtain robust estimation in challenging scenarios such as densely-packed bins and clutter where other approaches suffer as a result of large occlusion and ambiguities due to similar looking texture-less surfaces.}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } Robot manipulation often depend on some form of pose estimation to represent the state of the world and allow decision making both at the task-level and for motion or grasp planning. Recent progress in deep learning gives hope for a pose estimation solution that could generalize over textured and texture-less objects, objects with or without distinctive shape properties, and under different lighting conditions and clutter scenarios. Nevertheless, it gives rise to a new set of challenges such as the painful task of acquiring large-scale labeled training datasets and of dealing with their stochastic output over unforeseen scenarios that are not captured by the training. This restricts the scalability of such pose estimation solutions in robot manipulation tasks that often deal with a variety of objects and changing environments. The thesis first describes an automatic data generation and learning framework to address the scalability challenge. Learning is bootstrapped by generating labeled data via physics simulation and rendering. Then it self-improves over time by acquiring and labeling real-world images via a search-based pose estimation process. The thesis proposes algorithms to generate and validate object poses online based on the objects' geometry and based on the physical consistency of their scene-level interactions. These algorithms provide robustness even when there exists a domain gap between the synthetic training and the real test scenarios. Finally, the thesis proposes a manipulation planning framework that goes beyond model-based pose estimation. By utilizing a dynamic object representation, this integrated perception and manipulation framework can efficiently solve the task of picking unknown objects and placing them in a constrained space. The algorithms are evaluated over real-world robot manipulation experiments and over large-scale public datasets. The results indicate the usefulness of physical constraints in both the training and the online estimation phase. Moreover, the proposed framework, while only utilizing simulated data can obtain robust estimation in challenging scenarios such as densely-packed bins and clutter where other approaches suffer as a result of large occlusion and ambiguities due to similar looking texture-less surfaces. |
Kleinbort, M; Solovey, K; Bonalli, R; Granados, E; Bekris, K; Halperin, D Refined Analysis of Asymptotically-Optimal Kinodynamic Planning in the State-Cost Space Conference IEEE International Conference on Robotics and Automation (ICRA), Paris, France, 2020. @conference{Kleinbort:2020aa, title = {Refined Analysis of Asymptotically-Optimal Kinodynamic Planning in the State-Cost Space}, author = {M Kleinbort and K Solovey and R Bonalli and E Granados and K Bekris and D Halperin}, url = {https://arxiv.org/abs/1909.05569}, year = {2020}, date = {2020-06-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Paris, France}, abstract = {We present a novel analysis of AO-RRT: a tree-based planner for motion planning with kinodynamic constraints, originally described by Hauser and Zhou (AO-X, 2016). AO-RRT explores the state-cost space and has been shown to efficiently obtain high-quality solutions in practice without relying on the availability of a computationally-intensive two-point boundary-value solver. Our main contribution is an optimality proof for the single-tree version of the algorithm---a variant that was not analyzed before. Our proof only requires a mild and easily-verifiable set of assumptions on the problem and system: Lipschitz-continuity of the cost function and the dynamics. In particular, we prove that for any system satisfying these assumptions, any trajectory having a piecewise-constant control function and positive clearance from the obstacles can be approximated arbitrarily well by a trajectory found by AO-RRT. We also discuss practical aspects of AO-RRT and present experimental comparisons of variants of the algorithm.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We present a novel analysis of AO-RRT: a tree-based planner for motion planning with kinodynamic constraints, originally described by Hauser and Zhou (AO-X, 2016). AO-RRT explores the state-cost space and has been shown to efficiently obtain high-quality solutions in practice without relying on the availability of a computationally-intensive two-point boundary-value solver. Our main contribution is an optimality proof for the single-tree version of the algorithm---a variant that was not analyzed before. Our proof only requires a mild and easily-verifiable set of assumptions on the problem and system: Lipschitz-continuity of the cost function and the dynamics. In particular, we prove that for any system satisfying these assumptions, any trajectory having a piecewise-constant control function and positive clearance from the obstacles can be approximated arbitrarily well by a trajectory found by AO-RRT. We also discuss practical aspects of AO-RRT and present experimental comparisons of variants of the algorithm. |
Shome, R; Bekris, K Synchronized Multi-Arm Rearrangement Guided by Mode Graphs with Capacity Constraints Conference Workshop on the Algorithmic Foundations of Robotics (WAFR), Oulu, Finland, 2020. @conference{Shome:2020ac, title = {Synchronized Multi-Arm Rearrangement Guided by Mode Graphs with Capacity Constraints}, author = {R Shome and K Bekris}, url = {https://arxiv.org/abs/2005.09127}, year = {2020}, date = {2020-06-01}, booktitle = {Workshop on the Algorithmic Foundations of Robotics (WAFR)}, address = {Oulu, Finland}, abstract = {Solving task planning problems involving multiple objects and multiple robotic arms poses scalability challenges. Such problems involve not only coordinating multiple high-DoF arms, but also searching through possible sequences of actions including object placements, and handoffs. The current work identifies a useful connection between multi-arm rearrangement and recent results in multi-body path planning on graphs with vertex capacity constraints. Solving a synchronized multi-arm rearrangement at a high-level involves reasoning over a modal graph, where nodes correspond to stable object placements and object transfer states by the arms. Edges of this graph correspond to pick, placement and handoff operations. The objects can be viewed as pebbles moving over this graph, which has capacity constraints. For instance, each arm can carry a single object but placement locations can accumulate many objects. Efficient integer linear programming-based solvers have been proposed for the corresponding pebble problem. The current work proposes a heuristic to guide the task planning process for synchronized multi-arm rearrangement. Results indicate good scalability to multiple arms and objects, and an algorithm that can find high-quality solutions fast and exhibiting desirable anytime behavior.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Solving task planning problems involving multiple objects and multiple robotic arms poses scalability challenges. Such problems involve not only coordinating multiple high-DoF arms, but also searching through possible sequences of actions including object placements, and handoffs. The current work identifies a useful connection between multi-arm rearrangement and recent results in multi-body path planning on graphs with vertex capacity constraints. Solving a synchronized multi-arm rearrangement at a high-level involves reasoning over a modal graph, where nodes correspond to stable object placements and object transfer states by the arms. Edges of this graph correspond to pick, placement and handoff operations. The objects can be viewed as pebbles moving over this graph, which has capacity constraints. For instance, each arm can carry a single object but placement locations can accumulate many objects. Efficient integer linear programming-based solvers have been proposed for the corresponding pebble problem. The current work proposes a heuristic to guide the task planning process for synchronized multi-arm rearrangement. Results indicate good scalability to multiple arms and objects, and an algorithm that can find high-quality solutions fast and exhibiting desirable anytime behavior. |
Shome, R; Nakhimovich, D; Bekris, K Pushing the Boundaries of Asymptotic Optimality in Integrated Task and Motion Planning Conference Workshop on the Algorithmic Foundations of Robotics (WAFR), Oulu, Finland, 2020. @conference{Shome:2020ab, title = {Pushing the Boundaries of Asymptotic Optimality in Integrated Task and Motion Planning}, author = {R Shome and D Nakhimovich and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/asymptotic_optimality_task_motion_planning.pdf}, year = {2020}, date = {2020-06-01}, booktitle = {Workshop on the Algorithmic Foundations of Robotics (WAFR)}, address = {Oulu, Finland}, abstract = {Integrated task and motion planning problems describe a multi-modal state space, which is often abstracted as a set of smooth manifolds that are connected via sets of transitions states. One approach to solving such problems is to sample reachable states in each of the manifolds, while simultaneously sampling transition states. Prior work has shown that in order to achieve asymptotically optimal (AO) solutions for such piecewise-smooth task planning problems, it is sufficient to double the connection radius required for AO sampling-based motion planning. This was shown under the assumption that the transition sets themselves are smooth. The current work builds upon this result and demonstrates that it is sufficient to use the same connection radius as for standard AO motion planning. Furthermore, the current work studies the case that the transition sets are non-smooth boundary points of the valid state space, which is frequently the case in practice, such as when a gripper grasps an object. This paper generalizes the notion of clearance that is typically assumed in motion and task planning to include such individual, potentially non-smooth transition states. It is shown that asymptotic optimality is retained under this generalized regime.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Integrated task and motion planning problems describe a multi-modal state space, which is often abstracted as a set of smooth manifolds that are connected via sets of transitions states. One approach to solving such problems is to sample reachable states in each of the manifolds, while simultaneously sampling transition states. Prior work has shown that in order to achieve asymptotically optimal (AO) solutions for such piecewise-smooth task planning problems, it is sufficient to double the connection radius required for AO sampling-based motion planning. This was shown under the assumption that the transition sets themselves are smooth. The current work builds upon this result and demonstrates that it is sufficient to use the same connection radius as for standard AO motion planning. Furthermore, the current work studies the case that the transition sets are non-smooth boundary points of the valid state space, which is frequently the case in practice, such as when a gripper grasps an object. This paper generalizes the notion of clearance that is typically assumed in motion and task planning to include such individual, potentially non-smooth transition states. It is shown that asymptotic optimality is retained under this generalized regime. |
Littlefield, Z Efficient and Asymptotically Optimal Kinodynamic Motion Planning PhD Thesis Rutgers, the State University of New Jersey, 2020. @phdthesis{Littlefield:2020aa, title = {Efficient and Asymptotically Optimal Kinodynamic Motion Planning}, author = {Z Littlefield}, url = {http://www.cs.rutgers.edu/~kb572/pubs/LittlefieldThesisMay2020.pdf}, year = {2020}, date = {2020-05-01}, volume = {PhD}, school = {Rutgers, the State University of New Jersey}, abstract = {This dissertation explores properties of motion planners that build tree data structures in a robottextquoterights state space. Sampling-based tree planners are especially useful for planning for systems with significant dynamics, due to the inherent forward search that is per- formed. This is in contrast to roadmap planners that require a steering local planner in order to make a graph containing multiple possible paths. This dissertation explores a family of motion planners for systems with significant dynamics, where a steering local planner may be computationally expensive or may not exist. These planners focus on providing practical path quality guarantees without prohibitive computational costs. These planners can be considered successors of each other, in that each sub- sequent algorithm addresses some drawback of its predecessor. The first algorithm, Sparse-RRT, addresses a drawback of the RRT method by considering path quality during the tree construction process. Sparse-RRT is proven to be probabilistically complete under mild conditions for the first time here, albeit with a poor convergence rate. The second algorithm presented, SST, provides probabilistic completeness and asymptotic near-optimality properties that are provable, but at the cost of additional algorithmic overhead. SST is shown to improve the convergence rate compared to Sparse-RRT. The third algorithm, DIRT, incorporates learned lessons from these two algorithms and their shortcomings, incorporates task space heuristics to further improve runtime performance, and simplifies the parameters to more user-friendly ones. DIRT is also shown to be probabilistically complete and asymptotically near-optimal. Application areas explored using this family of algorithms include evaluation of distance functions for planning in belief space, manipulation in cluttered environments, and locomotion planning for an icosahedral tensegrity-based rover prototype that requires a physics engine to simulate its motions.}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } This dissertation explores properties of motion planners that build tree data structures in a robottextquoterights state space. Sampling-based tree planners are especially useful for planning for systems with significant dynamics, due to the inherent forward search that is per- formed. This is in contrast to roadmap planners that require a steering local planner in order to make a graph containing multiple possible paths. This dissertation explores a family of motion planners for systems with significant dynamics, where a steering local planner may be computationally expensive or may not exist. These planners focus on providing practical path quality guarantees without prohibitive computational costs. These planners can be considered successors of each other, in that each sub- sequent algorithm addresses some drawback of its predecessor. The first algorithm, Sparse-RRT, addresses a drawback of the RRT method by considering path quality during the tree construction process. Sparse-RRT is proven to be probabilistically complete under mild conditions for the first time here, albeit with a poor convergence rate. The second algorithm presented, SST, provides probabilistic completeness and asymptotic near-optimality properties that are provable, but at the cost of additional algorithmic overhead. SST is shown to improve the convergence rate compared to Sparse-RRT. The third algorithm, DIRT, incorporates learned lessons from these two algorithms and their shortcomings, incorporates task space heuristics to further improve runtime performance, and simplifies the parameters to more user-friendly ones. DIRT is also shown to be probabilistically complete and asymptotically near-optimal. Application areas explored using this family of algorithms include evaluation of distance functions for planning in belief space, manipulation in cluttered environments, and locomotion planning for an icosahedral tensegrity-based rover prototype that requires a physics engine to simulate its motions. |
Wang, R; Mitash, C; Lu, S; Boehm, D; Bekris, K Safe and Effective Picking Paths in Clutter Given Discrete Distributions of Object Poses Conference IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, 2020. @conference{Wang:2020ab, title = {Safe and Effective Picking Paths in Clutter Given Discrete Distributions of Object Poses}, author = {R Wang and C Mitash and S Lu and D Boehm and K Bekris}, url = {https://arxiv.org/abs/2008.04465}, year = {2020}, date = {2020-01-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, address = {Las Vegas, NV}, abstract = {Picking an item in the presence of other objects can be challenging as it involves occlusions and partial views. Given object models, one approach is to perform object pose estimation and use the most likely candidate pose per object to pick the target without collisions. This approach, however, ignores the uncertainty of the perception process both regarding the target's and the surrounding objects' poses. This work proposes first a perception process for 6D pose estimation, which returns a discrete distribution of object poses in a scene. Then, an open-loop planning pipeline is proposed to return safe and effective solutions for moving a robotic arm to pick, which (a) minimizes the probability of collision with the obstructing objects; and (b) maximizes the probability of reaching the target item. The planning framework models the challenge as a stochastic variant of the Minimum Constraint Removal (MCR) problem. The effectiveness of the methodology is verified given both simulated and real data in different scenarios. The experiments demonstrate the importance of considering the uncertainty of the perception process in terms of safe execution. The results also show that the methodology is more effective than conservative MCR approaches, which avoid all possible object poses regardless of the reported uncertainty.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Picking an item in the presence of other objects can be challenging as it involves occlusions and partial views. Given object models, one approach is to perform object pose estimation and use the most likely candidate pose per object to pick the target without collisions. This approach, however, ignores the uncertainty of the perception process both regarding the target's and the surrounding objects' poses. This work proposes first a perception process for 6D pose estimation, which returns a discrete distribution of object poses in a scene. Then, an open-loop planning pipeline is proposed to return safe and effective solutions for moving a robotic arm to pick, which (a) minimizes the probability of collision with the obstructing objects; and (b) maximizes the probability of reaching the target item. The planning framework models the challenge as a stochastic variant of the Minimum Constraint Removal (MCR) problem. The effectiveness of the methodology is verified given both simulated and real data in different scenarios. The experiments demonstrate the importance of considering the uncertainty of the perception process in terms of safe execution. The results also show that the methodology is more effective than conservative MCR approaches, which avoid all possible object poses regardless of the reported uncertainty. |
Shome, R Rutgers University, 2020. @phdthesis{Shome:2020ad, title = {The Problem of Many: Efficient Multi-Arm, Multi-Object Task and and Motion Planning with Optimality Guarantees}, author = {R Shome}, url = {https://doi.org/doi:10.7282/t3-8fcf-xp94}, year = {2020}, date = {2020-01-01}, volume = {PhD}, address = {New Brunswick, NJ}, school = {Rutgers University}, abstract = {This thesis deals with task and motion planning challenges, specifically those involving manipulating multiple objects using multiple robot manipulators. The contributions range from a new foundational understanding of the problem and the conditions for achieving asymptotic optimality to devising application-oriented and efficient planning algorithms as well as experiments on real systems. A key focus corresponds to overcoming scalability challenges in motion planning and dealing with hybrid planning domains, i.e., those that combine continuous and discrete action spaces, to solve manipulation problems that involve multiple types of actions, such as picks, placements and handoffs. The thesis starts with a review of the theoretical foundations regarding the asymptotic optimality properties of sampling-based motion planners. The work outlines core ideas that motivated relevant algorithmic discoveries, as well as the various avenues of research that have followed since. It then presents a new foundational contribution regarding the theoretical conditions for guaranteeing asymptotic optimality in integrated task and motion planning problems. The work addresses the theoretical gap that existed in modeling interactions with the boundaries of the collision-free space, which invariably arise in task planning for manipulation. The second contribution pertains to the design of an efficient, heuristically guided, scalable and asymptotically optimal sampling-based algorithm specifically for solving high-dimensional multi-robot problems. The dRRT* algorithm extends the idea of a tensor roadmap decomposition of the underlying configuration space and uses efficient single-robot heuristics to solve challenging planning problems involving multiple manipulators in a coupled manner. The third area of impact relates to multi-arm task planning problems. Leveraging the efficient multi-arm planning paradigm provided by dRRT*, a multi-modal task planning approach has been developed to deal with pick-handoff-place problems involving up to $7$ robotic arms. A key benefit of integrated task planning enables every arm to preempt the motions that might be necessary for a sequence of actions. Similar task-planning challenges arise when instead of multiple arms, the number of objects increases, which leads to object rearrangement problems. The combinatorial explosion in this case arises from the choices available for assigning objects to arms, and sequencing such actions makes the problem more challenging. In this context, this thesis provides an efficient solution for dual-arm tabletop rearrangement by decomposing the problem into more efficiently solvable subproblems - weighted edge-matching and the traveling salesperson. The above two lines of work have been extended to address more general multi-arm rearrangement problems, dealing with instances involving up to 9 arms and 4 objects. The key insight is a specially constructed mode-graph with capacity constraints, where an efficiently solvable multi-agent path finding solution for the objects can be mapped to a solution to the task planning problem. The consideration of multiple agents in planning problems can extend to human and robotic agents as well. This thesis includes work in human-robot interaction which relate to legibility of manipulator motions, and different types of robotic pointing. It concludes by highlighting applications of the presented planning methods in important domains, such as solving robotic product packing, dual-arm constrained placement and the use of robots in exposure studies.}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } This thesis deals with task and motion planning challenges, specifically those involving manipulating multiple objects using multiple robot manipulators. The contributions range from a new foundational understanding of the problem and the conditions for achieving asymptotic optimality to devising application-oriented and efficient planning algorithms as well as experiments on real systems. A key focus corresponds to overcoming scalability challenges in motion planning and dealing with hybrid planning domains, i.e., those that combine continuous and discrete action spaces, to solve manipulation problems that involve multiple types of actions, such as picks, placements and handoffs. The thesis starts with a review of the theoretical foundations regarding the asymptotic optimality properties of sampling-based motion planners. The work outlines core ideas that motivated relevant algorithmic discoveries, as well as the various avenues of research that have followed since. It then presents a new foundational contribution regarding the theoretical conditions for guaranteeing asymptotic optimality in integrated task and motion planning problems. The work addresses the theoretical gap that existed in modeling interactions with the boundaries of the collision-free space, which invariably arise in task planning for manipulation. The second contribution pertains to the design of an efficient, heuristically guided, scalable and asymptotically optimal sampling-based algorithm specifically for solving high-dimensional multi-robot problems. The dRRT* algorithm extends the idea of a tensor roadmap decomposition of the underlying configuration space and uses efficient single-robot heuristics to solve challenging planning problems involving multiple manipulators in a coupled manner. The third area of impact relates to multi-arm task planning problems. Leveraging the efficient multi-arm planning paradigm provided by dRRT*, a multi-modal task planning approach has been developed to deal with pick-handoff-place problems involving up to $7$ robotic arms. A key benefit of integrated task planning enables every arm to preempt the motions that might be necessary for a sequence of actions. Similar task-planning challenges arise when instead of multiple arms, the number of objects increases, which leads to object rearrangement problems. The combinatorial explosion in this case arises from the choices available for assigning objects to arms, and sequencing such actions makes the problem more challenging. In this context, this thesis provides an efficient solution for dual-arm tabletop rearrangement by decomposing the problem into more efficiently solvable subproblems - weighted edge-matching and the traveling salesperson. The above two lines of work have been extended to address more general multi-arm rearrangement problems, dealing with instances involving up to 9 arms and 4 objects. The key insight is a specially constructed mode-graph with capacity constraints, where an efficiently solvable multi-agent path finding solution for the objects can be mapped to a solution to the task planning problem. The consideration of multiple agents in planning problems can extend to human and robotic agents as well. This thesis includes work in human-robot interaction which relate to legibility of manipulator motions, and different types of robotic pointing. It concludes by highlighting applications of the presented planning methods in important domains, such as solving robotic product packing, dual-arm constrained placement and the use of robots in exposure studies. |
Shome, R; Solovey, K; Dobson, A; Halperin, D; Bekris, K DRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning Journal Article Autonomous Robots, 2020. @article{Shome:2020aa, title = {DRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning}, author = {R Shome and K Solovey and A Dobson and D Halperin and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/drrt_star_auro.pdf}, year = {2020}, date = {2020-01-01}, journal = {Autonomous Robots}, abstract = {Many exciting robotic applications require multiple robots with many degrees of freedom, such as manipulators, to coordinate their motion in a shared workspace. Discovering high-quality paths in such scenarios can be achieved, in principle, by exploring the composite space of all robots. Sampling-based planners do so by building a roadmap or a tree data structure in the corresponding configuration space and can achieve asymptotic optimality. The hardness of motion planning, however, renders the explicit construction of such structures in the composite space of multiple robots impractical. This work proposes a scalable solution for such coupled multi-robot problems, which provides desirable path-quality guarantees and is also computationally efficient. In particular, the proposed dRRT* is an informed, asymptotically-optimal extension of a prior sampling-based multi-robot motion planner, dRRT. The prior approach introduced the idea of building roadmaps for each robot and implicitly searching the tensor product of these structures in the composite space. This work identifies the conditions for convergence to optimal paths in multi-robot problems, which the prior method was not achieving.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Many exciting robotic applications require multiple robots with many degrees of freedom, such as manipulators, to coordinate their motion in a shared workspace. Discovering high-quality paths in such scenarios can be achieved, in principle, by exploring the composite space of all robots. Sampling-based planners do so by building a roadmap or a tree data structure in the corresponding configuration space and can achieve asymptotic optimality. The hardness of motion planning, however, renders the explicit construction of such structures in the composite space of multiple robots impractical. This work proposes a scalable solution for such coupled multi-robot problems, which provides desirable path-quality guarantees and is also computationally efficient. In particular, the proposed dRRT* is an informed, asymptotically-optimal extension of a prior sampling-based multi-robot motion planner, dRRT. The prior approach introduced the idea of building roadmaps for each robot and implicitly searching the tensor product of these structures in the composite space. This work identifies the conditions for convergence to optimal paths in multi-robot problems, which the prior method was not achieving. |
Bekris, K; Shome, R Asymptotically Optimal Sampling-Based Planners Book Chapter Encyclopedia of Robotics, 2020. @inbook{Bekris:2020aa, title = {Asymptotically Optimal Sampling-Based Planners}, author = {K Bekris and R Shome}, url = {https://arxiv.org/abs/1911.04044}, year = {2020}, date = {2020-01-01}, booktitle = {Encyclopedia of Robotics}, abstract = {An asymptotically optimal sampling-based planner employs sampling to solve robot motion planning problems and returns paths with a cost that converges to the optimal solution cost, as the number of samples approaches infinity. This comprehensive article covers the theoretical characteristics of asymptotic optimality of motion planning algorithms, and traces its origins, analysis models, practical performance, extensions, and applications.}, keywords = {}, pubstate = {published}, tppubtype = {inbook} } An asymptotically optimal sampling-based planner employs sampling to solve robot motion planning problems and returns paths with a cost that converges to the optimal solution cost, as the number of samples approaches infinity. This comprehensive article covers the theoretical characteristics of asymptotic optimality of motion planning algorithms, and traces its origins, analysis models, practical performance, extensions, and applications. |
Goldberg, K; Abbeel, P; Bekris, K; Miller, L Algorithmic Foundations of Robotics XII Book Springer, 2020, ISBN: 978-3-030-43089-4. @book{Goldberg:2020aa, title = {Algorithmic Foundations of Robotics XII}, author = {K Goldberg and P Abbeel and K Bekris and L Miller}, url = {https://link.springer.com/book/10.1007/978-3-030-43089-4}, doi = {10.1007/978-3-030-43089-4}, isbn = {978-3-030-43089-4}, year = {2020}, date = {2020-01-01}, volume = {13}, publisher = {Springer}, organization = {Springer}, series = {Springer Proceedings in Advanced Robotics}, abstract = {Robotics is reaching an elevated level of maturity and continues to benefit from the advances and innovations in its enabling technologies. These all are contributing to an unprecedented effort to bringing robots to the human environment in hospitals and homes, factories, and schools, in the field for robots fighting fires, making goods and products, picking fruits and watering the farmland, saving time and lives. Robots today hold the promise for making a considerable impact in a wide range of real-world applications from industrial manufacturing to health care, transportation, and exploration of the deep space and sea. Tomorrow, robots will become pervasive and touch upon many aspects of modern life. The Springer Tracts in Advanced Robotics (STAR) was launched in 2002 with the goal of bringing to the research community the latest advances in the robotics field based on their significance and quality. During the latest fifteen years, the STAR series has featured publication of both monographs and edited collections. Among the latter, the proceedings of thematic symposia devoted to excellence in robotics research, such as ISRR, ISER, FSR, and WAFR, have been regularly included in STAR. The expansion of our field as well as the emergence of new research areas has motivated us to enlarge the pool of proceedings in the STAR series in the past few years. This has ultimately led to launching a sister series in parallel to STAR. The Springer Proceedings in Advanced Robotics (SPAR) is dedicated to the timely dissemination of the latest research results presented in selected symposia and workshops. This volume of the SPAR series brings the proceedings of the twelfth edition of the Workshop Algorithmic Foundations of Robotics (WAFR). WAFR went back to its roots and was held from December 18 to 20, 2016, in San Francisco, California, the same city in which the very first WAFR was held in 1994. The volume edited by Ken Goldberg, Pieter Abbeel, Kostas Bekris, and Lauren Miller is a collection of 58 contributions spanning a wide range of applications in manufacturing, medicine, distributed robotics, human--robot interaction, intelligent prosthetics, computer animation, computational biology, and many other areas. Validation of algorithms, design concepts, or techniques is the common thread running through this focused collection. Rich by topics and authoritative contributors, WAFR culminates with this unique reference on the current developments and new directions in the field of algorithmic foundations. A very fine addition to the series! More information about the conference, including videos of the presentations can be found under the conference's website: http://wafr2016.berkeley.edu}, keywords = {}, pubstate = {published}, tppubtype = {book} } Robotics is reaching an elevated level of maturity and continues to benefit from the advances and innovations in its enabling technologies. These all are contributing to an unprecedented effort to bringing robots to the human environment in hospitals and homes, factories, and schools, in the field for robots fighting fires, making goods and products, picking fruits and watering the farmland, saving time and lives. Robots today hold the promise for making a considerable impact in a wide range of real-world applications from industrial manufacturing to health care, transportation, and exploration of the deep space and sea. Tomorrow, robots will become pervasive and touch upon many aspects of modern life. The Springer Tracts in Advanced Robotics (STAR) was launched in 2002 with the goal of bringing to the research community the latest advances in the robotics field based on their significance and quality. During the latest fifteen years, the STAR series has featured publication of both monographs and edited collections. Among the latter, the proceedings of thematic symposia devoted to excellence in robotics research, such as ISRR, ISER, FSR, and WAFR, have been regularly included in STAR. The expansion of our field as well as the emergence of new research areas has motivated us to enlarge the pool of proceedings in the STAR series in the past few years. This has ultimately led to launching a sister series in parallel to STAR. The Springer Proceedings in Advanced Robotics (SPAR) is dedicated to the timely dissemination of the latest research results presented in selected symposia and workshops. This volume of the SPAR series brings the proceedings of the twelfth edition of the Workshop Algorithmic Foundations of Robotics (WAFR). WAFR went back to its roots and was held from December 18 to 20, 2016, in San Francisco, California, the same city in which the very first WAFR was held in 1994. The volume edited by Ken Goldberg, Pieter Abbeel, Kostas Bekris, and Lauren Miller is a collection of 58 contributions spanning a wide range of applications in manufacturing, medicine, distributed robotics, human--robot interaction, intelligent prosthetics, computer animation, computational biology, and many other areas. Validation of algorithms, design concepts, or techniques is the common thread running through this focused collection. Rich by topics and authoritative contributors, WAFR culminates with this unique reference on the current developments and new directions in the field of algorithmic foundations. A very fine addition to the series! More information about the conference, including videos of the presentations can be found under the conference's website: http://wafr2016.berkeley.edu |
2019 |
Kimmel, A; Shome, R; Bekris, K Anytime Motion Planning for Prehensile Manipulation in Dense Clutter Journal Article Advanced Robotics, 2019. @article{Kimmel:2019ab, title = {Anytime Motion Planning for Prehensile Manipulation in Dense Clutter}, author = {A Kimmel and R Shome and K Bekris}, url = {https://www.rahulsho.me/papers/ar_gmp.pdf}, year = {2019}, date = {2019-11-01}, journal = {Advanced Robotics}, abstract = {Many methods have been developed for planning the motion of robotic arms for picking and placing, ranging from local optimization to global search techniques, which are effective for sparsely placed objects. Dense clutter, however, still adversely affects the success rate, computation times, and quality of solutions in many real-world setups. The proposed method achieves high success ratio in clutter with anytime performance by returning solutions quickly and improving their quality over time. The method first explores the lower dimensional end effector's task space efficiently by ignoring the arm, and build a discrete approximation of a navigation function. This is performed online, without prior knowledge of the scene. Then, an informed sampling-based planner for the entire arm uses Jacobian- based steering to reach promising end effector poses given the task space guidance. This process is also comprehensive and allows the exploration of alternative paths over time if the task space guidance is misleading. This paper evaluates the proposed method against alternatives in picking or placing tasks among varying amounts of clutter for a variety of robotic manipulators with different end-effectors. The results suggest that the method reliably provides higher quality solution paths quicker, with a higher success rate relative to alternatives.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Many methods have been developed for planning the motion of robotic arms for picking and placing, ranging from local optimization to global search techniques, which are effective for sparsely placed objects. Dense clutter, however, still adversely affects the success rate, computation times, and quality of solutions in many real-world setups. The proposed method achieves high success ratio in clutter with anytime performance by returning solutions quickly and improving their quality over time. The method first explores the lower dimensional end effector's task space efficiently by ignoring the arm, and build a discrete approximation of a navigation function. This is performed online, without prior knowledge of the scene. Then, an informed sampling-based planner for the entire arm uses Jacobian- based steering to reach promising end effector poses given the task space guidance. This process is also comprehensive and allows the exploration of alternative paths over time if the task space guidance is misleading. This paper evaluates the proposed method against alternatives in picking or placing tasks among varying amounts of clutter for a variety of robotic manipulators with different end-effectors. The results suggest that the method reliably provides higher quality solution paths quicker, with a higher success rate relative to alternatives. |
Littlefield, Z; Surovik, D; Vespignani, M; Bruce, J; Wang, W; Bekris, K Kinodynamic Planning for Spherical Tensegrity Locomotion with Effective Gait Primitives Journal Article International Journal of Robotics Research (IJRR), 2019. @article{Littlefield:2019aa, title = {Kinodynamic Planning for Spherical Tensegrity Locomotion with Effective Gait Primitives}, author = {Z Littlefield and D Surovik and M Vespignani and J Bruce and W Wang and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/kinodynamic_tensegrity.pdf}, year = {2019}, date = {2019-10-01}, journal = {International Journal of Robotics Research (IJRR)}, abstract = {Tensegrity-based robots can achieve locomotion through shape deformation and compliance. They are highly adaptable to their surroundings, have light weight, low cost and are physically robust. Their high dimensionality and strongly dynamic nature, however, complicate motion planning. Efforts to-date have primarily considered quasi-static reconfiguration and short-term dynamic motion of tensegrity robots, which do not fully exploit the underlying system dynamics in the long term. Longer-horizon planning has previously required costly search over the full space of valid control inputs. This work synthesizes new and existing approaches to produce dynamic long-term motion while balancing the computational demand. A numerical process based upon quasi-static assumptions is first applied to deform the system into an unstable configuration, causing forward motion. The dynamical characteristics of the result are then altered via a few simple parameters to produce a small but diverse set of useful behaviors. The proposed approach takes advantage of identified symmetries on the prototypical spherical tensegrity robot, which reduce the number of needed gaits but allow motion along different directions. These gaits are first combined with a standard search method to achieve long term planning in environments where the developed gaits are effective. For more complex environments, the various motion primitives are paired with the fall-back option of random valid actions and are used by an informed sampling-based kinodynamic motion planner with anytime properties. Evaluations using a physics-based model for the prototypical robot demonstrate that modest but efficiently-applied search effort can unlock the utility of dynamic tensegrity motion to produce high-quality solutions.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Tensegrity-based robots can achieve locomotion through shape deformation and compliance. They are highly adaptable to their surroundings, have light weight, low cost and are physically robust. Their high dimensionality and strongly dynamic nature, however, complicate motion planning. Efforts to-date have primarily considered quasi-static reconfiguration and short-term dynamic motion of tensegrity robots, which do not fully exploit the underlying system dynamics in the long term. Longer-horizon planning has previously required costly search over the full space of valid control inputs. This work synthesizes new and existing approaches to produce dynamic long-term motion while balancing the computational demand. A numerical process based upon quasi-static assumptions is first applied to deform the system into an unstable configuration, causing forward motion. The dynamical characteristics of the result are then altered via a few simple parameters to produce a small but diverse set of useful behaviors. The proposed approach takes advantage of identified symmetries on the prototypical spherical tensegrity robot, which reduce the number of needed gaits but allow motion along different directions. These gaits are first combined with a standard search method to achieve long term planning in environments where the developed gaits are effective. For more complex environments, the various motion primitives are paired with the fall-back option of random valid actions and are used by an informed sampling-based kinodynamic motion planner with anytime properties. Evaluations using a physics-based model for the prototypical robot demonstrate that modest but efficiently-applied search effort can unlock the utility of dynamic tensegrity motion to produce high-quality solutions. |
Kimmel, A; Sintov, A; Tan, J; Wen, B; Boularias, A; Bekris, K Belief-Space Planning Using Learned Models with Application to Underactuated Hands Conference International Symposium on Robotics Research (ISRR), Hanoi, Vietnam, 2019. @conference{Kimmel:2019aa, title = {Belief-Space Planning Using Learned Models with Application to Underactuated Hands}, author = {A Kimmel and A Sintov and J Tan and B Wen and A Boularias and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/belief_space_learned_models_adaptive_hands.pdf}, year = {2019}, date = {2019-10-01}, booktitle = {International Symposium on Robotics Research (ISRR)}, address = {Hanoi, Vietnam}, abstract = {Acquiring a precise model is a challenging task for many important robotic tasks and systems - including in-hand manipulation using underactuated, adaptive hands. Learning stochastic, data-driven models is a promising alternative as they provide not only a way to propagate forward the system dynamics, but also express the uncertainty present in the collected data. Therefore, such models en- able planning in the space of state distributions, i.e., in the belief space. This paper proposes a planning framework that employs stochastic, learned models, which ex- press a distribution of states as a set of particles. The integration achieves anytime behavior in terms of returning paths of increasing quality under constraints for the probability of success to achieve a goal. The focus of this effort is on pushing the efficiency of the overall methodology despite the notorious computational hardness of belief-space planning. Experiments show that the proposed framework enables reaching a desired goal with higher success rate compared to alternatives in sim- ple benchmarks. This work also provides an application to the motivating domain of in-hand manipulation with underactuated, adaptive hands, both in the case of physically-simulated experiments as well as demonstrations with a real hand.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Acquiring a precise model is a challenging task for many important robotic tasks and systems - including in-hand manipulation using underactuated, adaptive hands. Learning stochastic, data-driven models is a promising alternative as they provide not only a way to propagate forward the system dynamics, but also express the uncertainty present in the collected data. Therefore, such models en- able planning in the space of state distributions, i.e., in the belief space. This paper proposes a planning framework that employs stochastic, learned models, which ex- press a distribution of states as a set of particles. The integration achieves anytime behavior in terms of returning paths of increasing quality under constraints for the probability of success to achieve a goal. The focus of this effort is on pushing the efficiency of the overall methodology despite the notorious computational hardness of belief-space planning. Experiments show that the proposed framework enables reaching a desired goal with higher success rate compared to alternatives in sim- ple benchmarks. This work also provides an application to the motivating domain of in-hand manipulation with underactuated, adaptive hands, both in the case of physically-simulated experiments as well as demonstrations with a real hand. |
Sivaramakrishnan, A; Littlefield, Z; Bekris, K Towards Learning Efficient Maneuver Sets for Kinodynamic Motion Planning Technical Report 2019. @techreport{Sivaramakrishnan:2019aa, title = {Towards Learning Efficient Maneuver Sets for Kinodynamic Motion Planning}, author = {A Sivaramakrishnan and Z Littlefield and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/Learning_Maneuver_Sets_PlanRob2019.pdf}, year = {2019}, date = {2019-07-01}, school = {PlanRob 2019 Workshop of ICAPS 2019}, abstract = {Planning for systems with dynamics is challenging as often there is no local planner available and the only primitive to explore the state space is forward propagation of controls. In this context, tree sampling-based planners have been developed, some of which achieve asymptotic optimality by propagating random controls during each iteration. While desirable for the analysis, random controls result in slow convergence to high quality trajectories in practice. This short position statement first argues that if a kinodynamic planner has access to local maneuvers that appropriately balance an exploitation-exploration trade-off, the plannertextquoterights per iteration performance is significantly improved. Furthermore, this work argues for the integration of modern machine learning frameworks with state-of-the-art, informed and asymptotically optimal kinodynamic planners. The proposed approach involves using using neural networks to infer local maneuvers for a robotic system with dynamics, which properly balance the above exploitation-exploration trade-off. Preliminary indications in simulated environments and systems are promising but also point to certain challenges that motivate further research in this direction.}, keywords = {}, pubstate = {published}, tppubtype = {techreport} } Planning for systems with dynamics is challenging as often there is no local planner available and the only primitive to explore the state space is forward propagation of controls. In this context, tree sampling-based planners have been developed, some of which achieve asymptotic optimality by propagating random controls during each iteration. While desirable for the analysis, random controls result in slow convergence to high quality trajectories in practice. This short position statement first argues that if a kinodynamic planner has access to local maneuvers that appropriately balance an exploitation-exploration trade-off, the plannertextquoterights per iteration performance is significantly improved. Furthermore, this work argues for the integration of modern machine learning frameworks with state-of-the-art, informed and asymptotically optimal kinodynamic planners. The proposed approach involves using using neural networks to infer local maneuvers for a robotic system with dynamics, which properly balance the above exploitation-exploration trade-off. Preliminary indications in simulated environments and systems are promising but also point to certain challenges that motivate further research in this direction. |
Shome, R; Bekris, K Anytime Multi-Arm Task and Motion Planning for Pick-and-Place of Individual Objects Via Handoffs Conference IEEE International Conference on Multi-Robot and Multi-Agent Systems (MRS), New Brunswick, NJ, 2019. @conference{Shome:2019aa, title = {Anytime Multi-Arm Task and Motion Planning for Pick-and-Place of Individual Objects Via Handoffs}, author = {R Shome and K Bekris}, url = {https://arxiv.org/abs/1905.03179}, year = {2019}, date = {2019-06-01}, booktitle = {IEEE International Conference on Multi-Robot and Multi-Agent Systems (MRS)}, address = {New Brunswick, NJ}, abstract = {Automation applications are pushing the deployment of many high DoF manipulators in warehouse and manufacturing environments. This has motivated many efforts on optimizing manipulation tasks involving a single arm. Coordinating multiple arms for manipulation, however, introduces additional computational challenges arising from the increased DoFs, as well as the combinatorial increase in the available operations that many manipulators can perform, including handoffs between arms. The focus here is on the case of pick-and-place tasks, which require a sequence of handoffs to be executed, so as to achieve computational efficiency, asymptotic optimality and practical anytime performance. The paper leverages recent advances in multi-robot motion planning for high DoF systems to propose a novel multi-modal extension of the dRRT* algorithm. The key insight is that, instead of naively solving a sequence of motion planning problems, it is computationally advantageous to directly explore the composite space of the integrated multi-arm task and motion planning problem, given input sets of possible pick and handoff configurations. Asymptotic optimality guarantees are possible by sampling additional picks and handoffs over time. The evaluation shows that the approach finds initial solutions fast and improves their quality over time. It also succeeds in finding solutions to harder problem instances relative to alternatives and can scale effectively as the number of robots increases.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Automation applications are pushing the deployment of many high DoF manipulators in warehouse and manufacturing environments. This has motivated many efforts on optimizing manipulation tasks involving a single arm. Coordinating multiple arms for manipulation, however, introduces additional computational challenges arising from the increased DoFs, as well as the combinatorial increase in the available operations that many manipulators can perform, including handoffs between arms. The focus here is on the case of pick-and-place tasks, which require a sequence of handoffs to be executed, so as to achieve computational efficiency, asymptotic optimality and practical anytime performance. The paper leverages recent advances in multi-robot motion planning for high DoF systems to propose a novel multi-modal extension of the dRRT* algorithm. The key insight is that, instead of naively solving a sequence of motion planning problems, it is computationally advantageous to directly explore the composite space of the integrated multi-arm task and motion planning problem, given input sets of possible pick and handoff configurations. Asymptotic optimality guarantees are possible by sampling additional picks and handoffs over time. The evaluation shows that the approach finds initial solutions fast and improves their quality over time. It also succeeds in finding solutions to harder problem instances relative to alternatives and can scale effectively as the number of robots increases. |
Kleinbort, M; Solovey, K; Littlefield, Z; Bekris, K; Halperin, D Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning with Forward Propagation Journal Article IEEE Robotics and Automation Letters (RA-L) (also appearing at IEEE ICRA 2019), 2019. @article{Kleinbort:2019aa, title = {Probabilistic Completeness of RRT for Geometric and Kinodynamic Planning with Forward Propagation}, author = {M Kleinbort and K Solovey and Z Littlefield and K Bekris and D Halperin}, url = {https://www.cs.rutgers.edu/~kb572/pubs/prob_completeness_rrt.pdf}, year = {2019}, date = {2019-01-01}, journal = {IEEE Robotics and Automation Letters (RA-L) (also appearing at IEEE ICRA 2019)}, abstract = {The Rapidly-exploring Random Tree (RRT) algorithm has been one of the most prevalent and popular motion-planning techniques for two decades now. Surprisingly, in spite of its centrality, there has been an active debate under which conditions RRT is probabilistically complete. We provide two new proofs of probabilistic completeness (PC) of RRT with a reduced set of assumptions. The first one for the purely geometric setting, where we only require that the solution path has a certain clearance from the obstacles. For the kinodynamic case with forward propagation of random controls and duration, we only consider in addition mild Lipschitz-continuity conditions. These proofs fill a gap in the study of RRT itself. They also lay sound foundations for a variety of more recent and alternative sampling-based methods, whose PC property relies on that of RRT.}, keywords = {}, pubstate = {published}, tppubtype = {article} } The Rapidly-exploring Random Tree (RRT) algorithm has been one of the most prevalent and popular motion-planning techniques for two decades now. Surprisingly, in spite of its centrality, there has been an active debate under which conditions RRT is probabilistically complete. We provide two new proofs of probabilistic completeness (PC) of RRT with a reduced set of assumptions. The first one for the purely geometric setting, where we only require that the solution path has a certain clearance from the obstacles. For the kinodynamic case with forward propagation of random controls and duration, we only consider in addition mild Lipschitz-continuity conditions. These proofs fill a gap in the study of RRT itself. They also lay sound foundations for a variety of more recent and alternative sampling-based methods, whose PC property relies on that of RRT. |
2018 |
Shome, R; Solovey, K; Yu, J; Bekris, K; Halperin, D Fast and High-Quality Dual-Arm Rearrangement in Synchronous, Monotone Tabletop Setups Conference Workshop on the Algorithmic Foundations of Robotics (WAFR), MΓ©rida, MΓ©xico, 2018. @conference{Shome:2018aa, title = {Fast and High-Quality Dual-Arm Rearrangement in Synchronous, Monotone Tabletop Setups}, author = {R Shome and K Solovey and J Yu and K Bekris and D Halperin}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Fast_High_Quality_Dual_Arm_Rearrangement.pdf}, year = {2018}, date = {2018-12-01}, booktitle = {Workshop on the Algorithmic Foundations of Robotics (WAFR)}, address = {MΓ©rida, MΓ©xico}, abstract = {Rearranging objects on a planar surface arises in a variety of applications, such as packaging. Using two arms can improve efficiency but introduces new combinatorial challenges. This paper studies the structure of dual-arm rearrangement for synchronous, monotone tabletop setups and develops an optimal MILP model. It then describes an efficient and scalable algorithm, which first minimizes the cost of object transfers and then of transitions between objects. This is motivated by the fact that asymptotically object transfers dominate the cost of solutions. Moreover, a lazy strategy minimizes the number of motion planning calls and results in significant speedups. Theoretical arguments support the benefits of using two arms and indicate that synchronous operation introduces only a small cost increase. Experiments support these points and show that the scalable method can quickly compute solutions close to optimal for the considered setup.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Rearranging objects on a planar surface arises in a variety of applications, such as packaging. Using two arms can improve efficiency but introduces new combinatorial challenges. This paper studies the structure of dual-arm rearrangement for synchronous, monotone tabletop setups and develops an optimal MILP model. It then describes an efficient and scalable algorithm, which first minimizes the cost of object transfers and then of transitions between objects. This is motivated by the fact that asymptotically object transfers dominate the cost of solutions. Moreover, a lazy strategy minimizes the number of motion planning calls and results in significant speedups. Theoretical arguments support the benefits of using two arms and indicate that synchronous operation introduces only a small cost increase. Experiments support these points and show that the scalable method can quickly compute solutions close to optimal for the considered setup. |
Kimmel, A; Shome, R; Littlefield, Z; Bekris, K Fast, Anytime Motion Planning for Prehensile Manipulation in Clutter Conference IEEE-RAS International Conference on Humanoid Robots (Humanoids), Beijing, China, 2018. @conference{Kimmel:2018aa, title = {Fast, Anytime Motion Planning for Prehensile Manipulation in Clutter}, author = {A Kimmel and R Shome and Z Littlefield and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/gmp.pdf}, year = {2018}, date = {2018-11-01}, booktitle = {IEEE-RAS International Conference on Humanoid Robots (Humanoids)}, address = {Beijing, China}, abstract = {Many methods have been developed for planning the motion of robotic arms for picking and placing, ranging from local optimization to global search techniques, which are effective for sparsely placed objects. Dense clutter, however, still adversely affects the success rate, computation times, and quality of solutions in many real-world setups. The current work integrates tools from existing methodologies and proposes a framework that achieves high success ratio in clutter with anytime performance by returning solutions quickly and improving their quality over time, measured in terms of end effectortextquoterights displacement. The idea is to first explore the lower dimensional end effectortextquoterights task space efficiently by ignoring the arm, and build a discrete approximation of a navigation function, which guides the end effector towards the set of available grasps or object placements. This is performed online, without prior knowledge of the scene. Then, an informed sampling-based planner for the entire arm uses Jacobian-based steering to reach promising end effector poses given the task space guidance. While informed, the method is also comprehensive and allows the exploration of alternative paths over time if the task space guidance does not lead to a solution. This paper evaluates the proposed method against alternatives in picking or placing tasks among varying amounts of clutter for a variety of robotic manipulators with different end-effectors. The results suggest that the method reliably provides higher quality solution paths quicker, with a higher success rate relative to alternatives.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Many methods have been developed for planning the motion of robotic arms for picking and placing, ranging from local optimization to global search techniques, which are effective for sparsely placed objects. Dense clutter, however, still adversely affects the success rate, computation times, and quality of solutions in many real-world setups. The current work integrates tools from existing methodologies and proposes a framework that achieves high success ratio in clutter with anytime performance by returning solutions quickly and improving their quality over time, measured in terms of end effectortextquoterights displacement. The idea is to first explore the lower dimensional end effectortextquoterights task space efficiently by ignoring the arm, and build a discrete approximation of a navigation function, which guides the end effector towards the set of available grasps or object placements. This is performed online, without prior knowledge of the scene. Then, an informed sampling-based planner for the entire arm uses Jacobian-based steering to reach promising end effector poses given the task space guidance. While informed, the method is also comprehensive and allows the exploration of alternative paths over time if the task space guidance does not lead to a solution. This paper evaluates the proposed method against alternatives in picking or placing tasks among varying amounts of clutter for a variety of robotic manipulators with different end-effectors. The results suggest that the method reliably provides higher quality solution paths quicker, with a higher success rate relative to alternatives. |
Littlefield, Z; Bekris, K Efficient and Asymptotically Optimal Kinodynamic Motion Planning Via Dominance-Informed Regions Conference IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Madrid, Spain, 2018. @conference{Littlefield:2018aa, title = {Efficient and Asymptotically Optimal Kinodynamic Motion Planning Via Dominance-Informed Regions}, author = {Z Littlefield and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/iros_dirt.pdf}, year = {2018}, date = {2018-10-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, address = {Madrid, Spain}, abstract = {Motion planners have been recently developed that provide path quality guarantees for robots with dynamics. This work aims to improve upon their efficiency, while maintaining their properties. Inspired by informed search principles, one objective is to use heuristics. Nevertheless, comprehensive and fast spatial exploration of the state space is still important in robotics. For this reason, this work introduces Dominance- Informed Regions (DIR), which express both whether parts of the space are unexplored and whether they lie along a high quality path. Furthermore, to speed up the generation of a successful successor state, which involves collision checking or physics-based simulation, a proposed strategy generates the most promising successor in an informed way, while maintaing properties. Overall, this paper introduces a new informed and asymptotically optimal kinodynamic motion planner, the Dominance-Informed Region Tree (DIRT). The method balances exploration-exploitation tradeoffs without many explicit parameters. It is shown to outperform sampling-based and search-based methods for robots with significant dynamics}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Motion planners have been recently developed that provide path quality guarantees for robots with dynamics. This work aims to improve upon their efficiency, while maintaining their properties. Inspired by informed search principles, one objective is to use heuristics. Nevertheless, comprehensive and fast spatial exploration of the state space is still important in robotics. For this reason, this work introduces Dominance- Informed Regions (DIR), which express both whether parts of the space are unexplored and whether they lie along a high quality path. Furthermore, to speed up the generation of a successful successor state, which involves collision checking or physics-based simulation, a proposed strategy generates the most promising successor in an informed way, while maintaing properties. Overall, this paper introduces a new informed and asymptotically optimal kinodynamic motion planner, the Dominance-Informed Region Tree (DIRT). The method balances exploration-exploitation tradeoffs without many explicit parameters. It is shown to outperform sampling-based and search-based methods for robots with significant dynamics |
Han, S; Stiffler, N; Bekris, K; Yu, J Efficient, High-Quality Stack Rearrangement Journal Article IEEE Robotics and Automation Letters (RA-L) [Also accepted to appear at the 2018 IEEE International Conference on Robotics and Automation (ICRA)], 3 , pp. 1608β1615, 2018. @article{187, title = {Efficient, High-Quality Stack Rearrangement}, author = {S Han and N Stiffler and K Bekris and J Yu}, url = {https://www.cs.rutgers.edu/~kb572/pubs/stack_rearrangement.pdf}, year = {2018}, date = {2018-07-01}, journal = {IEEE Robotics and Automation Letters (RA-L) [Also accepted to appear at the 2018 IEEE International Conference on Robotics and Automation (ICRA)]}, volume = {3}, pages = {1608--1615}, abstract = {This work studies rearrangement problems involving the sorting of robots or objects in stack-like containers, which can be accessed only from one side. Two scenarios are considered: one where every robot or object needs to reach a particular stack, and a setting in which each robot has a distinct position within a stack. In both cases, the goal is to minimize the number of stack removals that need to be performed. Stack rearrangement is shown to be intimately connected to pebble motion problems, a useful abstraction in multi-robot path planning. Through this connection, feasibility of stack rearrangement can be readily addressed. The paper continues to establish lower and upper bounds on optimality, which differ only by a logarithmic factor, in terms of stack removals. An algorithmic solution is then developed that produces suboptimal paths much quicker than a pebble motion solver. Furthermore, informed search-based methods are proposed for finding high-quality solutions. The efficiency and desirable scalability of the methods is demonstrated in simulation.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This work studies rearrangement problems involving the sorting of robots or objects in stack-like containers, which can be accessed only from one side. Two scenarios are considered: one where every robot or object needs to reach a particular stack, and a setting in which each robot has a distinct position within a stack. In both cases, the goal is to minimize the number of stack removals that need to be performed. Stack rearrangement is shown to be intimately connected to pebble motion problems, a useful abstraction in multi-robot path planning. Through this connection, feasibility of stack rearrangement can be readily addressed. The paper continues to establish lower and upper bounds on optimality, which differ only by a logarithmic factor, in terms of stack removals. An algorithmic solution is then developed that produces suboptimal paths much quicker than a pebble motion solver. Furthermore, informed search-based methods are proposed for finding high-quality solutions. The efficiency and desirable scalability of the methods is demonstrated in simulation. |
2017 |
Dobson, A; Solovey, K; Shome, R; Halperin, D; Bekris, K Scalable Asymptotically-Optimal Multi-Robot Motion Planning Conference 1st IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS), [Best Paper Award] [Best Paper Award], Los Angeles, CA, USA, 2017. @conference{Dobson:2017aa, title = {Scalable Asymptotically-Optimal Multi-Robot Motion Planning}, author = {A Dobson and K Solovey and R Shome and D Halperin and K Bekris}, url = {https://arxiv.org/abs/1706.09932}, year = {2017}, date = {2017-12-01}, booktitle = {1st IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS)}, publisher = {[Best Paper Award]}, address = {Los Angeles, CA, USA}, organization = {[Best Paper Award]}, abstract = {Discovering high-quality paths for multi-robot problems can be achieved, in principle, through asymptotically-optimal data structures in the composite space of all robots, such as a sampling-based roadmap or a tree. The hardness of motion planning, however, which depends exponentially on the number of robots, renders the explicit construction of such structures impractical. This work proposes a scalable, sampling-based planner for coupled multi-robot problems that provides desirable path-quality guarantees. The proposed dRRT* is an informed, asymptotically-optimal extension of a prior method dRRT, which introduced the idea of building roadmaps for each robot and implicitly searching the tensor product of these structures in the composite space. The paper describes the conditions for convergence to optimal paths in multi-robot problems. Moreover, simulated experiments indicate dRRT* converges to high-quality paths and scales to higher numbers of robots where various alternatives fail. It can also be used on high-dimensional challenges, such as planning for robot manipulators.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Discovering high-quality paths for multi-robot problems can be achieved, in principle, through asymptotically-optimal data structures in the composite space of all robots, such as a sampling-based roadmap or a tree. The hardness of motion planning, however, which depends exponentially on the number of robots, renders the explicit construction of such structures impractical. This work proposes a scalable, sampling-based planner for coupled multi-robot problems that provides desirable path-quality guarantees. The proposed dRRT* is an informed, asymptotically-optimal extension of a prior method dRRT, which introduced the idea of building roadmaps for each robot and implicitly searching the tensor product of these structures in the composite space. The paper describes the conditions for convergence to optimal paths in multi-robot problems. Moreover, simulated experiments indicate dRRT* converges to high-quality paths and scales to higher numbers of robots where various alternatives fail. It can also be used on high-dimensional challenges, such as planning for robot manipulators. |
Littlefield, Z; Surovik, D; Wang, W; Bekris, K From Quasi-Static to Kinodynamic Planning for Spherical Tensegrity Locomotion Conference International Symosium on Robotics Research (ISRR), Puerto Varas, Chile, 2017. @conference{Littlefield:2017aa, title = {From Quasi-Static to Kinodynamic Planning for Spherical Tensegrity Locomotion}, author = {Z Littlefield and D Surovik and W Wang and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/isrr17_quasistatic_kinodynamic.pdf}, year = {2017}, date = {2017-12-01}, booktitle = {International Symosium on Robotics Research (ISRR)}, address = {Puerto Varas, Chile}, abstract = {Tensegrity-based robots can achieve locomotion through shape deformation and compliance. They are highly adaptable to surroundings, have light weight, low cost and high endurance. Their high dimensionality and highly dynamic nature, however, complicate motion planning. So far, only rudimentary quasi-static solutions have been achieved, which do not utilize tensegrity dynamics. This work explores a spectrum of planning methods that increasingly allow dynamic motion for such platforms. Symmetries are first identified for a prototypical spherical tensegrity robot, which reduce the number of needed gaits. Then, a numerical process is proposed for generating quasi-static gaits that move forward the systemtextquoterights center of mass in different directions. These gaits are combined with a search method to achieve a quasi-static solution. In complex environments, however, this approach is not able to fully explore the space and utilize dynamics. This motivates the application of sampling-based, kinodynamic planners. This paper proposes such a method for tensegrity locomotion that is informed and has anytime properties. The proposed solution allows the generation of dynamic motion and provides good quality solutions. Evaluation using a physics-based model for the prototypical robot highlight the benefits of the proposed scheme and the limits of quasi-static solutions.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Tensegrity-based robots can achieve locomotion through shape deformation and compliance. They are highly adaptable to surroundings, have light weight, low cost and high endurance. Their high dimensionality and highly dynamic nature, however, complicate motion planning. So far, only rudimentary quasi-static solutions have been achieved, which do not utilize tensegrity dynamics. This work explores a spectrum of planning methods that increasingly allow dynamic motion for such platforms. Symmetries are first identified for a prototypical spherical tensegrity robot, which reduce the number of needed gaits. Then, a numerical process is proposed for generating quasi-static gaits that move forward the systemtextquoterights center of mass in different directions. These gaits are combined with a search method to achieve a quasi-static solution. In complex environments, however, this approach is not able to fully explore the space and utilize dynamics. This motivates the application of sampling-based, kinodynamic planners. This paper proposes such a method for tensegrity locomotion that is informed and has anytime properties. The proposed solution allows the generation of dynamic motion and provides good quality solutions. Evaluation using a physics-based model for the prototypical robot highlight the benefits of the proposed scheme and the limits of quasi-static solutions. |
Surovik, D; Bekris, K Deep Coverage: Motion Synthesis in the Data-Driven Era Conference International Symposium on Robotics Research (ISRR), Puerto Varas, Chile, 2017. @conference{Surovik:2017aa, title = {Deep Coverage: Motion Synthesis in the Data-Driven Era}, author = {D Surovik and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/deep_coverage.pdf}, year = {2017}, date = {2017-12-01}, booktitle = {International Symposium on Robotics Research (ISRR)}, address = {Puerto Varas, Chile}, abstract = {Effective robotic systems must be able to produce desired motion in a sufficiently broad variety of robot states and environmental contexts. Classic control and planning methods achieve such coverage through the synthesis of model-based components. New applications and platforms, such as soft robots, present novel challenges, ranging from richer dynamical behaviors to increasingly unstructured environments. In these setups, derived models frequently fail to express important real-world subtleties. An increasingly popular approach to deal with this issue corresponds to end-to-end machine learning architectures, which adapt to such complexities through a data-driven process. Unfortunately, however, data are not always available for all regions of the operational space, which complicates the extensibility of these solutions. In light of these issues, this paper proposes a reconciliation of classic motion synthesis with modern data-driven tools towards the objective of "deep coverage". This notion utilizes the concept of composability, a feature of traditional control and planning methods, over data-derived "motion elements", towards generalizable and scalable solutions that adapt to real-world experience.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Effective robotic systems must be able to produce desired motion in a sufficiently broad variety of robot states and environmental contexts. Classic control and planning methods achieve such coverage through the synthesis of model-based components. New applications and platforms, such as soft robots, present novel challenges, ranging from richer dynamical behaviors to increasingly unstructured environments. In these setups, derived models frequently fail to express important real-world subtleties. An increasingly popular approach to deal with this issue corresponds to end-to-end machine learning architectures, which adapt to such complexities through a data-driven process. Unfortunately, however, data are not always available for all regions of the operational space, which complicates the extensibility of these solutions. In light of these issues, this paper proposes a reconciliation of classic motion synthesis with modern data-driven tools towards the objective of "deep coverage". This notion utilizes the concept of composability, a feature of traditional control and planning methods, over data-derived "motion elements", towards generalizable and scalable solutions that adapt to real-world experience. |
Shome, R; Bekris, K IEEE International Conference on Humanoid Robots, Birmingham, UK, 2017. @conference{Shome:2017aa, title = {Improving the Scalability of Asymptotically Optimal Motion Planning for Humanoid Dual-Arm Manipulators}, author = {R Shome and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/asymp_optimal_dual_arm.pdf}, year = {2017}, date = {2017-11-01}, booktitle = {IEEE International Conference on Humanoid Robots}, address = {Birmingham, UK}, abstract = {Due to high-dimensionality, many motion planners for dual-arm systems follow a decoupled approach but do not provide guarantees. Asymptotically optimal sampling-based planners provide guarantees, but in practice face computational scalability challenges. This work improves the computational scalability of the latter methods in this domain. It builds on top of recent advances in multi-robot motion planning, which provide guarantees without having to explicitly construct a roadmap in the composite space of all robots. The proposed framework builds roadmaps for components of a humanoid robottextquoterights kinematic chain. Then, the tensor product of these component roadmaps is searched implicitly online in a way that asymptotic optimality is provided. Appropriate heuristics from the component roadmaps are utilized for discovering the solution in the composite space effectively. Evaluation on various dual-arm problems show that the method returns paths of increasing quality, has significantly reduced space requirements and improved convergence rate relative to the standard asymptotically optimal approaches.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Due to high-dimensionality, many motion planners for dual-arm systems follow a decoupled approach but do not provide guarantees. Asymptotically optimal sampling-based planners provide guarantees, but in practice face computational scalability challenges. This work improves the computational scalability of the latter methods in this domain. It builds on top of recent advances in multi-robot motion planning, which provide guarantees without having to explicitly construct a roadmap in the composite space of all robots. The proposed framework builds roadmaps for components of a humanoid robottextquoterights kinematic chain. Then, the tensor product of these component roadmaps is searched implicitly online in a way that asymptotic optimality is provided. Appropriate heuristics from the component roadmaps are utilized for discovering the solution in the composite space effectively. Evaluation on various dual-arm problems show that the method returns paths of increasing quality, has significantly reduced space requirements and improved convergence rate relative to the standard asymptotically optimal approaches. |
Krontiris, A; Bekris, K Tradeoffs in the Computation of Minimum Constraint Removal Paths for Manipulation Planning Journal Article Advanced Robotics Journal, 31 , pp. 1313β1324, 2017. @article{Krontiris:2017aa, title = {Tradeoffs in the Computation of Minimum Constraint Removal Paths for Manipulation Planning}, author = {A Krontiris and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/min_constraint_removal.pdf}, year = {2017}, date = {2017-09-01}, journal = {Advanced Robotics Journal}, volume = {31}, pages = {1313--1324}, abstract = {The typical objective in path planning is to find the shortest feasible path. Many times, however, such paths may not be available given constraints, such as movable obstacles. This frequently happens in manipulation planning, where it may be desirable to identify the minimum set of movable obstacles to be cleared to manipulate a target object. This is a similar objective to that of the Minimum Constraint Removal problem, which, however, does not exhibit dynamic programming properties, i.e., subsets of optimum solutions are not necessarily optimal. Thus, searching for MCR paths is computationally expensive. Motivated by this challenge and related work, this paper investigates approximations for computing MCR paths in the context of manipulation planning. The proposed framework searches for MCR paths up to a certain length of solution in terms of end-effector distance. This length can be defined as a multiple of the shortest path length in the space when movable objects are ignored. Given experimental evaluation on simulated manipulation planning challenges, the bounded-length approximation provides a desirable tradeoff between minimizing constraints, computational cost and path length.}, keywords = {}, pubstate = {published}, tppubtype = {article} } The typical objective in path planning is to find the shortest feasible path. Many times, however, such paths may not be available given constraints, such as movable obstacles. This frequently happens in manipulation planning, where it may be desirable to identify the minimum set of movable obstacles to be cleared to manipulate a target object. This is a similar objective to that of the Minimum Constraint Removal problem, which, however, does not exhibit dynamic programming properties, i.e., subsets of optimum solutions are not necessarily optimal. Thus, searching for MCR paths is computationally expensive. Motivated by this challenge and related work, this paper investigates approximations for computing MCR paths in the context of manipulation planning. The proposed framework searches for MCR paths up to a certain length of solution in terms of end-effector distance. This length can be defined as a multiple of the shortest path length in the space when movable objects are ignored. Given experimental evaluation on simulated manipulation planning challenges, the bounded-length approximation provides a desirable tradeoff between minimizing constraints, computational cost and path length. |
Littlefield, Z; Bekris, K Informed Asymptotically Near-Optimal Planning for Field Robots with Dynamics Conference 11th Conference on Field and Service Robotics (FSR) 2017, Zurich, Switzerland, 2017. @conference{Littlefield:2017ab, title = {Informed Asymptotically Near-Optimal Planning for Field Robots with Dynamics}, author = {Z Littlefield and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/fsr_isst.pdf}, year = {2017}, date = {2017-09-01}, booktitle = {11th Conference on Field and Service Robotics (FSR) 2017}, address = {Zurich, Switzerland}, abstract = {Recent progress in sampling-based planning has provided performance guarantees in terms of optimizing trajectory cost even in the presence of significant dynamics. The STABLE SPARSE RRT (SST) algorithm has these desirable path quality properties and achieves computational efficiency by maintaining a sparse set of state-space samples. The current paper focuses on field robotics, where workspace information can be used to effectively guide the search process of a planner, and improves the computational performance of SST by appropriately utilizing such information in the form of heuristics. The workspace information guides the exploration process of the planner and focuses it on the useful subset of the state space. The resulting Informed-SST is evaluated in several scenarios involving either ground vehicles or quadrotors. This includes testing for a physically-simulated vehicle over uneven terrain, which is a computationally expensive challenge.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Recent progress in sampling-based planning has provided performance guarantees in terms of optimizing trajectory cost even in the presence of significant dynamics. The STABLE SPARSE RRT (SST) algorithm has these desirable path quality properties and achieves computational efficiency by maintaining a sparse set of state-space samples. The current paper focuses on field robotics, where workspace information can be used to effectively guide the search process of a planner, and improves the computational performance of SST by appropriately utilizing such information in the form of heuristics. The workspace information guides the exploration process of the planner and focuses it on the useful subset of the state space. The resulting Informed-SST is evaluated in several scenarios involving either ground vehicles or quadrotors. This includes testing for a physically-simulated vehicle over uneven terrain, which is a computationally expensive challenge. |
Mitash, C; Bekris, K; Boularias, A IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, Canada, 2017. @conference{Mitash:2017aa, title = {A Self-Supervised Learning System for Object Detection Using Physics Simulation and Multi-View Pose Estimation}, author = {C Mitash and K Bekris and A Boularias}, url = {https://www.cs.rutgers.edu/~kb572/pubs/physics_object_detection.pdf}, year = {2017}, date = {2017-09-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, address = {Vancouver, Canada}, abstract = {Impressive progress has been achieved in object detection with the use of deep learning. Nevertheless, such tools typically require a large amount of training data and significant manual effort for labeling objects. This limits their applicability in robotics, where it is necessary to scale solutions to a large number of objects and a variety of conditions. The present work proposes a fully autonomous process to train a Convolutional Neural Network (CNNs) for object detection and pose estimation in robotic setups. The application involves detection of objects placed in a clutter and in tight environments, such as a shelf. In particular, given access to 3D object models, several aspects of the environment are simulated and the models are placed in physically realistic poses with respect to their environment to generate a labeled synthetic dataset. To further improve object detection, the network self-trains over real images that are labeled using a robust multi-view pose estimation process. The proposed training process is evaluated on several existing datasets and on a dataset that we collected with a Motoman robotic manipulator. Results show that the proposed process outperforms popular training processes relying on synthetic data generation and manual annotation.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Impressive progress has been achieved in object detection with the use of deep learning. Nevertheless, such tools typically require a large amount of training data and significant manual effort for labeling objects. This limits their applicability in robotics, where it is necessary to scale solutions to a large number of objects and a variety of conditions. The present work proposes a fully autonomous process to train a Convolutional Neural Network (CNNs) for object detection and pose estimation in robotic setups. The application involves detection of objects placed in a clutter and in tight environments, such as a shelf. In particular, given access to 3D object models, several aspects of the environment are simulated and the models are placed in physically realistic poses with respect to their environment to generate a labeled synthetic dataset. To further improve object detection, the network self-trains over real images that are labeled using a robust multi-view pose estimation process. The proposed training process is evaluated on several existing datasets and on a dataset that we collected with a Motoman robotic manipulator. Results show that the proposed process outperforms popular training processes relying on synthetic data generation and manual annotation. |
Azizi, V; Kimmel, A; Bekris, K; Kapadia, M Geometric Reachability Analysis for Grasp Planning in Cluttered Scenes for Varying End-Effectors Conference China, 2017. @conference{Azizi:2017aa, title = {Geometric Reachability Analysis for Grasp Planning in Cluttered Scenes for Varying End-Effectors}, author = {V Azizi and A Kimmel and K Bekris and M Kapadia}, url = {https://www.cs.rutgers.edu/~kb572/pubs/grasping_planning_precision.pdf}, year = {2017}, date = {2017-08-01}, journal = {IEEE International Conference on Automation Science and Engineering (CASE)}, address = {China}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Han, S; Stiffler, N; Krontiris, A; Bekris, K; Yu, J High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods Conference Robotics: Science and Systems (RSS), [Best Student Paper Award Finalist] [Best Student Paper Award Finalist], Cambridge, MA, 2017. @conference{172, title = {High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods}, author = {S Han and N Stiffler and A Krontiris and K Bekris and J Yu}, url = {https://www.roboticsproceedings.org/rss13/p51.pdf}, year = {2017}, date = {2017-07-01}, booktitle = {Robotics: Science and Systems (RSS)}, publisher = {[Best Student Paper Award Finalist]}, address = {Cambridge, MA}, organization = {[Best Student Paper Award Finalist]}, abstract = {This paper studies the underlying combinatorial structure of a class of object rearrangement problems that appear frequently in applications. This class considers multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them with overhand grasps and perform pick-and-place operations to rearrange them. The paper considers both the case where the start and goal object poses overlap, and where they do not. For overlapping poses, the primary objective is to minimize the number of pick-and-place actions and then to minimize the distance traveled by the end-effector. For the non-overlapping case, the objective is solely to minimize the end-effector distance. While this class of problems does not involve all the complexities of general rearrangement, it remains a computationally hard challenge for both cases. This is shown by reducing well understood combinatorial challenges that are hard to these rearrangement problems. The benefit of this reduction is that there are well studied algorithms for solving the combinatorial challenges. These algorithms can be very efficient in practice despite the hardness results. The paper builds on top of these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problem. Experimental evaluation shows that the proposed pipeline achieves high-quality paths in terms of the optimization objective(s) and exhibits highly desirable scalability as the number of objects increases in both overlapping and non-overlapping setups.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper studies the underlying combinatorial structure of a class of object rearrangement problems that appear frequently in applications. This class considers multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them with overhand grasps and perform pick-and-place operations to rearrange them. The paper considers both the case where the start and goal object poses overlap, and where they do not. For overlapping poses, the primary objective is to minimize the number of pick-and-place actions and then to minimize the distance traveled by the end-effector. For the non-overlapping case, the objective is solely to minimize the end-effector distance. While this class of problems does not involve all the complexities of general rearrangement, it remains a computationally hard challenge for both cases. This is shown by reducing well understood combinatorial challenges that are hard to these rearrangement problems. The benefit of this reduction is that there are well studied algorithms for solving the combinatorial challenges. These algorithms can be very efficient in practice despite the hardness results. The paper builds on top of these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problem. Experimental evaluation shows that the proposed pipeline achieves high-quality paths in terms of the optimization objective(s) and exhibits highly desirable scalability as the number of objects increases in both overlapping and non-overlapping setups. |
2016 |
Kimmel, A; Bekris, K Scheduling Pick-and-Place Tasks for Dual-Arm Manipulators Using Incremental Search on Coordination Diagrams Journal Article 2016. @article{Kimmel:2016aa, title = {Scheduling Pick-and-Place Tasks for Dual-Arm Manipulators Using Incremental Search on Coordination Diagrams}, author = {A Kimmel and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/kimmel_schedule.pdf}, year = {2016}, date = {2016-06-01}, booktitle = {ICAPS workshop on planning and robotics (PlanRob)}, address = {London, UK}, abstract = {A premise of dual-arm robots is increased efficiency relative to single-arm counterparts in manipulation challenges. Nevertheless, moving two high-dimensional arms simultaneously in the same space is challenging and care must be taken so that collisions are avoided. Given trajectories for two arms to pick two objects, velocity tuning over a coordination diagram can resolve collisions. When multiple objects need to be moved, a scheduling challenge also arises. It involves finding the order with which objects should be manipulated. This paper considers two ways to approach this combination of scheduling and coordination challenges: (i) a ``batch'' approach, where an ordering of objects is selected first; for the given ordering, velocity tuning is performed over a matrix of coordination diagrams that considers all pairs of pick-and-place trajectories; and (ii) an incremental approach, where the ordering of objects is discovered on the fly given the subset of coordination diagrams that arise depending on which object one of the arms is currently manipulating. Simulated experiments for a Baxter robot show that both methods return significantly more efficient trajectories relative to the naive ``round-robin'' schedule, where only one arm moves at a time. Furthermore, the incremental approach is computationally faster, it implicitly provides a good schedule for picking objects and can be used effectively when objects appear dynamically.}, keywords = {}, pubstate = {published}, tppubtype = {article} } A premise of dual-arm robots is increased efficiency relative to single-arm counterparts in manipulation challenges. Nevertheless, moving two high-dimensional arms simultaneously in the same space is challenging and care must be taken so that collisions are avoided. Given trajectories for two arms to pick two objects, velocity tuning over a coordination diagram can resolve collisions. When multiple objects need to be moved, a scheduling challenge also arises. It involves finding the order with which objects should be manipulated. This paper considers two ways to approach this combination of scheduling and coordination challenges: (i) a ``batch'' approach, where an ordering of objects is selected first; for the given ordering, velocity tuning is performed over a matrix of coordination diagrams that considers all pairs of pick-and-place trajectories; and (ii) an incremental approach, where the ordering of objects is discovered on the fly given the subset of coordination diagrams that arise depending on which object one of the arms is currently manipulating. Simulated experiments for a Baxter robot show that both methods return significantly more efficient trajectories relative to the naive ``round-robin'' schedule, where only one arm moves at a time. Furthermore, the incremental approach is computationally faster, it implicitly provides a good schedule for picking objects and can be used effectively when objects appear dynamically. |
Littlefield, Z; Caluwaerts, K; Bruce, J; SunSpiral, V; Bekris, K Integrating Simulated Tensegrity Models with Efficient Motion Planning for Planetary Navigation Conference International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS 2016), Beijing, China, 2016. @conference{Littlefield:2016ab, title = {Integrating Simulated Tensegrity Models with Efficient Motion Planning for Planetary Navigation}, author = {Z Littlefield and K Caluwaerts and J Bruce and V SunSpiral and K Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/isairas_littlefield.pdf}, year = {2016}, date = {2016-06-01}, booktitle = {International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS 2016)}, address = {Beijing, China}, abstract = {Tensegrity-based robots use compression elements and tension cables to create lightweight structures that can reconfigure their shape. These characteristics are especially suited for planetary exploration, including for hard to traverse areas, such as lava tubes. While these capabilities are desirable for transporting these robots beyond Earth as well as reducing material costs, they complicate the control process. With such dynamic and reconfiguring parts, both simulating the motions of the tensegrity robot and planning future motions become challenging. New simulation tools for tensegrity rovers and state-of-the-art planning algorithms have been recently developed which can help to address these challenges, but have yet to used in tandem. This work integrates a recent sampling-based motion planner, which has been shown to converge to asymptotically optimal solutions even for systems with dynamics, with a novel tensegrity rover simulation tool, which has been verified in terms of accuracy against a hardware prototype. This paper shows that it is possible to get complex, long-duration trajectories for planetary navigation through this integration. At the same time, this integration is computationally demanding which motivated a parallel implementation of the proposed integration. With the parallel implementation, it is possible to observe improving path quality as computation time increases. This framework allows the consideration of planning under uncertainty to compute robust solutions, which is even more computationally demanding.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Tensegrity-based robots use compression elements and tension cables to create lightweight structures that can reconfigure their shape. These characteristics are especially suited for planetary exploration, including for hard to traverse areas, such as lava tubes. While these capabilities are desirable for transporting these robots beyond Earth as well as reducing material costs, they complicate the control process. With such dynamic and reconfiguring parts, both simulating the motions of the tensegrity robot and planning future motions become challenging. New simulation tools for tensegrity rovers and state-of-the-art planning algorithms have been recently developed which can help to address these challenges, but have yet to used in tandem. This work integrates a recent sampling-based motion planner, which has been shown to converge to asymptotically optimal solutions even for systems with dynamics, with a novel tensegrity rover simulation tool, which has been verified in terms of accuracy against a hardware prototype. This paper shows that it is possible to get complex, long-duration trajectories for planetary navigation through this integration. At the same time, this integration is computationally demanding which motivated a parallel implementation of the proposed integration. With the parallel implementation, it is possible to observe improving path quality as computation time increases. This framework allows the consideration of planning under uncertainty to compute robust solutions, which is even more computationally demanding. |
Krontiris, A; Bekris, K International Conference on Robotics and Automation (ICRA), Stockholm, Sweden, 2016. @conference{Krontiris:2016ab, title = {Efficiently Solving General Rearrangement Tasks: A Fast Extension Primitive for an Incremental Sampling-Based Planner}, author = {A Krontiris and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/fast_object_rearrangement.pdf}, year = {2016}, date = {2016-05-01}, booktitle = {International Conference on Robotics and Automation (ICRA)}, address = {Stockholm, Sweden}, abstract = {Manipulating movable obstacles is a hard problem that involves searching high-dimensional configuration spaces. A milestone method for this problem by Stilman et al. was able to compute solutions for monotone instances. These are problems where every object needs to be transferred at most once to achieve a desired arrangement of all objects. The method uses backtracking search to find the order with which objects should be moved in the environment. This paper first proposes an approximate but significantly faster alternative for monotone rearrangement instances. The method defines a dependency graph between objects given the minimum constraint removal paths (Minimum Constraint Removal) to transfer each object to its target. From this graph it is possible to discover the order of moving the objects by performing topological sorting without the need for backtracking search. The approximation arises from the limitation to consider only the Minimum Constraint Removal paths for moving the objects. Such paths, however, minimize the number of conflicts between the objects. To solve non-monotone instances, this primitive is incorporated in a higher-level incremental search algorithm for general rearrangement planning, that operates similar to Bi-RRT. Given a start and a goal arrangement of objects, tree structures of reachable new arrangements are generated by using the primitive as an expansion procedure. The integrated solution achieves probabilistic completeness for the general non-monotone case and based on simulated experiments it achieves very good success ratios, solution times and path quality relative to all the alternatives considered.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Manipulating movable obstacles is a hard problem that involves searching high-dimensional configuration spaces. A milestone method for this problem by Stilman et al. was able to compute solutions for monotone instances. These are problems where every object needs to be transferred at most once to achieve a desired arrangement of all objects. The method uses backtracking search to find the order with which objects should be moved in the environment. This paper first proposes an approximate but significantly faster alternative for monotone rearrangement instances. The method defines a dependency graph between objects given the minimum constraint removal paths (Minimum Constraint Removal) to transfer each object to its target. From this graph it is possible to discover the order of moving the objects by performing topological sorting without the need for backtracking search. The approximation arises from the limitation to consider only the Minimum Constraint Removal paths for moving the objects. Such paths, however, minimize the number of conflicts between the objects. To solve non-monotone instances, this primitive is incorporated in a higher-level incremental search algorithm for general rearrangement planning, that operates similar to Bi-RRT. Given a start and a goal arrangement of objects, tree structures of reachable new arrangements are generated by using the primitive as an expansion procedure. The integrated solution achieves probabilistic completeness for the general non-monotone case and based on simulated experiments it achieves very good success ratios, solution times and path quality relative to all the alternatives considered. |
Li, Y; Littlefield, Z; Bekris, K Asymptotically Optimal Sampling-Based Kinodynamic Planning Journal Article International Journal of Robotics Research (IJRR), 35 , pp. 528β564, 2016. @article{Li:2016aa, title = {Asymptotically Optimal Sampling-Based Kinodynamic Planning}, author = {Y Li and Z Littlefield and K Bekris}, url = {http://arxiv.org/abs/1407.2896}, year = {2016}, date = {2016-04-01}, journal = {International Journal of Robotics Research (IJRR)}, volume = {35}, pages = {528--564}, abstract = {Sampling-based algorithms are viewed as practical solutions for high-dimensional motion planning. Recent progress has taken advantage of random geometric graph theory to show how asymptotic optimality can also be achieved with these methods. Achieving this desirable property for systems with dynamics requires solving a two-point boundary value problem (BVP) in the state space of the underlying dynamical system. It is difficult, however, if not impractical, to generate a BVP solver for a variety of important dynamical models of robots or physically simulated ones. Thus, an open challenge was whether it was even possible to achieve optimality guarantees when planning for systems without access to a BVP solver. This work resolves the above question and describes how to achieve asymptotic optimality for kinodynamic planning using incremental sampling-based planners by introducing a new rigorous framework. Two new methods, Stable Sparse-RRT (SST) and SST*, result from this analysis, which are asymptotically near-optimal and optimal, respectively. The techniques are shown to converge fast to high-quality paths, while they maintain only a sparse set of samples, which makes them computationally efficient. The good performance of the planners is confirmed by experimental results using dynamical systems benchmarks, as well as physically simulated robots.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Sampling-based algorithms are viewed as practical solutions for high-dimensional motion planning. Recent progress has taken advantage of random geometric graph theory to show how asymptotic optimality can also be achieved with these methods. Achieving this desirable property for systems with dynamics requires solving a two-point boundary value problem (BVP) in the state space of the underlying dynamical system. It is difficult, however, if not impractical, to generate a BVP solver for a variety of important dynamical models of robots or physically simulated ones. Thus, an open challenge was whether it was even possible to achieve optimality guarantees when planning for systems without access to a BVP solver. This work resolves the above question and describes how to achieve asymptotic optimality for kinodynamic planning using incremental sampling-based planners by introducing a new rigorous framework. Two new methods, Stable Sparse-RRT (SST) and SST*, result from this analysis, which are asymptotically near-optimal and optimal, respectively. The techniques are shown to converge fast to high-quality paths, while they maintain only a sparse set of samples, which makes them computationally efficient. The good performance of the planners is confirmed by experimental results using dynamical systems benchmarks, as well as physically simulated robots. |
2015 |
Dobson, A; Bekris, K Planning Representations and Algorithms for Prehensile Multi-Arm Manipulation Conference IEEE/RSJ International Conference on Intelligent Robots and Systems, Hamburg, Germany, 2015. @conference{Dobson:2015ab, title = {Planning Representations and Algorithms for Prehensile Multi-Arm Manipulation}, author = {A Dobson and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Dobson_Bekris_multi_arm_iros15.pdf}, year = {2015}, date = {2015-09-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, address = {Hamburg, Germany}, abstract = {This paper describes the topology of general multi-arm prehensile manipulation by extending work on the single and dual-arm cases. Reasonable assumptions are applied to reduce the number of manipulation modes, which results in an explicit graphical representation for multi-arm manipulation that is computationally manageable to store and search for solution paths. In this context, it is also possible to take advantage of preprocessing steps to significantly speed up online query resolution. The approach is evaluated in simulation for multiple arms showing it is possible to quickly compute multi-arm manipulation paths of high-quality on the fly.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper describes the topology of general multi-arm prehensile manipulation by extending work on the single and dual-arm cases. Reasonable assumptions are applied to reduce the number of manipulation modes, which results in an explicit graphical representation for multi-arm manipulation that is computationally manageable to store and search for solution paths. In this context, it is also possible to take advantage of preprocessing steps to significantly speed up online query resolution. The approach is evaluated in simulation for multiple arms showing it is possible to quickly compute multi-arm manipulation paths of high-quality on the fly. |
Krontiris, A; Bekris, K Dealing with Difficult Instances of Object Rearrangement Conference Robotics: Science and Systems (RSS), 1123 , [Best Paper &amp; Best Student Paper Award Finalists] [Best Paper &amp; Best Student Paper Award Finalists], Rome, Italy, 2015. @conference{Krontiris:2015ab, title = {Dealing with Difficult Instances of Object Rearrangement}, author = {A Krontiris and K Bekris}, url = {https://people.cs.rutgers.edu/~kb572/pubs/Krontiris_Bekris_rearrangement_RSS2015.pdf}, year = {2015}, date = {2015-07-01}, booktitle = {Robotics: Science and Systems (RSS)}, volume = {1123}, publisher = {[Best Paper &amp; Best Student Paper Award Finalists]}, address = {Rome, Italy}, organization = {[Best Paper &amp; Best Student Paper Award Finalists]}, abstract = {An important skill for robots is the effective rearrangement of multiple objects so as to deal with clutter in human spaces. This paper proposes a simple but general primitive for rearranging multiple objects and its use in task planning frameworks. Rearrangement is a challenging problem as it involves combinatorially large, continuous C-spaces for multiple movable bodies and with kinematic constraints. This work starts by reviewing an existing search-based approach, which quickly computes solutions for monotone challenges, i.e., when objects need to be grasped only once so as to be rearranged. This work focuses on non-monotone challenges, as well as labeled problems, which some of the related efforts do not address. The first contribution is the extension of the monotone solution to a method that addresses a subset of non-monotone challenges. Then, this work proposes the use of the resulting non-monotone solver as a local planner in the context of a higher-level task planner that searches the space of object placements and for which stronger guarantees can be provided. The paper aims to emphasize the benefit of using more powerful motion primitives in the context of task planning for object rearrangement. Experiments in simulation using a model of a Baxter robot arm show the capability of solving difficult instances of rearrangement problems and evaluate the methods in terms of success ratio, computational requirements, scalability and path quality.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } An important skill for robots is the effective rearrangement of multiple objects so as to deal with clutter in human spaces. This paper proposes a simple but general primitive for rearranging multiple objects and its use in task planning frameworks. Rearrangement is a challenging problem as it involves combinatorially large, continuous C-spaces for multiple movable bodies and with kinematic constraints. This work starts by reviewing an existing search-based approach, which quickly computes solutions for monotone challenges, i.e., when objects need to be grasped only once so as to be rearranged. This work focuses on non-monotone challenges, as well as labeled problems, which some of the related efforts do not address. The first contribution is the extension of the monotone solution to a method that addresses a subset of non-monotone challenges. Then, this work proposes the use of the resulting non-monotone solver as a local planner in the context of a higher-level task planner that searches the space of object placements and for which stronger guarantees can be provided. The paper aims to emphasize the benefit of using more powerful motion primitives in the context of task planning for object rearrangement. Experiments in simulation using a model of a Baxter robot arm show the capability of solving difficult instances of rearrangement problems and evaluate the methods in terms of success ratio, computational requirements, scalability and path quality. |