Co-robots Dynamics Human robot interaction Learning Legible paths Manipulation Manipulator Multi-Robot Planning Pose Estimation Rearrangement Robot Perception simulation Sociotechnological Systems tensegrity Topology
2020 |
Bekris, K E; Shome, R Asymptotically Optimal Sampling-based Planners Book Chapter Encyclopedia of Robotics, 2020. Abstract | Links | BibTeX | Tags: @inbook{219, title = {Asymptotically Optimal Sampling-based Planners}, author = {K E 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. |
2019 |
Kimmel, A; Shome, R; Bekris, K E Anytime Motion Planning for Prehensile Manipulation in Dense Clutter Journal Article Advanced Robotics, 2019. Abstract | Links | BibTeX | Tags: @article{217, title = {Anytime Motion Planning for Prehensile Manipulation in Dense Clutter}, author = {A Kimmel and R Shome and K E Bekris}, url = {https://www.rahulsho.me/papers/ar_gmp.pdf}, year = {2019}, date = {2019-11-17}, 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. |
Kimmel, A; Sintov, A; Tan, J; Wen, B; Boularias, A; Bekris, K E Belief-Space Planning using Learned Models with Application to Underactuated Hands Conference International Symposium on Robotics Research (ISRR), Hanoi, Vietnam, 2019. Abstract | Links | BibTeX | Tags: @conference{213, 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 E 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. |
Mitash, C; Wen, B; Bekris, K E; Boularias, A Scene-level Pose Estimation for Multiple Instances of Densely Packed Objects Conference Conference on Robot Learning (CoRL), Osaka, Japan, 2019. Abstract | Links | BibTeX | Tags: @conference{214, title = {Scene-level Pose Estimation for Multiple Instances of Densely Packed Objects}, author = {C Mitash and B Wen and K E Bekris and A Boularias}, url = {https://arxiv.org/pdf/1910.04953.pdf}, year = {2019}, date = {2019-10-01}, booktitle = {Conference on Robot Learning (CoRL)}, address = {Osaka, Japan}, abstract = {This paper introduces key machine learning operations that allow the realization of robust, joint 6D pose estimation of multiple instances of objects either densely packed or in unstructured piles from RGB-D data. The first objective is to learn semantic and instance-boundary detectors without manual labeling. An adversarial training framework in conjunction with physics-based simulation is used to achieve detectors that behave similarly in synthetic and real data. Given the stochastic output of such detectors, candidates for object poses are sampled. The second objective is to automatically learn a single score for each pose candidate that represents its quality in terms of explaining the entire scene via a gradient boosted tree. The proposed method uses features derived from surface and boundary alignment between the observed scene and the object model placed at hypothesized poses. Scene-level, multi-instance pose estimation is then achieved by an integer linear programming process that selects hypotheses that maximize the sum of the learned individual scores, while respecting constraints, such as avoiding collisions. To evaluate this method, a dataset of densely packed objects with challenging setups for state-of-the-art approaches is collected. Experiments on this dataset and a public one show that the method significantly outperforms alternatives in terms of 6D pose accuracy while trained only with synthetic datasets.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper introduces key machine learning operations that allow the realization of robust, joint 6D pose estimation of multiple instances of objects either densely packed or in unstructured piles from RGB-D data. The first objective is to learn semantic and instance-boundary detectors without manual labeling. An adversarial training framework in conjunction with physics-based simulation is used to achieve detectors that behave similarly in synthetic and real data. Given the stochastic output of such detectors, candidates for object poses are sampled. The second objective is to automatically learn a single score for each pose candidate that represents its quality in terms of explaining the entire scene via a gradient boosted tree. The proposed method uses features derived from surface and boundary alignment between the observed scene and the object model placed at hypothesized poses. Scene-level, multi-instance pose estimation is then achieved by an integer linear programming process that selects hypotheses that maximize the sum of the learned individual scores, while respecting constraints, such as avoiding collisions. To evaluate this method, a dataset of densely packed objects with challenging setups for state-of-the-art approaches is collected. Experiments on this dataset and a public one show that the method significantly outperforms alternatives in terms of 6D pose accuracy while trained only with synthetic datasets. |
Sivaramakrishnan, A; Littlefield, Z; Bekris, K E Towards Learning Efficient Maneuver Sets for Kinodynamic Motion Planning Technical Report PlanRob 2019 Workshop of ICAPS 2019 2019. Abstract | Links | BibTeX | Tags: @techreport{211, title = {Towards Learning Efficient Maneuver Sets for Kinodynamic Motion Planning}, author = {A Sivaramakrishnan and Z Littlefield and K E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/Learning_Maneuver_Sets_PlanRob2019.pdf}, year = {2019}, date = {2019-07-01}, institution = {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 E 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. Abstract | Links | BibTeX | Tags: @conference{212, title = {Anytime Multi-arm Task and Motion Planning for Pick-and-Place of Individual Objects via Handoffs}, author = {R Shome and K E 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. |
Sintov, A; Morgan, A; Kimmel, A; Dollar, A; Bekris, K E; Boularias, A Learning a State Transition Model of an Underactuated Adaptive Hand Journal Article IEEE Robotics and Automation Letters (RA-L) (also appearing at IEEE ICRA 2019), 2019. Abstract | Links | BibTeX | Tags: @article{205, title = {Learning a State Transition Model of an Underactuated Adaptive Hand}, author = {A Sintov and A Morgan and A Kimmel and A Dollar and K E Bekris and A Boularias}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Learning_a_State_Transition_Model.pdf}, year = {2019}, date = {2019-05-01}, journal = {IEEE Robotics and Automation Letters (RA-L) (also appearing at IEEE ICRA 2019)}, abstract = {Fully-actuated, multi-fingered robotic hands are often expensive and fragile. Low-cost, under-actuated hands are appealing but present challenges due to the lack of analytical models. This paper aims to learn a stochastic version of such models automatically from data with minimum user effort. The focus is on identifying the dominant, sensible features required to express hand state transitions given quasi-static motions, thereby enabling the learning of a probabilistic transition model from recorded trajectories. Experiments both with Gaussian Processes (GP) and Neural Network models are included for analysis and evaluation. The metric for local GP regression is obtained with a manifold learning approach, known as "Diffusion Maps", to uncover the lower-dimensional subspace in which the data lies and provide a geodesic metric. Results show that using Diffusion Maps with a feature space composed of the object position, actuator angles, and actuator loads, sufficiently expresses the hand-object system "configuration and can provide accurate enough predictions for a relatively long horizon. To the best of the authorstextquoteright knowledge, this is the first learned transition model for such underactuated hands that achieves this level of predictability. Notably, the same feature space implicitly embeds the size of the manipulated object and can generalize to new objects of varying sizes. Furthermore, the learned model can identify states that are on the verge of failure and which should be avoided during manipulation. The usefulness of the model is also demonstrated by integrating it with closed-loop control to successfully and safely complete manipulation tasks.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Fully-actuated, multi-fingered robotic hands are often expensive and fragile. Low-cost, under-actuated hands are appealing but present challenges due to the lack of analytical models. This paper aims to learn a stochastic version of such models automatically from data with minimum user effort. The focus is on identifying the dominant, sensible features required to express hand state transitions given quasi-static motions, thereby enabling the learning of a probabilistic transition model from recorded trajectories. Experiments both with Gaussian Processes (GP) and Neural Network models are included for analysis and evaluation. The metric for local GP regression is obtained with a manifold learning approach, known as "Diffusion Maps", to uncover the lower-dimensional subspace in which the data lies and provide a geodesic metric. Results show that using Diffusion Maps with a feature space composed of the object position, actuator angles, and actuator loads, sufficiently expresses the hand-object system "configuration and can provide accurate enough predictions for a relatively long horizon. To the best of the authorstextquoteright knowledge, this is the first learned transition model for such underactuated hands that achieves this level of predictability. Notably, the same feature space implicitly embeds the size of the manipulated object and can generalize to new objects of varying sizes. Furthermore, the learned model can identify states that are on the verge of failure and which should be avoided during manipulation. The usefulness of the model is also demonstrated by integrating it with closed-loop control to successfully and safely complete manipulation tasks. |
Shome, R; Tang, W N; Song, C; Mitash, C; Kourtev, C; Yu, J; Boularias, A; Bekris, K E Towards Robust Product Packing with a Minimalistic End-Effector Conference IEEE International Conference on Robotics and Automation (ICRA), 2019, (Nomination for Best Paper Award in Automation). Abstract | Links | BibTeX | Tags: Manipulation, Robot Perception @conference{207, title = {Towards Robust Product Packing with a Minimalistic End-Effector}, author = {R Shome and W N Tang and C Song and C Mitash and C Kourtev and J Yu and A Boularias and K E Bekris}, url = {http://robotpacking.org/}, year = {2019}, date = {2019-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, abstract = {Advances in sensor technologies, object detection algorithms, planning frameworks and hardware designs have motivated the deployment of robots in warehouse automation. A variety of such applications, like order fulfillment or packing tasks, require picking objects from unstructured piles and carefully arranging them in bins or containers. Desirable solutions need to be low-cost, easily deployable and controllable, making minimalistic hardware choices desirable. The challenge in designing an effective solution to this problem relates to appropriately integrating multiple components, so as to achieve a robust pipeline that minimizes failure conditions. The current work proposes a complete pipeline for solving such packing tasks, given access only to RGB-D data and a single robot arm with a minimalistic, vacuum-based end-effector. To achieve the desired level of robustness, three key manipulation primitives are identified, which take advantage of the environment and simple operations to successfully pack multiple cubic objects. The overall approach is demonstrated to be robust to execution and perception errors. The impact of each manipulation primitive is evaluated by considering different versions of the proposed pipeline that incrementally introduce reasoning about object poses and corrective manipulation actions.}, note = {Nomination for Best Paper Award in Automation}, keywords = {Manipulation, Robot Perception}, pubstate = {published}, tppubtype = {conference} } Advances in sensor technologies, object detection algorithms, planning frameworks and hardware designs have motivated the deployment of robots in warehouse automation. A variety of such applications, like order fulfillment or packing tasks, require picking objects from unstructured piles and carefully arranging them in bins or containers. Desirable solutions need to be low-cost, easily deployable and controllable, making minimalistic hardware choices desirable. The challenge in designing an effective solution to this problem relates to appropriately integrating multiple components, so as to achieve a robust pipeline that minimizes failure conditions. The current work proposes a complete pipeline for solving such packing tasks, given access only to RGB-D data and a single robot arm with a minimalistic, vacuum-based end-effector. To achieve the desired level of robustness, three key manipulation primitives are identified, which take advantage of the environment and simple operations to successfully pack multiple cubic objects. The overall approach is demonstrated to be robust to execution and perception errors. The impact of each manipulation primitive is evaluated by considering different versions of the proposed pipeline that incrementally introduce reasoning about object poses and corrective manipulation actions. |
Feld-Cook, E; Shome, R; Zaleski, R; Mohan, K; Kourtev, C; Bekris, K E; Weiseil, C; Shin, J Exploring the Utility of Robots in Exposure Studies Journal Article Journal of Exposure Science and Environmental Epidemiology (JESEE), 2019. Abstract | Links | BibTeX | Tags: @article{215, title = {Exploring the Utility of Robots in Exposure Studies}, author = {E Feld-Cook and R Shome and R Zaleski and K Mohan and C Kourtev and K E Bekris and C Weiseil and J Shin}, url = {https://www.nature.com/articles/s41370-019-0190-x}, year = {2019}, date = {2019-01-01}, journal = {Journal of Exposure Science and Environmental Epidemiology (JESEE)}, abstract = {Advancements in robotic technology continue to help expand the use of robots in the workplace, research, and society. In this proof-of-concept study, a robotic platform was programmed to do a simple task, painting drywall, to help determine if robots are a plausible alternative to human subjects in exposure studies. For the exposure component, passive and active air samplers and direct-read monitors were placed by the robot to measure VOCs emitted from the paint and later compared to modeled estimates. A strong correlation of R2 = 0.85- 0.89 was found between increased paint used and increased total VOC air concentrations. Similar trends were observed for all painting trials for the direct read monitors with an overall low VOC air concentration (< 4 ppm), indicating a low exposure profile. Consistent results for the front (60.1 textpm 2.5 cm by 77.5 textpm 0.85 cm) and sides (60.1 textpm 2.5 cm by 60.1 textpm 2.9 cm) painted by the robot, the resulting exposure, and the amount of paint used per trial suggest that using a robot to perform an exposure study was successful. This study demonstrated how robots, compared to human subjects, are quicker and reliable way to perform exposure studies.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Advancements in robotic technology continue to help expand the use of robots in the workplace, research, and society. In this proof-of-concept study, a robotic platform was programmed to do a simple task, painting drywall, to help determine if robots are a plausible alternative to human subjects in exposure studies. For the exposure component, passive and active air samplers and direct-read monitors were placed by the robot to measure VOCs emitted from the paint and later compared to modeled estimates. A strong correlation of R2 = 0.85- 0.89 was found between increased paint used and increased total VOC air concentrations. Similar trends were observed for all painting trials for the direct read monitors with an overall low VOC air concentration (< 4 ppm), indicating a low exposure profile. Consistent results for the front (60.1 textpm 2.5 cm by 77.5 textpm 0.85 cm) and sides (60.1 textpm 2.5 cm by 60.1 textpm 2.9 cm) painted by the robot, the resulting exposure, and the amount of paint used per trial suggest that using a robot to perform an exposure study was successful. This study demonstrated how robots, compared to human subjects, are quicker and reliable way to perform exposure studies. |
Ricks, B; Dobson, A; Krontiris, A; Bekris, K E; Kapadia, M; Roberts, F Generation of Crowd Arrival and Destination Locations/Times in Complex Transit Facilities Journal Article The Visual Computer Journal, 2019. Abstract | Links | BibTeX | Tags: @article{216, title = {Generation of Crowd Arrival and Destination Locations/Times in Complex Transit Facilities}, author = {B Ricks and A Dobson and A Krontiris and K E Bekris and M Kapadia and F Roberts}, url = {https://rdcu.be/bUBid}, year = {2019}, date = {2019-01-01}, journal = {The Visual Computer Journal}, abstract = {In order to simulate virtual agents in the replica of a real facility across a long time span, a crowd simulation engine needs a list of agent arrival and destination locations and times that reflect those seen in the actual facility. Working together with a major metropolitan transportation authority, we pro- pose a specification that can be used to procedurally generate this information. This specification is both uniquely compact and expressive—compact enough to mirror the mental model of building managers and ex- pressive enough to handle the wide variety of crowds seen in real urban environments. We also propose a procedural algorithm for generating tens of thousands of high-level agent paths from this specification. This algorithm allows our specification to be used with tradi- tional crowd simulation obstacle avoidance algorithms while still maintaining the realism required for the com- plex, real-world simulations of a transit facility. Our evaluation with industry professionals shows that our approach is intuitive and provides controls at the right level of detail to be used in large facilities (200,000+ people/day).}, keywords = {}, pubstate = {published}, tppubtype = {article} } In order to simulate virtual agents in the replica of a real facility across a long time span, a crowd simulation engine needs a list of agent arrival and destination locations and times that reflect those seen in the actual facility. Working together with a major metropolitan transportation authority, we pro- pose a specification that can be used to procedurally generate this information. This specification is both uniquely compact and expressive—compact enough to mirror the mental model of building managers and ex- pressive enough to handle the wide variety of crowds seen in real urban environments. We also propose a procedural algorithm for generating tens of thousands of high-level agent paths from this specification. This algorithm allows our specification to be used with tradi- tional crowd simulation obstacle avoidance algorithms while still maintaining the realism required for the com- plex, real-world simulations of a transit facility. Our evaluation with industry professionals shows that our approach is intuitive and provides controls at the right level of detail to be used in large facilities (200,000+ people/day). |
Kleinbort, M; Solovey, K; Littlefield, Z; Bekris, K E; 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. Abstract | Links | BibTeX | Tags: @article{202, title = {Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation}, author = {M Kleinbort and K Solovey and Z Littlefield and K E 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. |
Surovik, D; Wang, K; Vespignani, M; Bruce, J; Bekris, K E Adaptive Tensegrity Locomotion: Controlling a Compliant Icosahedron with Symmetry-Reduced Reinforcement Learning Journal Article International Journal of Robotics Research (IJRR), 2019. Abstract | Links | BibTeX | Tags: @article{210, title = {Adaptive Tensegrity Locomotion: Controlling a Compliant Icosahedron with Symmetry-Reduced Reinforcement Learning}, author = {D Surovik and K Wang and M Vespignani and J Bruce and K E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/reinf_learning_tensegrity_locomotion.pdf}, year = {2019}, date = {2019-00-01}, journal = {International Journal of Robotics Research (IJRR)}, abstract = {Tensegrity robots, which are prototypical examples of hybrid soft-rigid robots, exhibit dynamical properties that provide ruggedness and adaptability. They also bring about, however, major challenges for locomotion control. Due to high dimensionality and the complex evolution of contact states, data-driven approaches are appropriate for producing viable feedback policies for tensegrities. Guided Policy Search (GPS), a sample-efficient hybrid framework for optimization and reinforcement learning, has previously been applied to generate periodic, axis-constrained locomotion by an icosahedral tensegrity on flat ground. Varying environments and tasks, however, create a need for more adaptive and general locomotion control that actively utilizes an expanded space of robot states. This implies significantly higher needs in terms of sample data and setup effort. This work mitigates such requirements by proposing a new GPS- based reinforcement learning pipeline, which exploits the vehicletextquoterights high degree of symmetry and appropriately learns contextual behaviors that are sustainable without periodicity. Newly achieved capabilities include axially-unconstrained rolling, rough terrain traversal, and rough incline ascent. These tasks are evaluated for a small variety of key model parameters in simulation and tested on the NASA hardware prototype, SUPERball. Results confirm the utility of symmetry exploitation and the adaptability of the vehicle. They also shed light on numerous strengths and limitations of the GPS framework for policy design and transfer to real hybrid soft-rigid robots.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Tensegrity robots, which are prototypical examples of hybrid soft-rigid robots, exhibit dynamical properties that provide ruggedness and adaptability. They also bring about, however, major challenges for locomotion control. Due to high dimensionality and the complex evolution of contact states, data-driven approaches are appropriate for producing viable feedback policies for tensegrities. Guided Policy Search (GPS), a sample-efficient hybrid framework for optimization and reinforcement learning, has previously been applied to generate periodic, axis-constrained locomotion by an icosahedral tensegrity on flat ground. Varying environments and tasks, however, create a need for more adaptive and general locomotion control that actively utilizes an expanded space of robot states. This implies significantly higher needs in terms of sample data and setup effort. This work mitigates such requirements by proposing a new GPS- based reinforcement learning pipeline, which exploits the vehicletextquoterights high degree of symmetry and appropriately learns contextual behaviors that are sustainable without periodicity. Newly achieved capabilities include axially-unconstrained rolling, rough terrain traversal, and rough incline ascent. These tasks are evaluated for a small variety of key model parameters in simulation and tested on the NASA hardware prototype, SUPERball. Results confirm the utility of symmetry exploitation and the adaptability of the vehicle. They also shed light on numerous strengths and limitations of the GPS framework for policy design and transfer to real hybrid soft-rigid robots. |
Littlefield, Z; Surovik, D; Vespignani, M; Bruce, J; Wang, W; Bekris, K E Kinodynamic Planning for Spherical Tensegrity Locomotion with Effective Gait Primitives Journal Article International Journal of Robotics Research (IJRR), 2019. Abstract | Links | BibTeX | Tags: @article{208, 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 E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/kinodynamic_tensegrity.pdf}, year = {2019}, date = {2019-00-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. |
Mitash, C; Boularias, A; Bekris, K E Physics-based Scene-level Reasoning for Object Pose Estimation in Clutter Journal Article International Journal of Robotics Research (IJRR), 2019. Abstract | Links | BibTeX | Tags: @article{209, title = {Physics-based Scene-level Reasoning for Object Pose Estimation in Clutter}, author = {C Mitash and A Boularias and K E Bekris}, url = {https://arxiv.org/pdf/1806.10457.pdf}, year = {2019}, date = {2019-00-01}, journal = {International Journal of Robotics Research (IJRR)}, abstract = {This paper focuses on vision-based pose estimation for multiple rigid objects placed in clutter, especially in cases involving occlusions and objects resting on each other. Progress has been achieved recently in object recognition given advancements in deep learning. Nevertheless, such tools typically require a large amount of training data and significant manual effort to label objects. This limits their applicability in robotics, where solutions must scale to a large number of objects and variety of conditions. Moreover, the combinatorial nature of the scenes that could arise from the placement of multiple objects is hard to capture in the training dataset. Thus, the learned models might not produce the desired level of precision required for tasks, such as robotic manipulation. This work proposes an autonomous process for pose estimation that spans from data generation, to scene-level reasoning and self-learning. In particular, the proposed framework first generates a labeled dataset for training a Convolutional Neural Network (CNN) for object detection in clutter. These detections are used to guide a scene-level optimization process, which considers the interactions between the different objects present in the clutter to output pose estimates of high precision. Furthermore, confident estimates are used to label online real images from multiple views and re-train the process in a self-learning pipeline. Experimental results indicate that this process is quickly able to identify in cluttered scenes physically-consistent object poses that are more precise than the ones found by reasoning over individual instances of objects. Furthermore, the quality of pose estimates increases over time given the self-learning process.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This paper focuses on vision-based pose estimation for multiple rigid objects placed in clutter, especially in cases involving occlusions and objects resting on each other. Progress has been achieved recently in object recognition given advancements in deep learning. Nevertheless, such tools typically require a large amount of training data and significant manual effort to label objects. This limits their applicability in robotics, where solutions must scale to a large number of objects and variety of conditions. Moreover, the combinatorial nature of the scenes that could arise from the placement of multiple objects is hard to capture in the training dataset. Thus, the learned models might not produce the desired level of precision required for tasks, such as robotic manipulation. This work proposes an autonomous process for pose estimation that spans from data generation, to scene-level reasoning and self-learning. In particular, the proposed framework first generates a labeled dataset for training a Convolutional Neural Network (CNN) for object detection in clutter. These detections are used to guide a scene-level optimization process, which considers the interactions between the different objects present in the clutter to output pose estimates of high precision. Furthermore, confident estimates are used to label online real images from multiple views and re-train the process in a self-learning pipeline. Experimental results indicate that this process is quickly able to identify in cluttered scenes physically-consistent object poses that are more precise than the ones found by reasoning over individual instances of objects. Furthermore, the quality of pose estimates increases over time given the self-learning process. |
2018 |
Shome, R; Solovey, K; Yu, J; Bekris, K E; 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. Abstract | Links | BibTeX | Tags: @conference{199, title = {Fast and High-Quality Dual-Arm Rearrangement in Synchronous, Monotone Tabletop Setups}, author = {R Shome and K Solovey and J Yu and K E 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. |
Surovik, D; Bruce, J; Wang, K; Vespignani, M; Bekris, K E Any-axis Tensegrity Rolling via Bootstrapped Learning and Symmetry Reduction Conference International Symposium on Experimental Robotics (ISER), Buenos Aires, Argentina, 2018. @conference{194, title = {Any-axis Tensegrity Rolling via Bootstrapped Learning and Symmetry Reduction}, author = {D Surovik and J Bruce and K Wang and M Vespignani and K E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/any_axis_tensegrity_rolling.pdf}, year = {2018}, date = {2018-11-01}, booktitle = {International Symposium on Experimental Robotics (ISER)}, address = {Buenos Aires, Argentina}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Kimmel, A; Shome, R; Littlefield, Z; Bekris, K E Fast, Anytime Motion Planning for Prehensile Manipulation in Clutter Conference 2018 IEEE-RAS 18th International Conference on Humanoid Robots (Humanoids 2018), Beijing, China, 2018. Abstract | Links | BibTeX | Tags: @conference{200, title = {Fast, Anytime Motion Planning for Prehensile Manipulation in Clutter}, author = {A Kimmel and R Shome and Z Littlefield and K E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/gmp.pdf}, year = {2018}, date = {2018-11-01}, booktitle = {2018 IEEE-RAS 18th International Conference on Humanoid Robots (Humanoids 2018)}, 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. |
Calli, B; Kimmel, A; Hang, K; Bekris, K E; Dollar, A Path Planning for Within-Hand Manipulation Over Learned Representations of Safe States Conference International Symposium on Experimental Robotics (ISER), Buenos Aires, Argentina, 2018. Abstract | Links | BibTeX | Tags: @conference{195, title = {Path Planning for Within-Hand Manipulation Over Learned Representations of Safe States}, author = {B Calli and A Kimmel and K Hang and K E Bekris and A Dollar}, url = {http://www.cs.rutgers.edu/~kb572/pubs/within_hand_planning_over_learning.pdf}, year = {2018}, date = {2018-11-01}, booktitle = {International Symposium on Experimental Robotics (ISER)}, address = {Buenos Aires, Argentina}, abstract = {This work proposes a framework for tracking a desired path of an object held by an adaptive hand via within-hand manipulation. Such underactuated hands are able to passively achieve stable contacts with objects. Combined with vision-based control and data-driven state estimation process, they can solve tasks without accurate hand-object models or multi-modal sensory feedback. In particular, a data-driven regression process is used here to estimate the probability of dropping the object for given manipulation states. Then, an optimization-based planner aims to track the desired path while avoiding states that are above a threshold probability of dropping the object. The optimized cost function, based on the principle of Dynamic-Time Warping (DTW), seeks to minimize the area between the desired and the followed path. By adapting the threshold for the probability of dropping the object, the framework can handle objects of different weights without retraining. Experiments involving writing letters with a marker, as well as tracing randomized paths, were conducted on the Yale Model T-42 hand. Results indicate that the framework successfully avoids undesirable states, while minimizing the proposed cost function, thereby producing object paths for within-hand manipulation that closely match the target ones.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This work proposes a framework for tracking a desired path of an object held by an adaptive hand via within-hand manipulation. Such underactuated hands are able to passively achieve stable contacts with objects. Combined with vision-based control and data-driven state estimation process, they can solve tasks without accurate hand-object models or multi-modal sensory feedback. In particular, a data-driven regression process is used here to estimate the probability of dropping the object for given manipulation states. Then, an optimization-based planner aims to track the desired path while avoiding states that are above a threshold probability of dropping the object. The optimized cost function, based on the principle of Dynamic-Time Warping (DTW), seeks to minimize the area between the desired and the followed path. By adapting the threshold for the probability of dropping the object, the framework can handle objects of different weights without retraining. Experiments involving writing letters with a marker, as well as tracing randomized paths, were conducted on the Yale Model T-42 hand. Results indicate that the framework successfully avoids undesirable states, while minimizing the proposed cost function, thereby producing object paths for within-hand manipulation that closely match the target ones. |
Littlefield, Z; Bekris, K E 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{197, title = {Efficient and Asymptotically Optimal Kinodynamic Motion Planning via Dominance-Informed Regions}, author = {Z Littlefield and K E 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}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Zhu, S; Surovik, D; Bekris, K E; Boularias, A Efficient Model Identification for Tensegrity Locomotion Conference IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Madrid, Spain, 2018. Abstract | Links | BibTeX | Tags: @conference{196, title = {Efficient Model Identification for Tensegrity Locomotion}, author = {S Zhu and D Surovik and K E Bekris and A Boularias}, url = {https://www.cs.rutgers.edu/~kb572/pubs/model_identification_tensegrity.pdf}, year = {2018}, date = {2018-10-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, address = {Madrid, Spain}, abstract = {This paper aims to identify in a practical manner unknown physical parameters, such as mechanical models of actuated robot links, which are critical in dynamical robotic tasks. Key features include the use of an off-the-shelf physics engine and the Bayesian optimization framework. The task being considered is locomotion with a high-dimensional, compliant Tensegrity robot. A key insight, in this case, is the need to project the space of models into an appropriate lower dimensional space for time efficiency. Comparisons with alternatives indicate that the proposed method can identify the parameters more accurately within the given time budget, which also results in more precise locomotion control.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper aims to identify in a practical manner unknown physical parameters, such as mechanical models of actuated robot links, which are critical in dynamical robotic tasks. Key features include the use of an off-the-shelf physics engine and the Bayesian optimization framework. The task being considered is locomotion with a high-dimensional, compliant Tensegrity robot. A key insight, in this case, is the need to project the space of models into an appropriate lower dimensional space for time efficiency. Comparisons with alternatives indicate that the proposed method can identify the parameters more accurately within the given time budget, which also results in more precise locomotion control. |
Mitash, C; Boularias, A; Bekris, K E Robust 6D Pose Estimation with Stochastic Congruent Sets Conference British Machine Vision (BMVC) conference, Newcastle, UK, 2018. @conference{198, title = {Robust 6D Pose Estimation with Stochastic Congruent Sets}, author = {C Mitash and A Boularias and K E Bekris}, url = {https://arxiv.org/abs/1805.06324}, year = {2018}, date = {2018-09-01}, booktitle = {British Machine Vision (BMVC) conference}, address = {Newcastle, UK}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Shuai, H; Stiffler, N; Krontiris, A; Bekris, K E; Yu, J Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps Journal Article International Journal of Robotics Research (IJRR), 2018. Abstract | Links | BibTeX | Tags: @article{193, title = {Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps}, author = {H Shuai and N Stiffler and A Krontiris and K E Bekris and J Yu}, url = {https://www.cs.rutgers.edu/~kb572/pubs/optimal_tabletop_rearrangement.pdf}, year = {2018}, date = {2018-07-01}, journal = {International Journal of Robotics Research (IJRR)}, abstract = {This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications. The problems involve multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them from above 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 travel distance of the end-effector. While such problems do not involve all the complexities of general rearrangement, they remain computationally hard in both cases. This is shown through reductions from well-understood, hard combinatorial challenges to these rearrangement problems. The reductions are also shown to hold in the reverse direction, which enables the convenient application on rearrangement of well studied algorithms. These algorithms can be very efficient in practice despite the hardness results. The paper builds on these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problems. Experimental evaluation, including hardware-based trials, shows that the proposed pipeline computes high-quality paths with regards to the optimization objectives. Furthermore, it exhibits highly desirable scalability as the number of objects increases in both the overlapping and non-overlapping setup.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications. The problems involve multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them from above 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 travel distance of the end-effector. While such problems do not involve all the complexities of general rearrangement, they remain computationally hard in both cases. This is shown through reductions from well-understood, hard combinatorial challenges to these rearrangement problems. The reductions are also shown to hold in the reverse direction, which enables the convenient application on rearrangement of well studied algorithms. These algorithms can be very efficient in practice despite the hardness results. The paper builds on these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problems. Experimental evaluation, including hardware-based trials, shows that the proposed pipeline computes high-quality paths with regards to the optimization objectives. Furthermore, it exhibits highly desirable scalability as the number of objects increases in both the overlapping and non-overlapping setup. |
Shuai, H; Stiffler, N; Bekris, K E; 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. Abstract | Links | BibTeX | Tags: @article{187, title = {Efficient, High-Quality Stack Rearrangement}, author = {H Shuai and N Stiffler and K E 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. |
Zhu, S; Kimmel, A; Bekris, K E; Boularias, A Fast Model Identification via Physics Engines for Data-Efficient Policy Search Conference International Joint Conference on Artificial Intelligence (IJCAI), Stockholm, Sweden, 2018. Abstract | Links | BibTeX | Tags: @conference{192, title = {Fast Model Identification via Physics Engines for Data-Efficient Policy Search}, author = {S Zhu and A Kimmel and K E Bekris and A Boularias}, url = {https://www.cs.rutgers.edu/~kb572/pubs/physics_model_id.pdf}, year = {2018}, date = {2018-07-01}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, address = {Stockholm, Sweden}, abstract = {This paper presents a practical approach for identifying unknown mechanical parameters, such as mass and friction models of manipulated rigid objects or actuated robotic links, in a succinct manner that aims to improve the performance of policy search algorithms. Key features of this approach are the use of off-the-shelf physics engines and the adaptation of a black-box Bayesian optimization framework for this purpose. The physics engine is used to reproduce in simulation experiments that are performed on a real robot, and the mechanical parameters of the simulated system are automatically fine-tuned so that the simulated trajectories match with the real ones. The optimized model is then used for learning a policy in simulation, before safely deploying it on the real robot. Given the well-known limitations of physics engines in modeling real-world objects, it is generally not possible to find a mechanical model that reproduces in simulation the real trajectories exactly. Moreover, there are many scenarios where a near-optimal policy can be found without having a perfect knowledge of the system. Therefore, searching for a perfect model may not be worth the computational effort in practice. The proposed approach aims then to identify a model that is good enough to approximate the value of a locally optimal policy with a certain confidence, instead of spending all the computational resources on searching for the most accurate model. Empirical evaluations, performed in simulation and on a real robotic manipulation task, show that model identification via physics engines can significantly boost the performance of policy search algorithms that are popular in robotics, such as TRPO, PoWER and PILCO, with no additional real-world data.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper presents a practical approach for identifying unknown mechanical parameters, such as mass and friction models of manipulated rigid objects or actuated robotic links, in a succinct manner that aims to improve the performance of policy search algorithms. Key features of this approach are the use of off-the-shelf physics engines and the adaptation of a black-box Bayesian optimization framework for this purpose. The physics engine is used to reproduce in simulation experiments that are performed on a real robot, and the mechanical parameters of the simulated system are automatically fine-tuned so that the simulated trajectories match with the real ones. The optimized model is then used for learning a policy in simulation, before safely deploying it on the real robot. Given the well-known limitations of physics engines in modeling real-world objects, it is generally not possible to find a mechanical model that reproduces in simulation the real trajectories exactly. Moreover, there are many scenarios where a near-optimal policy can be found without having a perfect knowledge of the system. Therefore, searching for a perfect model may not be worth the computational effort in practice. The proposed approach aims then to identify a model that is good enough to approximate the value of a locally optimal policy with a certain confidence, instead of spending all the computational resources on searching for the most accurate model. Empirical evaluations, performed in simulation and on a real robotic manipulation task, show that model identification via physics engines can significantly boost the performance of policy search algorithms that are popular in robotics, such as TRPO, PoWER and PILCO, with no additional real-world data. |
Rennie, C; Bekris, K E Discovering A Library of Rhythmic Gaits for Spherical Tensegrity Locomotion Conference IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia, 2018. @conference{188, title = {Discovering A Library of Rhythmic Gaits for Spherical Tensegrity Locomotion}, author = {C Rennie and K E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/gps_bo_svm_tensegrity.pdf}, year = {2018}, date = {2018-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Brisbane, Australia}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Mitash, C; Boularias, A; Bekris, K E Improving 6D Pose Estimation of Objects in Clutter via Physics-aware Monte Carlo Tree Search Conference IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia, 2018. @conference{189, title = {Improving 6D Pose Estimation of Objects in Clutter via Physics-aware Monte Carlo Tree Search}, author = {C Mitash and A Boularias and K E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/physics_mcts_pose_estimation.pdf}, year = {2018}, date = {2018-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Brisbane, Australia}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Surovik, D; Bekris, K E Symmetric Reduction of Tensegrity Rover Dynamics for Efficient Data-Driven Control Conference ASCE Earth and Space Conference, Symposium on "Tensegrity - Structural Concept and Applications", Cleveland, Ohio, 2018. Abstract | Links | BibTeX | Tags: @conference{186, title = {Symmetric Reduction of Tensegrity Rover Dynamics for Efficient Data-Driven Control}, author = {D Surovik and K E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/asce_sym.pdf}, year = {2018}, date = {2018-04-01}, booktitle = {ASCE Earth and Space Conference, Symposium on "Tensegrity - Structural Concept and Applications"}, address = {Cleveland, Ohio}, abstract = {Tensegrity robots consist of disconnected rods suspended within a network of length-actuated cables, which gives them a high degree of compliance and adaptability suitable for traversing rugged terrain. These vehicles, however, undergo complex contact dynamics that prevent the use of traditional control techniques based on mathematical analyses of equations of motion. Data-driven approaches are thus an appropriate choice for controller design, but are themselves hindered by the high number of degrees of freedom and correspondingly large state spaces. This paper presents a scheme for exploiting the 24th-order symmetry of an icosahedral tensegrity robot to vastly reduce the breadth of the controller input space without loss of information. Symmetric properties and state reduction operations are detailed and placed in the context of a data-driven control pipeline. Results are illustrated by comparing the input and output of a locomotive controller in both raw and symmetry-reduced dynamical spaces. The findings suggest a strong relief of the data requirements for training locomotive controllers.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Tensegrity robots consist of disconnected rods suspended within a network of length-actuated cables, which gives them a high degree of compliance and adaptability suitable for traversing rugged terrain. These vehicles, however, undergo complex contact dynamics that prevent the use of traditional control techniques based on mathematical analyses of equations of motion. Data-driven approaches are thus an appropriate choice for controller design, but are themselves hindered by the high number of degrees of freedom and correspondingly large state spaces. This paper presents a scheme for exploiting the 24th-order symmetry of an icosahedral tensegrity robot to vastly reduce the breadth of the controller input space without loss of information. Symmetric properties and state reduction operations are detailed and placed in the context of a data-driven control pipeline. Results are illustrated by comparing the input and output of a locomotive controller in both raw and symmetry-reduced dynamical spaces. The findings suggest a strong relief of the data requirements for training locomotive controllers. |
Hodan, T; Kouskouridas, R; Kim, T -K; Tombari, F; Bekris, K E; Drost, B; Groueix, T; Walas, K; Lepetit, V; Leonardis, A; Steger, C; Michel, F; Sahin, C; Rother, C; Matas, J A Summary of the 4th International Workshop on Recovering 6D Object Pose Journal Article 2018. Abstract | Links | BibTeX | Tags: @article{201, title = {A Summary of the 4th International Workshop on Recovering 6D Object Pose}, author = {T Hodan and R Kouskouridas and T -K Kim and F Tombari and K E Bekris and B Drost and T Groueix and K Walas and V Lepetit and A Leonardis and C Steger and F Michel and C Sahin and C Rother and J Matas}, url = {https://arxiv.org/abs/1810.03758}, year = {2018}, date = {2018-01-01}, abstract = {This document summarizes the 4th International Workshop on Recovering 6D Object Pose which was organized in conjunction with ECCV 2018 in Munich. The workshop featured four invited talks, oral and poster presentations of accepted workshop papers, and an introduction of the BOP benchmark for 6D object pose estimation. The workshop was attended by 100+ people working on relevant topics in both academia and industry who shared up-to-date advances and discussed open problems.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This document summarizes the 4th International Workshop on Recovering 6D Object Pose which was organized in conjunction with ECCV 2018 in Munich. The workshop featured four invited talks, oral and poster presentations of accepted workshop papers, and an introduction of the BOP benchmark for 6D object pose estimation. The workshop was attended by 100+ people working on relevant topics in both academia and industry who shared up-to-date advances and discussed open problems. |
2017 |
Surovik, D; Bekris, K E Deep Coverage: Motion Synthesis in the Data-Driven Era Conference International Symposium on Robotics Research (ISRR), Puerto Varas, Chile, 2017. Abstract | Links | BibTeX | Tags: @conference{179, title = {Deep Coverage: Motion Synthesis in the Data-Driven Era}, author = {D Surovik and K E 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 textquotelefttextquoteleftdeep coveragetextquoterighttextquoteright. This notion utilizes the concept of composability, a feature of traditional control and planning methods, over data-derived textquotelefttextquoteleftmotion elementstextquoterighttextquoteright, 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 textquotelefttextquoteleftdeep coveragetextquoterighttextquoteright. This notion utilizes the concept of composability, a feature of traditional control and planning methods, over data-derived textquotelefttextquoteleftmotion elementstextquoterighttextquoteright, towards generalizable and scalable solutions that adapt to real-world experience. |
Littlefield, Z; Surovik, D; Wang, W; Bekris, K E From Quasi-static to Kinodynamic Planning for Spherical Tensegrity Locomotion Conference International Symosium on Robotics Research (ISRR), Puerto Varas, Chile, 2017. Abstract | Links | BibTeX | Tags: @conference{180, title = {From Quasi-static to Kinodynamic Planning for Spherical Tensegrity Locomotion}, author = {Z Littlefield and D Surovik and W Wang and K E 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. |
Dobson, A; Solovey, K; Shome, R; Halperin, D; Bekris, K E 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. Abstract | Links | BibTeX | Tags: @conference{181, title = {Scalable Asymptotically-Optimal Multi-Robot Motion Planning}, author = {A Dobson and K Solovey and R Shome and D Halperin and K E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/scalable_asympt_opt_multi_robot.pdf}, 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. |
Shome, R; Bekris, K E IEEE International Conference on Humanoid Robots, Birmingham, UK, 2017. Abstract | Links | BibTeX | Tags: @conference{182, title = {Improving the Scalability of Asymptotically Optimal Motion Planning for Humanoid Dual-arm Manipulators}, author = {R Shome and K E 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. |
Littlefield, Z; Bekris, K E Informed Asymptotically Near-Optimal Planning for Field Robots with Dynamics Conference 11th Conference on Field and Service Robotics (FSR) 2017, Zurich, Switzerland, 2017. Abstract | Links | BibTeX | Tags: @conference{174, title = {Informed Asymptotically Near-Optimal Planning for Field Robots with Dynamics}, author = {Z Littlefield and K E 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. |
Liu, R; Kwak, D; Devarakonda, S; Bekris, K E; Iftode, L Investigating Remote Driving over the LTE Network Conference AutomotiveUI, Oldenburg, Germany, 2017. Abstract | Links | BibTeX | Tags: @conference{177, title = {Investigating Remote Driving over the LTE Network}, author = {R Liu and D Kwak and S Devarakonda and K E Bekris and L Iftode}, url = {https://www.cs.rutgers.edu/~kb572/pubs/remote_driving_LTE_network.pdf}, year = {2017}, date = {2017-09-01}, booktitle = {AutomotiveUI}, address = {Oldenburg, Germany}, abstract = {Remote driving, by bringing human operators with sophisticated perceptual and cognitive skills into the control loop over the network, solves challenging aspects of vehicle autonomy based on artificial intelligence (AI). This paper studies the human behaviors in the remote driving situation, i.e., how human remote drivers perform and assess their workload under the state-of-the-art network conditions. To explore this, we build a scaled remote driving prototype and conduct a controlled human study with varying network delays based on current commercial LTE network. Our study demonstrates that remote driving over LTE is not immediately feasible, primarily caused by the variability of the network delay instead of its magnitude. In addition, our findings also indicate that the negative effect of remote driving over LTE can be mitigated by a video frame arrangement strategy that trades off the magnitude of delay in order to achieve smoother display.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Remote driving, by bringing human operators with sophisticated perceptual and cognitive skills into the control loop over the network, solves challenging aspects of vehicle autonomy based on artificial intelligence (AI). This paper studies the human behaviors in the remote driving situation, i.e., how human remote drivers perform and assess their workload under the state-of-the-art network conditions. To explore this, we build a scaled remote driving prototype and conduct a controlled human study with varying network delays based on current commercial LTE network. Our study demonstrates that remote driving over LTE is not immediately feasible, primarily caused by the variability of the network delay instead of its magnitude. In addition, our findings also indicate that the negative effect of remote driving over LTE can be mitigated by a video frame arrangement strategy that trades off the magnitude of delay in order to achieve smoother display. |
Mitash, C; Bekris, K E; Boularias, A IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, Canada, 2017. Abstract | Links | BibTeX | Tags: @conference{175, title = {A Self-supervised Learning System for Object Detection using Physics Simulation and Multi-view Pose Estimation}, author = {C Mitash and K E 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. |
Krontiris, A; Bekris, K E Tradeoffs in the Computation of Minimum Constraint Removal Paths for Manipulation Planning Journal Article Advanced Robotics Journal, 31 , pp. 1313-1324, 2017. Abstract | Links | BibTeX | Tags: @article{178, title = {Tradeoffs in the Computation of Minimum Constraint Removal Paths for Manipulation Planning}, author = {A Krontiris and K E 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. |
Azizi, V; Kimmel, A; Bekris, K E; Kapadia, M Geometric Reachability Analysis for Grasp Planning in Cluttered Scenes for Varying End-Effectors Conference 13th IEEE Conference on Automation Science and Engineering (CASE), China, 2017. @conference{173, title = {Geometric Reachability Analysis for Grasp Planning in Cluttered Scenes for Varying End-Effectors}, author = {V Azizi and A Kimmel and K E Bekris and M Kapadia}, url = {https://www.cs.rutgers.edu/~kb572/pubs/grasping_planning_precision.pdf}, year = {2017}, date = {2017-08-01}, booktitle = {13th IEEE Conference on Automation Science and Engineering (CASE)}, journal = {13th IEEE International Conference on Automation Science and Engineering (CASE 2017)}, address = {China}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Shuai, H; Stiffler, N; Krontiris, A; Bekris, K E; 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. Abstract | Links | BibTeX | Tags: @conference{172, title = {High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods}, author = {H Shuai and N Stiffler and A Krontiris and K E Bekris and J Yu}, url = {https://arxiv.org/pdf/1705.09180.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 |
Correll, N; Bekris, K E; Berenson, D; Brock, O; Causo, A; Hauser, K; Okada, K; Rodriguez, A; Romano, J; Wurman, P Analysis and Observations From the First Amazon Picking Challenge Journal Article IEEE Transactions on Automation Science and Engineering (T-ASE), pp. 1-17, 2016. Abstract | Links | BibTeX | Tags: @article{167, title = {Analysis and Observations From the First Amazon Picking Challenge}, author = {N Correll and K E Bekris and D Berenson and O Brock and A Causo and K Hauser and K Okada and A Rodriguez and J Romano and P Wurman}, url = {http://www.cs.rutgers.edu/~kb572/pubs/apc_tase_2016.pdf}, year = {2016}, date = {2016-10-01}, journal = {IEEE Transactions on Automation Science and Engineering (T-ASE)}, pages = {1-17}, abstract = {This paper presents an overview of the inaugural Amazon Picking Challenge along with a summary of a survey conducted among the 26 participating teams. The challenge goal was to design an autonomous robot to pick items from a warehouse shelf. This task is currently performed by human workers, and there is hope that robots can someday help increase efficiency and throughput while lowering cost. We report on a 28-question survey posed to the teams to learn about each teamtextquoterights background, mechanism design, perception apparatus, planning, and control approach. We identify trends in this data, correlate it with each teamtextquoterights success in the competition, and discuss observations and lessons learned based on survey results and the authorstextquoteright personal experiences during the challenge.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This paper presents an overview of the inaugural Amazon Picking Challenge along with a summary of a survey conducted among the 26 participating teams. The challenge goal was to design an autonomous robot to pick items from a warehouse shelf. This task is currently performed by human workers, and there is hope that robots can someday help increase efficiency and throughput while lowering cost. We report on a 28-question survey posed to the teams to learn about each teamtextquoterights background, mechanism design, perception apparatus, planning, and control approach. We identify trends in this data, correlate it with each teamtextquoterights success in the competition, and discuss observations and lessons learned based on survey results and the authorstextquoteright personal experiences during the challenge. |
Littlefield, Z; Zhu, S; Kourtev, C; Psarakis, Z; Shome, R; Kimmel, A; Dobson, A; Souza, Ferreira De A; Bekris, K E 12th IEEE International Conference on Automation Science and Engineering (IEEE CASE), Fort Worth, TX, 2016. Abstract | Links | BibTeX | Tags: @conference{166, title = {Evaluating End-Effector Modalities for Warehouse Picking: A Vacuum Gripper vs a 3-finger Underactuated Hand}, author = {Z Littlefield and S Zhu and C Kourtev and Z Psarakis and R Shome and A Kimmel and A Dobson and A Ferreira De Souza and K E Bekris}, url = {https://www.cs.rutgers.edu/~kb572/pubs/apc_grasping_evaluation.pdf}, year = {2016}, date = {2016-08-01}, booktitle = {12th IEEE International Conference on Automation Science and Engineering (IEEE CASE)}, address = {Fort Worth, TX}, abstract = {This paper evaluates two end-effector modalities in the context of warehouse picking tasks, where a robot has to grasp objects inside shelves. The two end-effectors correspond to (i) a recently developed, underactuated three-finger hand and (ii) a custom built, vacuum-based gripper. The two systems significantly differ on how they need to be placed relative to an object so that a successful grasp occurs. The first tool provides increased flexibility, while the vacuum alternative is simpler and has smaller form. The objective is to highlight how the end-effector choice can significantly influence the success rate of robotic picking as well as the speed of the overall solution. For the evaluation, the same grasping planning process is followed with both end-effectors given knowledge of an objectstextquoteright pose. Multiple objects with different geometries and characteristics are placed in various poses for testing purposes. The resulting trajectories are executed on a real system to evaluate the effectiveness of the corresponding end-effector modalities in practice. The results indicate that, under different conditions, different types of end-effectors can be beneficial, which motivates the development of hybrid solutions.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper evaluates two end-effector modalities in the context of warehouse picking tasks, where a robot has to grasp objects inside shelves. The two end-effectors correspond to (i) a recently developed, underactuated three-finger hand and (ii) a custom built, vacuum-based gripper. The two systems significantly differ on how they need to be placed relative to an object so that a successful grasp occurs. The first tool provides increased flexibility, while the vacuum alternative is simpler and has smaller form. The objective is to highlight how the end-effector choice can significantly influence the success rate of robotic picking as well as the speed of the overall solution. For the evaluation, the same grasping planning process is followed with both end-effectors given knowledge of an objectstextquoteright pose. Multiple objects with different geometries and characteristics are placed in various poses for testing purposes. The resulting trajectories are executed on a real system to evaluate the effectiveness of the corresponding end-effector modalities in practice. The results indicate that, under different conditions, different types of end-effectors can be beneficial, which motivates the development of hybrid solutions. |
Littlefield, Z; Caluwaerts, K; Bruce, J; SunSpiral, V; Bekris, K E 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{159, 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 E 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}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Kimmel, A; Bekris, K E Scheduling Pick-and-Place Tasks for Dual-arm Manipulators using Incremental Search on Coordination Diagrams Journal Article 2016. @article{161, title = {Scheduling Pick-and-Place Tasks for Dual-arm Manipulators using Incremental Search on Coordination Diagrams}, author = {A Kimmel and K E Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/kimmel_schedule.pdf}, year = {2016}, date = {2016-06-01}, address = {London, UK}, keywords = {}, pubstate = {published}, tppubtype = {article} } |
Krontiris, A; Bekris, K E; Kapadia, M ACUMEN: Activity-Centric Crowd Authoring Using Influence Maps Conference 29th International Conference on Computer Animation and Social Agents (CASA), Geneva, Switzerland, 2016. @conference{160, title = {ACUMEN: Activity-Centric Crowd Authoring Using Influence Maps}, author = {A Krontiris and K E Bekris and M Kapadia}, url = {https://www.cs.rutgers.edu/~kb572/pubs/acumen_casa_2016.pdf}, year = {2016}, date = {2016-05-01}, booktitle = {29th International Conference on Computer Animation and Social Agents (CASA)}, address = {Geneva, Switzerland}, keywords = {}, pubstate = {published}, tppubtype = {conference} } |
Krontiris, A; Bekris, K E International Conference on Robotics and Automation (ICRA), Stockholm, Sweden, 2016. Abstract | Links | BibTeX | Tags: @conference{157, title = {Efficiently Solving General Rearrangement Tasks: A Fast Extension Primitive for an Incremental Sampling-based Planner}, author = {A Krontiris and K E 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 E Asymptotically Optimal Sampling-based Kinodynamic Planning Journal Article International Journal of Robotics Research (IJRR), 35 , pp. 528-564, 2016. Abstract | Links | BibTeX | Tags: @article{156, title = {Asymptotically Optimal Sampling-based Kinodynamic Planning}, author = {Y Li and Z Littlefield and K E 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. |
Rennie, C; Shome, R; Bekris, K E; Souza, Ferreira De A A Dataset for Improved RGBD-based Object Detection and Pose Estimation for Warehouse Pick-and-Place Journal Article IEEE Robotics and Automation Letters (RA-L) [Also accepted to appear at the 2016 IEEE International Conference on Robotics and Automation (ICRA)], 1 , pp. 1179 - 1185, 2016. Abstract | Links | BibTeX | Tags: @article{158, title = {A Dataset for Improved RGBD-based Object Detection and Pose Estimation for Warehouse Pick-and-Place}, author = {C Rennie and R Shome and K E Bekris and A Ferreira De Souza}, url = {http://www.cs.rutgers.edu/~kb572/pubs/icra16_pose_estimation.pdf}, year = {2016}, date = {2016-02-01}, journal = {IEEE Robotics and Automation Letters (RA-L) [Also accepted to appear at the 2016 IEEE International Conference on Robotics and Automation (ICRA)]}, volume = {1}, pages = {1179 - 1185}, address = {Stockholm, Sweden}, abstract = {An important logistics application of robotics involves manipulators that pick-and-place objects placed in warehouse shelves. A critical aspect of this task corresponds to detecting the pose of a known object in the shelf using visual data. Solving this problem can be assisted by the use of an RGB-D sensor, which also provides depth information beyond visual data. Nevertheless, it remains a challenging problem since multiple issues need to be addressed, such as low illumination inside shelves, clutter, texture-less and reflective objects as well as the limitations of depth sensors. This paper provides a new rich data set for advancing the state-of-the-art in RGBD-based 3D object pose estimation, which is focused on the challenges that arise when solving warehouse pick-and-place tasks. The publicly available data set includes thousands of images and corresponding ground truth data for the objects used during the first Amazon Picking Challenge at different poses and clutter conditions. Each image is accompanied with ground truth information to assist in the evaluation of algorithms for object detection. To show the utility of the data set, a recent algorithm for RGBD-based pose estimation is evaluated in this paper. Based on the measured performance of the algorithm on the data set, various modifications and improvements are applied to increase the accuracy of detection. These steps can be easily applied to a variety of different methodologies for object pose detection and improve performance in the domain of warehouse pick-and-place.}, keywords = {}, pubstate = {published}, tppubtype = {article} } An important logistics application of robotics involves manipulators that pick-and-place objects placed in warehouse shelves. A critical aspect of this task corresponds to detecting the pose of a known object in the shelf using visual data. Solving this problem can be assisted by the use of an RGB-D sensor, which also provides depth information beyond visual data. Nevertheless, it remains a challenging problem since multiple issues need to be addressed, such as low illumination inside shelves, clutter, texture-less and reflective objects as well as the limitations of depth sensors. This paper provides a new rich data set for advancing the state-of-the-art in RGBD-based 3D object pose estimation, which is focused on the challenges that arise when solving warehouse pick-and-place tasks. The publicly available data set includes thousands of images and corresponding ground truth data for the objects used during the first Amazon Picking Challenge at different poses and clutter conditions. Each image is accompanied with ground truth information to assist in the evaluation of algorithms for object detection. To show the utility of the data set, a recent algorithm for RGBD-based pose estimation is evaluated in this paper. Based on the measured performance of the algorithm on the data set, various modifications and improvements are applied to increase the accuracy of detection. These steps can be easily applied to a variety of different methodologies for object pose detection and improve performance in the domain of warehouse pick-and-place. |
2015 |
Littlefield, Z; Klimenko, D; Kurniawati, H; Bekris, K E The Importance of a Suitable Distance Function in Belief-Space Planning Conference International Symposium on Robotic Research (ISRR), Sestri Levante, Italy, 2015. Abstract | Links | BibTeX | Tags: @conference{152, title = {The Importance of a Suitable Distance Function in Belief-Space Planning}, author = {Z Littlefield and D Klimenko and H Kurniawati and K E Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/LKKB_metric_for_belief_planning.pdf}, year = {2015}, date = {2015-09-01}, booktitle = {International Symposium on Robotic Research (ISRR)}, address = {Sestri Levante, Italy}, abstract = {Many methods for planning under uncertainty operate in the belief space, i.e., the set of distributions over states. Although the problem is computationally hard, recent advances have shown that belief-space planning is becoming practical for many medium size problems. Some of the most successful methods utilize sampling and often rely on distances between beliefs to partially guide the search process. This paper deals with the question of what is a suitable distance function for belief space planning, which despite its importance remains unanswered. This work indicates that the rarely used Wasserstein distance (also known as Earth Movertextquoterights Distance (EMD)) is a more suitable metric than the commonly used L1 and Kullback-Leibler (KL) for belief-space planning. Simulation results on Non-Observable Markov Decision Problems, i.e., the simplest class of belief-space planning, indicate that as the problem becomes more complex, the differences on the ef- fectiveness of different distance functions become quite prominent. In fact, in state spaces with more than 4 dimensions, by just replacing L1 or KL distance with EMD, the problems become from virtually unsolvable to solvable within a reasonable time frame. Furthermore, preliminary results on Partially Observable Markov Decision Processes indicate that point-based solvers with EMD use a smaller number of samples to generate policies with similar qualities, compared to those with L1 and KL. This paper also shows that EMD caries the Lipschitz continuity of the cost of the states to Lipschitz continuity of the expected cost of the beliefs. Such a continuity property is often critical for convergence to optimal solutions.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Many methods for planning under uncertainty operate in the belief space, i.e., the set of distributions over states. Although the problem is computationally hard, recent advances have shown that belief-space planning is becoming practical for many medium size problems. Some of the most successful methods utilize sampling and often rely on distances between beliefs to partially guide the search process. This paper deals with the question of what is a suitable distance function for belief space planning, which despite its importance remains unanswered. This work indicates that the rarely used Wasserstein distance (also known as Earth Movertextquoterights Distance (EMD)) is a more suitable metric than the commonly used L1 and Kullback-Leibler (KL) for belief-space planning. Simulation results on Non-Observable Markov Decision Problems, i.e., the simplest class of belief-space planning, indicate that as the problem becomes more complex, the differences on the ef- fectiveness of different distance functions become quite prominent. In fact, in state spaces with more than 4 dimensions, by just replacing L1 or KL distance with EMD, the problems become from virtually unsolvable to solvable within a reasonable time frame. Furthermore, preliminary results on Partially Observable Markov Decision Processes indicate that point-based solvers with EMD use a smaller number of samples to generate policies with similar qualities, compared to those with L1 and KL. This paper also shows that EMD caries the Lipschitz continuity of the cost of the states to Lipschitz continuity of the expected cost of the beliefs. Such a continuity property is often critical for convergence to optimal solutions. |
Dobson, A; Bekris, K E Planning Representations and Algorithms for Prehensile Multi-Arm Manipulation Conference IEEE/RSJ International Conference on Intelligent Robots and Systems, Hamburg, Germany, 2015. Abstract | Links | BibTeX | Tags: @conference{151, title = {Planning Representations and Algorithms for Prehensile Multi-Arm Manipulation}, author = {A Dobson and K E 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 E Dealing with Difficult Instances of Object Rearrangement Conference Robotics: Science and Systems (RSS), [Best Paper & Best Student Paper Award Finalists] [Best Paper & Best Student Paper Award Finalists], Rome, Italy, 2015. Abstract | Links | BibTeX | Tags: @conference{147, title = {Dealing with Difficult Instances of Object Rearrangement}, author = {A Krontiris and K E Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Krontiris_Bekris_rearrangement_RSS2015.pdf}, year = {2015}, date = {2015-07-01}, booktitle = {Robotics: Science and Systems (RSS)}, publisher = {[Best Paper & Best Student Paper Award Finalists]}, address = {Rome, Italy}, organization = {[Best Paper & 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. |
Krontiris, A; Bekris, K E Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths Conference Symposium on Combinatorial Search (SoCS), Dead Sea, Israel, 2015. Abstract | Links | BibTeX | Tags: @conference{149, title = {Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths}, author = {A Krontiris and K E Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Krontiris_SoCS2015_MCR.pdf}, year = {2015}, date = {2015-06-01}, booktitle = {Symposium on Combinatorial Search (SoCS)}, address = {Dead Sea, Israel}, abstract = {The typical objective of path planning is to find the shortest feasible path. Many times, however, there may be no solution given the existence of constraints, such as obstacles. In these cases, the minimum constraint removal problem asks for the minimum set of constraints that need to be removed from the state space to find a solution. For instance, in manipulation planning, it is desirable to compute the minimum set of obstacles to be cleared from the workspace to manipulate a target object. Unfortunately, minimum constraint removal paths do not exhibit dynamic programming properties, i.e., subsets of optimum solutions are not necessarily optimal. Thus, searching for such solutions is computationally expensive. This leads to approximate methods, which balance the cost of computing a solution and its quality. This work investigates alternatives in this context and evaluates their performance in terms of such tradeoffs. Solutions that follow a bounded-length approach, i.e., searching for paths up to a certain length, seem to provide a good balance between minimizing constraints, computational cost and path length.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The typical objective of path planning is to find the shortest feasible path. Many times, however, there may be no solution given the existence of constraints, such as obstacles. In these cases, the minimum constraint removal problem asks for the minimum set of constraints that need to be removed from the state space to find a solution. For instance, in manipulation planning, it is desirable to compute the minimum set of obstacles to be cleared from the workspace to manipulate a target object. Unfortunately, minimum constraint removal paths do not exhibit dynamic programming properties, i.e., subsets of optimum solutions are not necessarily optimal. Thus, searching for such solutions is computationally expensive. This leads to approximate methods, which balance the cost of computing a solution and its quality. This work investigates alternatives in this context and evaluates their performance in terms of such tradeoffs. Solutions that follow a bounded-length approach, i.e., searching for paths up to a certain length, seem to provide a good balance between minimizing constraints, computational cost and path length. |