This work seeks to generate high-quality paths for complex dynamic systems. Some of the challenges addressed by this project include extending asymptotically near-optimal motion planning to systems with complex dynamics and learning better metrics for such systems. In general, providing asymptotically optimal motion planning solutions requires a boundary value problem (BVP) solver; however, this work aims to show that convergence to near-optimal solutions can be achieved without the BVP solver. This is especially important for physics-based simulations, where the system dynamics are unknown and BVP solvers for the system do not exist.
Publications:
2024 |
Sivaramakrishnan, A; Tangirala, S; Granados, E; Carver, N; Bekris, K Roadmaps with Gaps Over Controllers: Achieving Efficiency in Planning under Dynamics Inproceedings IEEE/RSJ Intern. Conference on Intelligent Robots and Systems (IROS), Abu Dhabi, United Arab Emirates, 2024. @inproceedings{Sivaramakrishnan:2024aa, title = {Roadmaps with Gaps Over Controllers: Achieving Efficiency in Planning under Dynamics}, author = {A Sivaramakrishnan and S Tangirala and E Granados and N Carver and K Bekris}, url = {https://arxiv.org/abs/2310.03239}, year = {2024}, date = {2024-10-01}, booktitle = {IEEE/RSJ Intern. Conference on Intelligent Robots and Systems (IROS)}, address = {Abu Dhabi, United Arab Emirates}, abstract = {This paper aims to improve the computational efficiency of motion planning for mobile robots with non-trivial dynamics through the use of learned controllers. It adopts a decoupled strategy, where a system-specific controller is first trained offline in an empty environment to deal with the robot's dynamics. For a target environment, the proposed approach constructs offline a data structure, a ``Roadmap with Gaps,'' to approximately learn how to solve planning queries in this environment using the learned controller. The nodes of the roadmap correspond to local regions. Edges correspond to applications of the learned control policy that approximately connect these regions. Gaps arise because the controller does not perfectly connect pairs of individual states along edges. Online, given a query, a tree sampling-based motion planner uses the roadmap so that the tree's expansion is informed towards the goal region. The tree expansion selects local subgoals given a wavefront on the roadmap that guides towards the goal. When the controller cannot reach a subgoal region, the planner resorts to random exploration to maintain probabilistic completeness and asymptotic optimality. The accompanying experimental evaluation shows that the approach significantly improves the computational efficiency of motion planning on various benchmarks, including physics-based vehicular models on uneven and varying friction terrains as well as a quadrotor under air pressure effects.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } This paper aims to improve the computational efficiency of motion planning for mobile robots with non-trivial dynamics through the use of learned controllers. It adopts a decoupled strategy, where a system-specific controller is first trained offline in an empty environment to deal with the robot's dynamics. For a target environment, the proposed approach constructs offline a data structure, a ``Roadmap with Gaps,'' to approximately learn how to solve planning queries in this environment using the learned controller. The nodes of the roadmap correspond to local regions. Edges correspond to applications of the learned control policy that approximately connect these regions. Gaps arise because the controller does not perfectly connect pairs of individual states along edges. Online, given a query, a tree sampling-based motion planner uses the roadmap so that the tree's expansion is informed towards the goal region. The tree expansion selects local subgoals given a wavefront on the roadmap that guides towards the goal. When the controller cannot reach a subgoal region, the planner resorts to random exploration to maintain probabilistic completeness and asymptotic optimality. The accompanying experimental evaluation shows that the approach significantly improves the computational efficiency of motion planning on various benchmarks, including physics-based vehicular models on uneven and varying friction terrains as well as a quadrotor under air pressure effects. |
2023 |
Wang, K; Johnson, W; Lu, S; Huang, X; Booth, J; Kramer-Bottiglio, R; Aanjaneya, M; Bekris, K Real2sim2real Transfer for Control of Cable-Driven Robots Via a Differentiable Physics Engine Inproceedings IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Detroit, MI, 2023. @inproceedings{Wang:2023aa, title = {Real2sim2real Transfer for Control of Cable-Driven Robots Via a Differentiable Physics Engine}, author = {K Wang and W Johnson and S Lu and X Huang and J Booth and R Kramer-Bottiglio and M Aanjaneya and K Bekris}, url = {https://arxiv.org/abs/2209.06261}, year = {2023}, date = {2023-10-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, address = {Detroit, MI}, abstract = {Tensegrity robots, composed of rigid rods and flexible cables, exhibit high strength-to-weight ratios and significant deformations, which enable them to navigate unstructured terrains and survive harsh impacts. They are hard to control, however, due to high dimensionality, complex dynamics, and a coupled architecture. Physics-based simulation is a promising avenue for developing locomotion policies that can be transferred to real robots. Nevertheless, modeling tensegrity robots is a complex task due to a substantial sim2real gap. To address this issue, this paper describes a Real2Sim2Real (R2S2R) strategy for tensegrity robots. This strategy is based on a differentiable physics engine that can be trained given limited data from a real robot. These data include offline measurements of physical properties, such as mass and geometry for various robot components, and the observation of a trajectory using a random control policy. With the data from the real robot, the engine can be iteratively refined and used to discover locomotion policies that are directly transferable to the real robot. Beyond the R2S2R pipeline, key contributions of this work include computing non-zero gradients at contact points, a loss function for matching tensegrity locomotion gaits, and a trajectory segmentation technique that avoids conflicts in gradient evaluation during training. Multiple iterations of the R2S2R process are demonstrated and evaluated on a real 3-bar tensegrity robot.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Tensegrity robots, composed of rigid rods and flexible cables, exhibit high strength-to-weight ratios and significant deformations, which enable them to navigate unstructured terrains and survive harsh impacts. They are hard to control, however, due to high dimensionality, complex dynamics, and a coupled architecture. Physics-based simulation is a promising avenue for developing locomotion policies that can be transferred to real robots. Nevertheless, modeling tensegrity robots is a complex task due to a substantial sim2real gap. To address this issue, this paper describes a Real2Sim2Real (R2S2R) strategy for tensegrity robots. This strategy is based on a differentiable physics engine that can be trained given limited data from a real robot. These data include offline measurements of physical properties, such as mass and geometry for various robot components, and the observation of a trajectory using a random control policy. With the data from the real robot, the engine can be iteratively refined and used to discover locomotion policies that are directly transferable to the real robot. Beyond the R2S2R pipeline, key contributions of this work include computing non-zero gradients at contact points, a loss function for matching tensegrity locomotion gaits, and a trajectory segmentation technique that avoids conflicts in gradient evaluation during training. Multiple iterations of the R2S2R process are demonstrated and evaluated on a real 3-bar tensegrity robot. |
2020 |
Kleinbort, M; Solovey, K; Bonalli, R; Granados, E; Bekris, K; Halperin, D Refined Analysis of Asymptotically-Optimal Kinodynamic Planning in the State-Cost Space Conference IEEE International Conference on Robotics and Automation (ICRA), Paris, France, 2020. @conference{Kleinbort:2020aa, title = {Refined Analysis of Asymptotically-Optimal Kinodynamic Planning in the State-Cost Space}, author = {M Kleinbort and K Solovey and R Bonalli and E Granados and K Bekris and D Halperin}, url = {https://arxiv.org/abs/1909.05569}, year = {2020}, date = {2020-06-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Paris, France}, abstract = {We present a novel analysis of AO-RRT: a tree-based planner for motion planning with kinodynamic constraints, originally described by Hauser and Zhou (AO-X, 2016). AO-RRT explores the state-cost space and has been shown to efficiently obtain high-quality solutions in practice without relying on the availability of a computationally-intensive two-point boundary-value solver. Our main contribution is an optimality proof for the single-tree version of the algorithm---a variant that was not analyzed before. Our proof only requires a mild and easily-verifiable set of assumptions on the problem and system: Lipschitz-continuity of the cost function and the dynamics. In particular, we prove that for any system satisfying these assumptions, any trajectory having a piecewise-constant control function and positive clearance from the obstacles can be approximated arbitrarily well by a trajectory found by AO-RRT. We also discuss practical aspects of AO-RRT and present experimental comparisons of variants of the algorithm.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We present a novel analysis of AO-RRT: a tree-based planner for motion planning with kinodynamic constraints, originally described by Hauser and Zhou (AO-X, 2016). AO-RRT explores the state-cost space and has been shown to efficiently obtain high-quality solutions in practice without relying on the availability of a computationally-intensive two-point boundary-value solver. Our main contribution is an optimality proof for the single-tree version of the algorithm---a variant that was not analyzed before. Our proof only requires a mild and easily-verifiable set of assumptions on the problem and system: Lipschitz-continuity of the cost function and the dynamics. In particular, we prove that for any system satisfying these assumptions, any trajectory having a piecewise-constant control function and positive clearance from the obstacles can be approximated arbitrarily well by a trajectory found by AO-RRT. We also discuss practical aspects of AO-RRT and present experimental comparisons of variants of the algorithm. |
2014 |
Krontiris, A; Shome, R; Dobson, A; Kimmel, A; Bekris, K Rearranging Similar Objects with a Manipulator Using Pebble Graphs Conference IEEE-RAS International Conference on Humanoid Robots (HUMANOIDS), Madrid, Spain, 2014. @conference{Krontiris:2014aa, title = {Rearranging Similar Objects with a Manipulator Using Pebble Graphs}, author = {A Krontiris and R Shome and A Dobson and A Kimmel and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Krontiris_Humanoids14_rearrangement.pdf}, year = {2014}, date = {2014-01-01}, booktitle = {IEEE-RAS International Conference on Humanoid Robots (HUMANOIDS)}, address = {Madrid, Spain}, abstract = {This work proposes a method for effectively computing manipulation paths to rearrange similar objects in a cluttered space. Rearrangement is a challenging problem as it involves combinatorially large, continuous configuration spaces due to the presence of multiple bodies and kinematically complex manipulators. This work leverages ideas from algorithmic theory, multi-robot motion planning and manipulation planning to propose appropriate graphical representations for this challenge. These representations allow to quickly reason whether manipulation paths allow the transition between entire sets of object arrangements without having to explicitly store these arrangements. The proposed method also allows to take advantage of precomputation given a manipulation roadmap for transferring a single object in the same cluttered space. The resulting approach is probabilistically complete for a wide set of problem instances. It is evaluated in simulation for a realistic model of a Baxter robot and executed on the real system, showing that the approach solves complex instances and is promising in terms of scalability and success ratio.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This work proposes a method for effectively computing manipulation paths to rearrange similar objects in a cluttered space. Rearrangement is a challenging problem as it involves combinatorially large, continuous configuration spaces due to the presence of multiple bodies and kinematically complex manipulators. This work leverages ideas from algorithmic theory, multi-robot motion planning and manipulation planning to propose appropriate graphical representations for this challenge. These representations allow to quickly reason whether manipulation paths allow the transition between entire sets of object arrangements without having to explicitly store these arrangements. The proposed method also allows to take advantage of precomputation given a manipulation roadmap for transferring a single object in the same cluttered space. The resulting approach is probabilistically complete for a wide set of problem instances. It is evaluated in simulation for a realistic model of a Baxter robot and executed on the real system, showing that the approach solves complex instances and is promising in terms of scalability and success ratio. |
2012 |
Bekris, K; Grady, D; Moll, M; Kavraki, L Safe Distributed Motion Coordination for Second-Order Systems with Different Planning Cycles Journal Article International Journal of Robotics Research (IJRR), 31 (2), pp. 129–149, 2012. @article{Bekris:2012aa, title = {Safe Distributed Motion Coordination for Second-Order Systems with Different Planning Cycles}, author = {K Bekris and D Grady and M Moll and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/asynchronous_coordination_journal.pdf}, year = {2012}, date = {2012-01-01}, journal = {International Journal of Robotics Research (IJRR)}, volume = {31}, number = {2}, pages = {129--149}, abstract = {When multiple robots operate in the same environment, it is desirable for scalability purposes to coordinate their motion in a distributed fashion while providing guarantees about their safety. If the robots have to respect second-order dynamics, this becomes a challenging problem, even for static environments. This work presents a replanning framework where each robot computes partial plans during each cycle, while executing a previously computed trajectory. Each robot communicates with its neighbors to select a trajectory that is safe over an infinite time horizon. The proposed approach does not require synchronization and allows the robots to dynamically change their cycles over time. This paper proves that the proposed motion coordination algorithm guarantees safety under this general setting. This framework is not specific to the underlying robot dynamics, as it can be used with a variety of dynamical systems, nor to the planning or control algorithm used to generate the robot trajectories. The performance of the approach is evaluated using a distributed multi-robot simulator on a computing cluster, where the simulated robots are forced to communicate by exchanging messages. The simulation results confirm the safety of the algorithm in various environments with up to 32 robots governed by second-order dynamics.}, keywords = {}, pubstate = {published}, tppubtype = {article} } When multiple robots operate in the same environment, it is desirable for scalability purposes to coordinate their motion in a distributed fashion while providing guarantees about their safety. If the robots have to respect second-order dynamics, this becomes a challenging problem, even for static environments. This work presents a replanning framework where each robot computes partial plans during each cycle, while executing a previously computed trajectory. Each robot communicates with its neighbors to select a trajectory that is safe over an infinite time horizon. The proposed approach does not require synchronization and allows the robots to dynamically change their cycles over time. This paper proves that the proposed motion coordination algorithm guarantees safety under this general setting. This framework is not specific to the underlying robot dynamics, as it can be used with a variety of dynamical systems, nor to the planning or control algorithm used to generate the robot trajectories. The performance of the approach is evaluated using a distributed multi-robot simulator on a computing cluster, where the simulated robots are forced to communicate by exchanging messages. The simulation results confirm the safety of the algorithm in various environments with up to 32 robots governed by second-order dynamics. |
2009 |
Bekris, K; Tsianos, K; Kavraki, L Safe and Distributed Kinodynamic Replanning for Vehicular Networks Journal Article Mobile Networks and Applications, 14 (3), 2009. @article{distributed_kinodynamic, title = {Safe and Distributed Kinodynamic Replanning for Vehicular Networks}, author = {K Bekris and K Tsianos and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/distributed_kinodynamic.pdf}, year = {2009}, date = {2009-02-01}, journal = {Mobile Networks and Applications}, volume = {14}, number = {3}, chapter = {292-308}, abstract = {This work deals with the problem of planning collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment in real-time. A challenging aspect of this problem is how to utilize communication so that vehicles do not reach states from which collisions cannot be avoided due to second-order motion constraints. This paper initially shows how it is possible to provide theoretical safety guarantees with a priority-based coordination scheme. Safety means avoiding collisions with obstacles and between vehicles. This notion is also extended to include the retainment of a communication network when the vehicles operate as a networked team. The paper then progresses to extend this safety framework into a fully distributed communication protocol for real-time planning. The proposed algorithm integrates sampling-based motion planners with message-passing protocols for distributed constraint optimization. Each vehicle uses the motion planner to generate candidate feasible trajectories and the message-passing protocol for selecting a safe and compatible trajectory. The existence of such trajectories is guaranteed by the overall approach. The theoretical results have also been experimentally confirmed with a distributed simulator built on a cluster of processors and using applications such as coordinated exploration. Furthermore, experiments show that the distributed protocol has better scalability properties when compared against the priority-based scheme.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This work deals with the problem of planning collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment in real-time. A challenging aspect of this problem is how to utilize communication so that vehicles do not reach states from which collisions cannot be avoided due to second-order motion constraints. This paper initially shows how it is possible to provide theoretical safety guarantees with a priority-based coordination scheme. Safety means avoiding collisions with obstacles and between vehicles. This notion is also extended to include the retainment of a communication network when the vehicles operate as a networked team. The paper then progresses to extend this safety framework into a fully distributed communication protocol for real-time planning. The proposed algorithm integrates sampling-based motion planners with message-passing protocols for distributed constraint optimization. Each vehicle uses the motion planner to generate candidate feasible trajectories and the message-passing protocol for selecting a safe and compatible trajectory. The existence of such trajectories is guaranteed by the overall approach. The theoretical results have also been experimentally confirmed with a distributed simulator built on a cluster of processors and using applications such as coordinated exploration. Furthermore, experiments show that the distributed protocol has better scalability properties when compared against the priority-based scheme. |
2001 |
Bekris, K; Hatzopoulos, K; Kazazakis, G; Kontolemakis, G; Masvoula, M; Tsivourakis, N; Argyros, A; Trahanias, P Pytheas: An Integrated Robotic System with Autonomous Navigation Capabilities Conference KTISIVIOS Pan Hellenic Conference in Robotics and Automation, Santorini, Greece, 2001. @conference{Bekris:2001aa, title = {Pytheas: An Integrated Robotic System with Autonomous Navigation Capabilities}, author = {K Bekris and K Hatzopoulos and G Kazazakis and G Kontolemakis and M Masvoula and N Tsivourakis and A Argyros and P Trahanias}, url = {http://www.cs.rutgers.edu/~kb572/pubs/pytheas_ktisivios.pdf}, year = {2001}, date = {2001-07-01}, booktitle = {KTISIVIOS Pan Hellenic Conference in Robotics and Automation}, address = {Santorini, Greece}, abstract = {PYTHEAS is an integrated robotic software system that offers advanced navigation capabilities, which include localization, workspace mapping, path planning and tracking and obstacle avoidance. PYTHEAS facilitates mapping of an unknown indoors environment by exploiting information extracted from a laser scanner. Based on this acquired environment representation, the system is able to navigate autonomously in the mapped environment, while, at the same time, avoiding dynamic obstacles such as moving persons, etc. All the required competences are coupled in an integrated system, which can be controlled through a user-friendly interface over the web. Extensive experimental results demonstrate the capability of the developed system to map complicated environments and support navigation in dynamic worlds.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } PYTHEAS is an integrated robotic software system that offers advanced navigation capabilities, which include localization, workspace mapping, path planning and tracking and obstacle avoidance. PYTHEAS facilitates mapping of an unknown indoors environment by exploiting information extracted from a laser scanner. Based on this acquired environment representation, the system is able to navigate autonomously in the mapped environment, while, at the same time, avoiding dynamic obstacles such as moving persons, etc. All the required competences are coupled in an integrated system, which can be controlled through a user-friendly interface over the web. Extensive experimental results demonstrate the capability of the developed system to map complicated environments and support navigation in dynamic worlds. |