Publications:
2016 |
Krontiris, A; Bekris, K International Conference on Robotics and Automation (ICRA), Stockholm, Sweden, 2016. @conference{Krontiris:2016ab, title = {Efficiently Solving General Rearrangement Tasks: A Fast Extension Primitive for an Incremental Sampling-Based Planner}, author = {A Krontiris and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/fast_object_rearrangement.pdf}, year = {2016}, date = {2016-05-01}, booktitle = {International Conference on Robotics and Automation (ICRA)}, address = {Stockholm, Sweden}, abstract = {Manipulating movable obstacles is a hard problem that involves searching high-dimensional configuration spaces. A milestone method for this problem by Stilman et al. was able to compute solutions for monotone instances. These are problems where every object needs to be transferred at most once to achieve a desired arrangement of all objects. The method uses backtracking search to find the order with which objects should be moved in the environment. This paper first proposes an approximate but significantly faster alternative for monotone rearrangement instances. The method defines a dependency graph between objects given the minimum constraint removal paths (Minimum Constraint Removal) to transfer each object to its target. From this graph it is possible to discover the order of moving the objects by performing topological sorting without the need for backtracking search. The approximation arises from the limitation to consider only the Minimum Constraint Removal paths for moving the objects. Such paths, however, minimize the number of conflicts between the objects. To solve non-monotone instances, this primitive is incorporated in a higher-level incremental search algorithm for general rearrangement planning, that operates similar to Bi-RRT. Given a start and a goal arrangement of objects, tree structures of reachable new arrangements are generated by using the primitive as an expansion procedure. The integrated solution achieves probabilistic completeness for the general non-monotone case and based on simulated experiments it achieves very good success ratios, solution times and path quality relative to all the alternatives considered.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Manipulating movable obstacles is a hard problem that involves searching high-dimensional configuration spaces. A milestone method for this problem by Stilman et al. was able to compute solutions for monotone instances. These are problems where every object needs to be transferred at most once to achieve a desired arrangement of all objects. The method uses backtracking search to find the order with which objects should be moved in the environment. This paper first proposes an approximate but significantly faster alternative for monotone rearrangement instances. The method defines a dependency graph between objects given the minimum constraint removal paths (Minimum Constraint Removal) to transfer each object to its target. From this graph it is possible to discover the order of moving the objects by performing topological sorting without the need for backtracking search. The approximation arises from the limitation to consider only the Minimum Constraint Removal paths for moving the objects. Such paths, however, minimize the number of conflicts between the objects. To solve non-monotone instances, this primitive is incorporated in a higher-level incremental search algorithm for general rearrangement planning, that operates similar to Bi-RRT. Given a start and a goal arrangement of objects, tree structures of reachable new arrangements are generated by using the primitive as an expansion procedure. The integrated solution achieves probabilistic completeness for the general non-monotone case and based on simulated experiments it achieves very good success ratios, solution times and path quality relative to all the alternatives considered. |
Li, Y; Littlefield, Z; Bekris, K Asymptotically Optimal Sampling-Based Kinodynamic Planning Journal Article International Journal of Robotics Research (IJRR), 35 , pp. 528–564, 2016. @article{Li:2016aa, title = {Asymptotically Optimal Sampling-Based Kinodynamic Planning}, author = {Y Li and Z Littlefield and K Bekris}, url = {http://arxiv.org/abs/1407.2896}, year = {2016}, date = {2016-04-01}, journal = {International Journal of Robotics Research (IJRR)}, volume = {35}, pages = {528--564}, abstract = {Sampling-based algorithms are viewed as practical solutions for high-dimensional motion planning. Recent progress has taken advantage of random geometric graph theory to show how asymptotic optimality can also be achieved with these methods. Achieving this desirable property for systems with dynamics requires solving a two-point boundary value problem (BVP) in the state space of the underlying dynamical system. It is difficult, however, if not impractical, to generate a BVP solver for a variety of important dynamical models of robots or physically simulated ones. Thus, an open challenge was whether it was even possible to achieve optimality guarantees when planning for systems without access to a BVP solver. This work resolves the above question and describes how to achieve asymptotic optimality for kinodynamic planning using incremental sampling-based planners by introducing a new rigorous framework. Two new methods, Stable Sparse-RRT (SST) and SST*, result from this analysis, which are asymptotically near-optimal and optimal, respectively. The techniques are shown to converge fast to high-quality paths, while they maintain only a sparse set of samples, which makes them computationally efficient. The good performance of the planners is confirmed by experimental results using dynamical systems benchmarks, as well as physically simulated robots.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Sampling-based algorithms are viewed as practical solutions for high-dimensional motion planning. Recent progress has taken advantage of random geometric graph theory to show how asymptotic optimality can also be achieved with these methods. Achieving this desirable property for systems with dynamics requires solving a two-point boundary value problem (BVP) in the state space of the underlying dynamical system. It is difficult, however, if not impractical, to generate a BVP solver for a variety of important dynamical models of robots or physically simulated ones. Thus, an open challenge was whether it was even possible to achieve optimality guarantees when planning for systems without access to a BVP solver. This work resolves the above question and describes how to achieve asymptotic optimality for kinodynamic planning using incremental sampling-based planners by introducing a new rigorous framework. Two new methods, Stable Sparse-RRT (SST) and SST*, result from this analysis, which are asymptotically near-optimal and optimal, respectively. The techniques are shown to converge fast to high-quality paths, while they maintain only a sparse set of samples, which makes them computationally efficient. The good performance of the planners is confirmed by experimental results using dynamical systems benchmarks, as well as physically simulated robots. |
2015 |
Dobson, A; Bekris, K Planning Representations and Algorithms for Prehensile Multi-Arm Manipulation Conference IEEE/RSJ International Conference on Intelligent Robots and Systems, Hamburg, Germany, 2015. @conference{Dobson:2015ab, title = {Planning Representations and Algorithms for Prehensile Multi-Arm Manipulation}, author = {A Dobson and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Dobson_Bekris_multi_arm_iros15.pdf}, year = {2015}, date = {2015-09-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems}, address = {Hamburg, Germany}, abstract = {This paper describes the topology of general multi-arm prehensile manipulation by extending work on the single and dual-arm cases. Reasonable assumptions are applied to reduce the number of manipulation modes, which results in an explicit graphical representation for multi-arm manipulation that is computationally manageable to store and search for solution paths. In this context, it is also possible to take advantage of preprocessing steps to significantly speed up online query resolution. The approach is evaluated in simulation for multiple arms showing it is possible to quickly compute multi-arm manipulation paths of high-quality on the fly.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper describes the topology of general multi-arm prehensile manipulation by extending work on the single and dual-arm cases. Reasonable assumptions are applied to reduce the number of manipulation modes, which results in an explicit graphical representation for multi-arm manipulation that is computationally manageable to store and search for solution paths. In this context, it is also possible to take advantage of preprocessing steps to significantly speed up online query resolution. The approach is evaluated in simulation for multiple arms showing it is possible to quickly compute multi-arm manipulation paths of high-quality on the fly. |
Krontiris, A; Bekris, K Dealing with Difficult Instances of Object Rearrangement Conference Robotics: Science and Systems (RSS), 1123 , [Best Paper & Best Student Paper Award Finalists] [Best Paper & Best Student Paper Award Finalists], Rome, Italy, 2015. @conference{Krontiris:2015ab, title = {Dealing with Difficult Instances of Object Rearrangement}, author = {A Krontiris and K Bekris}, url = {https://people.cs.rutgers.edu/~kb572/pubs/Krontiris_Bekris_rearrangement_RSS2015.pdf}, year = {2015}, date = {2015-07-01}, booktitle = {Robotics: Science and Systems (RSS)}, volume = {1123}, publisher = {[Best Paper & 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. |
Kolchmeyer, R; Dobson, A; Bekris, K Expected Path Degradation When Searching Over a Sparse Grid Hierarchy Conference Symposium on Combinatorial Search (SoCS), Ein Gedi, Dead Sea, Israel, 2015. @conference{Kolchmeyer:2015aa, title = {Expected Path Degradation When Searching Over a Sparse Grid Hierarchy}, author = {R Kolchmeyer and A Dobson and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Kolchmeyer_SoCS2015_Sparse_Grid.pdf}, year = {2015}, date = {2015-06-01}, booktitle = {Symposium on Combinatorial Search (SoCS)}, address = {Ein Gedi, Dead Sea, Israel}, abstract = {A traditional direction for more efficient grid-based pathfinding is to speed up the search algorithm. An alternative, however, is to create a sparser grid representation, which can also significantly speed up searching for a path. This direction is related to the idea of spanners from graph theory. These are subgraphs that allow the computation of paths between any two vertices of the original graph while guaranteeing a maximum stretch in path length. In practice, the path degradation of graph spanners is significantly smaller than the theoretical bound; even so, expected path degradation of graph spanners is typically not studied. This work is inspired by this observation and focuses on grid path-finding to propose an algorithm that constructs a grid spanner. Theoretical analysis for the obstacle free case shows that significant performance gains can be achieved with a small decrease in expected path quality. This is an important first step towards studying the expected performance of spanners. Experiments on game maps show that expected path quality with obstacles is only sometimes marginally lower than that in the obstacle-free case and that a significant reduction in the size of the search space can be achieved.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } A traditional direction for more efficient grid-based pathfinding is to speed up the search algorithm. An alternative, however, is to create a sparser grid representation, which can also significantly speed up searching for a path. This direction is related to the idea of spanners from graph theory. These are subgraphs that allow the computation of paths between any two vertices of the original graph while guaranteeing a maximum stretch in path length. In practice, the path degradation of graph spanners is significantly smaller than the theoretical bound; even so, expected path degradation of graph spanners is typically not studied. This work is inspired by this observation and focuses on grid path-finding to propose an algorithm that constructs a grid spanner. Theoretical analysis for the obstacle free case shows that significant performance gains can be achieved with a small decrease in expected path quality. This is an important first step towards studying the expected performance of spanners. Experiments on game maps show that expected path quality with obstacles is only sometimes marginally lower than that in the obstacle-free case and that a significant reduction in the size of the search space can be achieved. |
Krontiris, A; Bekris, K Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths Conference Symposium on Combinatorial Search (SoCS), Dead Sea, Israel, 2015. @conference{Krontiris:2015aa, title = {Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths}, author = {A Krontiris and K 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. |
Dobson, A; Moustakides, G; Bekris, K IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, 2015. @conference{Dobson:2015aa, title = {Geometric Probability Results for Bounding Path Quality in Sampling-Based Roadmaps After Finite Computation}, author = {A Dobson and G Moustakides and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/finite_prm.pdf}, year = {2015}, date = {2015-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Seattle, WA}, abstract = {Sampling-based algorithms provide efficient solutions to high-dimensional, geometrically complex motion planning problems. For these methods asymptotic results are known in terms of completeness and optimality. Previous work by the authors argued that such methods also provide probabilistic near-optimality after finite computation time using indications from Monte Carlo experiments. This work formalizes these guarantees and provides a bound on the probability of finding a near-optimal solution with PRM* after a finite number of iterations. This bound is proven for general-dimension Euclidean spaces and evaluated through simulation. These results are leveraged to create automated stopping criteria for PRM* and sparser near-optimal roadmaps, which have reduced running time and storage requirements.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Sampling-based algorithms provide efficient solutions to high-dimensional, geometrically complex motion planning problems. For these methods asymptotic results are known in terms of completeness and optimality. Previous work by the authors argued that such methods also provide probabilistic near-optimality after finite computation time using indications from Monte Carlo experiments. This work formalizes these guarantees and provides a bound on the probability of finding a near-optimal solution with PRM* after a finite number of iterations. This bound is proven for general-dimension Euclidean spaces and evaluated through simulation. These results are leveraged to create automated stopping criteria for PRM* and sparser near-optimal roadmaps, which have reduced running time and storage requirements. |
Bekris, K; Shome, R; Krontiris, A; Dobson, A Cloud Automation: Precomputing Roadmaps for Flexible Manipulation Journal Article IEEE Robotics and Automation Magazine, (accepted) , 2015. @article{Bekris:2015aa, title = {Cloud Automation: Precomputing Roadmaps for Flexible Manipulation}, author = {K Bekris and R Shome and A Krontiris and A Dobson}, url = {http://www.cs.rutgers.edu/~kb572/pubs/cloud_manipulation.pdf}, year = {2015}, date = {2015-01-01}, journal = {IEEE Robotics and Automation Magazine}, volume = {(accepted)}, abstract = {This work aims to highlight the benefits of Cloud Automation, the opportunities that arise for industrial adopters and some of the research challenges that must be addressed in this process. The focus is on the use of cloud computing for efficiently planning the motion of new robot manipulators designed for flexible manufacturing floors. In particular, different ways that a robot can interact with a computing cloud are considered, where an architecture that splits computation between the remote cloud and the robot appears advantageous. Given this synergistic robot-cloud architecture, this work describes how solutions from the recent motion planning literature can be employed on the cloud during a periodically updated preprocessing phase to efficiently answer manipulation queries on the robot given changes in the workspace. In this setup, interesting tradeoffs arise between path quality and computational efficiency, which are evaluated in simulation. These tradeoffs motivate further research on how motion planning should be executed given access to a computing cloud.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This work aims to highlight the benefits of Cloud Automation, the opportunities that arise for industrial adopters and some of the research challenges that must be addressed in this process. The focus is on the use of cloud computing for efficiently planning the motion of new robot manipulators designed for flexible manufacturing floors. In particular, different ways that a robot can interact with a computing cloud are considered, where an architecture that splits computation between the remote cloud and the robot appears advantageous. Given this synergistic robot-cloud architecture, this work describes how solutions from the recent motion planning literature can be employed on the cloud during a periodically updated preprocessing phase to efficiently answer manipulation queries on the robot given changes in the workspace. In this setup, interesting tradeoffs arise between path quality and computational efficiency, which are evaluated in simulation. These tradeoffs motivate further research on how motion planning should be executed given access to a computing cloud. |
2014 |
Kimmel, A; Bekris, K Decentralized Multi-Agent Path Selection Using Minimal Information Conference International Symposium on Distributed Autonomous Robotic Systems (DARS), Daejeon, Korea, 2014. @conference{Kimmel:2014aa, title = {Decentralized Multi-Agent Path Selection Using Minimal Information}, author = {A Kimmel and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Kimmel_DARS2014_MinimumConflict.pdf}, year = {2014}, date = {2014-11-01}, booktitle = {International Symposium on Distributed Autonomous Robotic Systems (DARS)}, address = {Daejeon, Korea}, abstract = {This work aims to avoid conflicts between moving, non-communicating agents, which employ minimum sensing information. Since safety can be guaranteed by reactive obstacle avoidance for holonomic systems, the focus is on deadlock avoidance given proper selection of global paths in cluttered scenes. A method to compute the "interaction" of a path is proposed, which considers only the neighboring agents observed positions. Minimizing the interaction cost in a prototypical challenge involving two agents moving through two corridors from opposing sides guarantees the selection of non-conflicting paths. Complex scenes, however, where agents have many paths to follow are more challenging. This leads to a study of alternatives for decentralized path selection. Simulated experiments indicate that following a minimum-conflict path given the other agents observed positions results in deadlock avoidance. A scheme that selects between the minimum-conflict path and a set of shortest paths given their interaction cost improves path quality while still achieving deadlock avoidance. Finally, learning to select between the minimum-conflict and one of the shortest paths can also be achieved by reasoning using regret minimization. This hindsight learning method allows agents to be adaptive to the behavior of their neighbors.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This work aims to avoid conflicts between moving, non-communicating agents, which employ minimum sensing information. Since safety can be guaranteed by reactive obstacle avoidance for holonomic systems, the focus is on deadlock avoidance given proper selection of global paths in cluttered scenes. A method to compute the "interaction" of a path is proposed, which considers only the neighboring agents observed positions. Minimizing the interaction cost in a prototypical challenge involving two agents moving through two corridors from opposing sides guarantees the selection of non-conflicting paths. Complex scenes, however, where agents have many paths to follow are more challenging. This leads to a study of alternatives for decentralized path selection. Simulated experiments indicate that following a minimum-conflict path given the other agents observed positions results in deadlock avoidance. A scheme that selects between the minimum-conflict path and a set of shortest paths given their interaction cost improves path quality while still achieving deadlock avoidance. Finally, learning to select between the minimum-conflict and one of the shortest paths can also be achieved by reasoning using regret minimization. This hindsight learning method allows agents to be adaptive to the behavior of their neighbors. |
Littlefield, Z; Krontiris, A; Kimmel, A; Dobson, A; Shome, R; Bekris, K An Extensible Software Architecture for Composing Motion and Task Planners Conference International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR), Bergamo, Italy, 2014. @conference{Littlefield:2014aa, title = {An Extensible Software Architecture for Composing Motion and Task Planners}, author = {Z Littlefield and A Krontiris and A Kimmel and A Dobson and R Shome and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/pracsys_simpar14.pdf}, year = {2014}, date = {2014-10-01}, booktitle = {International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR)}, address = {Bergamo, Italy}, abstract = {This paper describes a software infrastructure for developing and composing task and motion planners. The functionality of motion planners is well defined and they provide a basic primitive on top of which it is possible to develop planners for addressing higher level tasks. It is more challenging, however, to identify a common interface for task planners, given the variety of challenges that they can be used for. The proposed software platform follows a hierarchical, object-oriented structure and identifies key abstractions that help in integrating new task planners with popular sampling-based motion planners. Examples of use cases that can be implemented within this common software framework include robotics applications such as planning among dynamic obstacles, object manipulation and rearrangement, as well as decentralized motion coordination. The described platform has been used to plan for a Baxter robot rearranging similar objects in an environment in an efficient way.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper describes a software infrastructure for developing and composing task and motion planners. The functionality of motion planners is well defined and they provide a basic primitive on top of which it is possible to develop planners for addressing higher level tasks. It is more challenging, however, to identify a common interface for task planners, given the variety of challenges that they can be used for. The proposed software platform follows a hierarchical, object-oriented structure and identifies key abstractions that help in integrating new task planners with popular sampling-based motion planners. Examples of use cases that can be implemented within this common software framework include robotics applications such as planning among dynamic obstacles, object manipulation and rearrangement, as well as decentralized motion coordination. The described platform has been used to plan for a Baxter robot rearranging similar objects in an environment in an efficient way. |
Li, Y; Littlefield, Z; Bekris, K Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning Conference Workshop on the Algorithmic Foundations of Robotics (WAFR), Istanbul, Turkey, 2014. @conference{Li:2014aa, title = {Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning}, author = {Y Li and Z Littlefield and K Bekris}, url = {https://link.springer.com/chapter/10.1007/978-3-319-16595-0_16}, year = {2014}, date = {2014-08-01}, booktitle = {Workshop on the Algorithmic Foundations of Robotics (WAFR)}, pages = {263--282}, address = {Istanbul, Turkey}, abstract = {This work describes SST, an algorithm that (a) provides asymptotic (near-)optimality for kinodynamic planning without access to a steering function, (b) maintains only a sparse set of samples, (c) converges fast to high-quality paths and (d) achieves competitive running time to RRT, which provides only probabilistic completeness. This algorithm addresses the limitation of RRT*, which requires a steering function for asymptotic optimality. This issue has motivated recent variations of RRT*, which either work for a limiting set of systems or exhibit increased computational cost. This paper provides formal arguments for the properties of the proposed algorithm. To the best of the authorstextquoteright knowledge, this is the first sparse data structure that provides such desirable guarantees for a wide set of systems under a reasonable set of assumptions. Simulations for a variety of standard benchmarks, including using a physics engine, confirm the argued properties of the approach.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This work describes SST, an algorithm that (a) provides asymptotic (near-)optimality for kinodynamic planning without access to a steering function, (b) maintains only a sparse set of samples, (c) converges fast to high-quality paths and (d) achieves competitive running time to RRT, which provides only probabilistic completeness. This algorithm addresses the limitation of RRT*, which requires a steering function for asymptotic optimality. This issue has motivated recent variations of RRT*, which either work for a limiting set of systems or exhibit increased computational cost. This paper provides formal arguments for the properties of the proposed algorithm. To the best of the authorstextquoteright knowledge, this is the first sparse data structure that provides such desirable guarantees for a wide set of systems under a reasonable set of assumptions. Simulations for a variety of standard benchmarks, including using a physics engine, confirm the argued properties of the approach. |
A., Dobson A; Bekris, K Improved Heuristic Search for Computing Sparse Data Structures for Motion Planning Conference Symposium on Combinatorial Search (SoCS), Prague, Czech Republic, 2014. @conference{Dobson:2014aa, title = {Improved Heuristic Search for Computing Sparse Data Structures for Motion Planning}, author = {A Dobson A. and K Bekris}, url = {http://www.aaai.org/ocs/index.php/SOCS/SOCS14/paper/viewFile/8919/8898}, year = {2014}, date = {2014-08-01}, booktitle = {Symposium on Combinatorial Search (SoCS)}, address = {Prague, Czech Republic}, abstract = {Sampling-based motion planners provide efficient, flexible solutions for computing motion, even for relatively complex systems operating in high-dimensional spaces. Asymptotically optimal variants of these planners ensure convergence to the optimal solution, but produce prohibitively dense structures. This work shows how to extend sparse methods achieving asymptotic near-optimality by performing multiple-goal heuristic search during graph construction. The result is an extension of an existing framework for sparse motion planning roadmaps, the Incremental Roadmap Spanner, which produces identical output, but does so in an order of magnitude less time.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Sampling-based motion planners provide efficient, flexible solutions for computing motion, even for relatively complex systems operating in high-dimensional spaces. Asymptotically optimal variants of these planners ensure convergence to the optimal solution, but produce prohibitively dense structures. This work shows how to extend sparse methods achieving asymptotic near-optimality by performing multiple-goal heuristic search during graph construction. The result is an extension of an existing framework for sparse motion planning roadmaps, the Incremental Roadmap Spanner, which produces identical output, but does so in an order of magnitude less time. |
Zhao, M; Shome, R; Yochelson, I; Bekris, K; Kowler, E An Experimental Study for Identifying Features of Legible Manipulator Paths Conference International Symposium on Experimental Robotics (ISER), Marrakech/Essaouira, Morocco, 2014. @conference{Zhao:2014aa, title = {An Experimental Study for Identifying Features of Legible Manipulator Paths}, author = {M Zhao and R Shome and I Yochelson and K Bekris and E Kowler}, url = {http://www.cs.rutgers.edu/~kb572/pubs/ISER_Motion_Legibility.pdf}, year = {2014}, date = {2014-06-01}, booktitle = {International Symposium on Experimental Robotics (ISER)}, address = {Marrakech/Essaouira, Morocco}, abstract = {The increasing availability of low-cost, compliant and human-friendly manipulators, such as Rethink Robotics' Baxter, allows robots to share a common workspace and cooperate with human workers. It is important that the human is able to easily understand the robot's intentions by observing its actions. Legible motion plans are an important part of making the robot understandable by human co-workers intuitively. The legible robot motion has been investigated in previous studies, which focus on generating and discriminating the legibility of motion with two reachable targets. The current study is to expand upon the existing experimental studies in two primary directions. Firstly, this work considers a workspace with many potential targets for the robot to interact with, as well as to avoid. Secondly, experiments are performed under the guidance of psychophysicists where human subjects are placed in close proximity to but out of reach of the manipulator robot. These experiments confirm aspects of previous work, such as the contradictory nature of shortest and legible paths, and they also reveal important features of legible paths in cluttered scenes. For instance, the direction and path of the end effector is shown to significantly influence a human observer's capability to realize the robot's intended target.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } The increasing availability of low-cost, compliant and human-friendly manipulators, such as Rethink Robotics' Baxter, allows robots to share a common workspace and cooperate with human workers. It is important that the human is able to easily understand the robot's intentions by observing its actions. Legible motion plans are an important part of making the robot understandable by human co-workers intuitively. The legible robot motion has been investigated in previous studies, which focus on generating and discriminating the legibility of motion with two reachable targets. The current study is to expand upon the existing experimental studies in two primary directions. Firstly, this work considers a workspace with many potential targets for the robot to interact with, as well as to avoid. Secondly, experiments are performed under the guidance of psychophysicists where human subjects are placed in close proximity to but out of reach of the manipulator robot. These experiments confirm aspects of previous work, such as the contradictory nature of shortest and legible paths, and they also reveal important features of legible paths in cluttered scenes. For instance, the direction and path of the end effector is shown to significantly influence a human observer's capability to realize the robot's intended target. |
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. |
Krontiris, A; Shome, R; Dobson, A; Kimmel, A; Yochelson, I; Bekris, K Similar Part Rearrangement with Pebble Graphs Journal Article CoRR, abs/1404.6573 , 2014. @article{Krontiris:2014ab, title = {Similar Part Rearrangement with Pebble Graphs}, author = {A Krontiris and R Shome and A Dobson and A Kimmel and I Yochelson and K Bekris}, url = {https://arxiv.org/abs/1404.6573}, year = {2014}, date = {2014-01-01}, journal = {CoRR}, volume = {abs/1404.6573}, abstract = {This work proposes a method for effectively computing manipulation paths to rearrange similar objects in a cluttered space. The solution can be used to place similar products in a factory floor in a desirable arrangement or for retrieving a particular object from a shelf blocked by similarly sized objects. These are challenging problems as they involve combinatorially large, continuous configuration spaces due to the presence of multiple moving 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 objects arrangements without having to explicitly enumerate the path for each pair of 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 evaluated in simulation for a realistic model of a Baxter robot and executed in open-loop 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 = {article} } This work proposes a method for effectively computing manipulation paths to rearrange similar objects in a cluttered space. The solution can be used to place similar products in a factory floor in a desirable arrangement or for retrieving a particular object from a shelf blocked by similarly sized objects. These are challenging problems as they involve combinatorially large, continuous configuration spaces due to the presence of multiple moving 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 objects arrangements without having to explicitly enumerate the path for each pair of 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 evaluated in simulation for a realistic model of a Baxter robot and executed in open-loop on the real system, showing that the approach solves complex instances and is promising in terms of scalability and success ratio. |
Dobson, A; Bekris, K Sparse Roadmap Spanners for Asymptotically Near-Optimal Motion Planning Journal Article International Journal of Robotics Research (IJRR), 33 , pp. 18–47, 2014. @article{Dobson:2014ad, title = {Sparse Roadmap Spanners for Asymptotically Near-Optimal Motion Planning}, author = {A Dobson and K Bekris}, url = {https://journals.sagepub.com/doi/10.1177/0278364913498292}, year = {2014}, date = {2014-01-01}, journal = {International Journal of Robotics Research (IJRR)}, volume = {33}, pages = {18--47}, abstract = {Asymptotically optimal planners, such as PRM*, guarantee that solutions approach optimal as the number of iterations increases. Roadmaps with this property, however, may grow too large for storing on resource-constrained robots and for achieving efficient online query resolution. By relaxing optimality, asymptotically near-optimal planners produce sparser graphs by not including all edges. The idea stems from graph spanners, which produce sparse subgraphs that guarantee near-optimality. Existing asymptotically optimal and near-optimal planners, however, include all sampled configurations as roadmap nodes, meaning only infinite-size graphs have the desired properties. To address this limitation, this work describes SPARS, an algorithm that returns a sparse roadmap spanner. The method provides the following properties: (a) probabilistic completeness, (b) asymptotic near-optimality and (c) the probability of adding nodes to the spanner converges to zero as iterations increase. The last point suggests that finite-size data structures with asymptotic near-optimality in continuous spaces may indeed exist. The approach builds simultaneously a dense graph similar to PRM* and its roadmap spanner, meaning that upon construction an infinite-size graph is still needed asymptotically. An extension of SPARS is also presented, termed SPARS-2, which removes the dependency on building a dense graph for constructing the sparse roadmap spanner and for which it is shown that the same desirable properties hold. Simulations for rigid body motion planning show that algorithms for constructing sparse roadmap spanners indeed provide small data structures and result in faster query resolution. The rate of node addition is shown to decrease over time and practically the quality of solutions is considerably better than the theoretical bounds. Upon construction, the memory requirements of SPARS-2 are significantly smaller but there is a small sacrifice in the size of the final spanner relative to SPARS.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Asymptotically optimal planners, such as PRM*, guarantee that solutions approach optimal as the number of iterations increases. Roadmaps with this property, however, may grow too large for storing on resource-constrained robots and for achieving efficient online query resolution. By relaxing optimality, asymptotically near-optimal planners produce sparser graphs by not including all edges. The idea stems from graph spanners, which produce sparse subgraphs that guarantee near-optimality. Existing asymptotically optimal and near-optimal planners, however, include all sampled configurations as roadmap nodes, meaning only infinite-size graphs have the desired properties. To address this limitation, this work describes SPARS, an algorithm that returns a sparse roadmap spanner. The method provides the following properties: (a) probabilistic completeness, (b) asymptotic near-optimality and (c) the probability of adding nodes to the spanner converges to zero as iterations increase. The last point suggests that finite-size data structures with asymptotic near-optimality in continuous spaces may indeed exist. The approach builds simultaneously a dense graph similar to PRM* and its roadmap spanner, meaning that upon construction an infinite-size graph is still needed asymptotically. An extension of SPARS is also presented, termed SPARS-2, which removes the dependency on building a dense graph for constructing the sparse roadmap spanner and for which it is shown that the same desirable properties hold. Simulations for rigid body motion planning show that algorithms for constructing sparse roadmap spanners indeed provide small data structures and result in faster query resolution. The rate of node addition is shown to decrease over time and practically the quality of solutions is considerably better than the theoretical bounds. Upon construction, the memory requirements of SPARS-2 are significantly smaller but there is a small sacrifice in the size of the final spanner relative to SPARS. |
2013 |
Dobson, A; Bekris, K Finite-Time Near-Optimality Properties of Sampling-Based Motion Planners Conference IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Tokyo Big Sight, Japan, 2013. @conference{Dobson:2013ab, title = {Finite-Time Near-Optimality Properties of Sampling-Based Motion Planners}, author = {A Dobson and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/finitetime_iros13.pdf}, year = {2013}, date = {2013-11-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, address = {Tokyo Big Sight, Japan}, abstract = {Sampling-based algorithms have proven practical in solving motion planning challenges in relatively high-dimensional instances in geometrically complex workspaces. Early work focused on quickly returning feasible solutions. Only recently was it shown under which conditions algorithms, such as PRM*, return optimal solutions in an asymptotic sense or near-optimal for the recently proposed roadmap spanners. Still, all these methods yield desired properties in an asymptotic fashion, meaning the properties are only truly attained after infinite amount of computation time. This work studies the finite-time properties of sampling-based algorithms in turns of path quality. The focus is on planners that construct roadmaps, as it is more straightforward to reason for these techniques. This paper argues that existing sampling-based planners, which construct roadmaps in an asymptotically optimal or near-optimal manner, exhibit a probably near-optimal property in finite time. This means that it is possible to compute a confidence value, i.e., a probability, regarding the existence of upper bounds for the length of the path returned by the roadmap as a function of the number of configuration space samples. This property can result in useful tools for determining existence of solutions and a probabilistic stopping criterion for prm -like methods. These properties are validated through experimental trials on point systems in Euclidean and toroidal spaces.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Sampling-based algorithms have proven practical in solving motion planning challenges in relatively high-dimensional instances in geometrically complex workspaces. Early work focused on quickly returning feasible solutions. Only recently was it shown under which conditions algorithms, such as PRM*, return optimal solutions in an asymptotic sense or near-optimal for the recently proposed roadmap spanners. Still, all these methods yield desired properties in an asymptotic fashion, meaning the properties are only truly attained after infinite amount of computation time. This work studies the finite-time properties of sampling-based algorithms in turns of path quality. The focus is on planners that construct roadmaps, as it is more straightforward to reason for these techniques. This paper argues that existing sampling-based planners, which construct roadmaps in an asymptotically optimal or near-optimal manner, exhibit a probably near-optimal property in finite time. This means that it is possible to compute a confidence value, i.e., a probability, regarding the existence of upper bounds for the length of the path returned by the roadmap as a function of the number of configuration space samples. This property can result in useful tools for determining existence of solutions and a probabilistic stopping criterion for prm -like methods. These properties are validated through experimental trials on point systems in Euclidean and toroidal spaces. |
Littlefield, Z; Li, Y; Bekris, K IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Tokyo Big Sight, Japan, 2013. @conference{Littlefield:2013aa, title = {Efficient Sampling-Based Motion Planning with Asymptotic Near-Optimality Guarantees for Systems with Dynamics}, author = {Z Littlefield and Y Li and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/sparse_rrt_iros13.pdf}, year = {2013}, date = {2013-11-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, address = {Tokyo Big Sight, Japan}, abstract = {Recent significant progress has provided sampling-based motion planners, such as RRT*, that asymptotically converge to optimal solutions. The basic variant of such methods requires a local planner, which connects two states with a trajectory. For systems with dynamics, the local planner needs to solve a two-point boundary value problem (BVP) for differential equations. Such a solver is not always available for state update equations of interesting systems with dynamics. Furthermore, asymptotically optimal solutions tend to impose increased computational requirements in practice relative to alternatives, such as RRT, that focus on feasibility, state-space exploration speed and which do not require a local planner. This paper describes a sampling-based motion planning solution with the following desirable properties: a) it does not require a BVP solver but only uses a forward propagation model, b) it employs a single propagation per iteration similar to RRT, making it very efficient, c) it is asymptotically near-optimal, and d) provides a sparse data structure for answering path queries, which further improves computational performance. Simulations on prototypical dynamical systems show the method is able to improve the quality of feasible solutions over time and that it is computationally efficient.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Recent significant progress has provided sampling-based motion planners, such as RRT*, that asymptotically converge to optimal solutions. The basic variant of such methods requires a local planner, which connects two states with a trajectory. For systems with dynamics, the local planner needs to solve a two-point boundary value problem (BVP) for differential equations. Such a solver is not always available for state update equations of interesting systems with dynamics. Furthermore, asymptotically optimal solutions tend to impose increased computational requirements in practice relative to alternatives, such as RRT, that focus on feasibility, state-space exploration speed and which do not require a local planner. This paper describes a sampling-based motion planning solution with the following desirable properties: a) it does not require a BVP solver but only uses a forward propagation model, b) it employs a single propagation per iteration similar to RRT, making it very efficient, c) it is asymptotically near-optimal, and d) provides a sparse data structure for answering path queries, which further improves computational performance. Simulations on prototypical dynamical systems show the method is able to improve the quality of feasible solutions over time and that it is computationally efficient. |
Kimmel, A; Bekris, K Minimizing Conflicts between Moving Agents Over a Set of Non-Homotopic Paths through Regret Minimization Journal Article 2013. @article{Kimmel:2013aa, title = {Minimizing Conflicts between Moving Agents Over a Set of Non-Homotopic Paths through Regret Minimization}, author = {A Kimmel and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/work_aaai_13_regret_minimization.pdf}, year = {2013}, date = {2013-07-01}, address = {Bellevue, WA, USA}, school = {AAAI 2013 Workshop on Intelligent Robotic Systems}, abstract = {This paper considers a game-theoretic framework for motion coordination challenges. The focus of this work is to minimize the number of interactions agents have when moving through an environment. In particular, agents employ a replanning framework and regret minimization over a set of actions, which correspond to different homotopic paths. By associating a cost to each trajectory, a motion coordination game arises. Regret minimization is argued as an appropriate technique, as agents do not have any knowledge of other agents cost functions. This work outlines a methodology for minimizing the regret of actions in a computationally efficient way. Initial simulation results involving pairs of mobile agents show indications that the proposed framework can improve the choice of non-colliding paths compared to a greedy choice by the agents, without increasing any information requirements.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This paper considers a game-theoretic framework for motion coordination challenges. The focus of this work is to minimize the number of interactions agents have when moving through an environment. In particular, agents employ a replanning framework and regret minimization over a set of actions, which correspond to different homotopic paths. By associating a cost to each trajectory, a motion coordination game arises. Regret minimization is argued as an appropriate technique, as agents do not have any knowledge of other agents cost functions. This work outlines a methodology for minimizing the regret of actions in a computationally efficient way. Initial simulation results involving pairs of mobile agents show indications that the proposed framework can improve the choice of non-colliding paths compared to a greedy choice by the agents, without increasing any information requirements. |
Krontiris, A; Luna, R; Bekris, K From Feasibility Tests to Path Planners for Multi-Agent Pathfinding Conference Symposium on Combinatorial Search (SoCS), Leavenworth, WA, USA, 2013. @conference{Krontiris:2013aa, title = {From Feasibility Tests to Path Planners for Multi-Agent Pathfinding}, author = {A Krontiris and R Luna and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/pmgsolver_socs13.pdf}, year = {2013}, date = {2013-07-01}, booktitle = {Symposium on Combinatorial Search (SoCS)}, address = {Leavenworth, WA, USA}, abstract = {Multi-agent pathfinding is an important challenge that relates to combinatorial search and has many applications, including warehouse management, robotics and computer games. Finding an optimal solution is NP-hard and raises scalability issues for optimal solvers. Interestingly, however, it is possible to check in linear time if an instance is solvable or not. These linear-time feasibility tests can be extended to provide path planners but to the best of the authorstextquoteright knowledge no such solver has been provided. This work first describes a path planner that is inspired by linear-time feasibility tests for multi-agent pathfinding. Initial experiments indicated reasonable scalability but worse path quality relative to existing suboptimal solutions. This led to the development of an algorithm that achieves both efficient running time and path quality relative to the alternatives and which finds a solution on available benchmarks. The paper outlines the relation of the final method to the feasibility tests and existing suboptimal planners. Experimental results evaluate the different algorithms, including an optimal solver.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Multi-agent pathfinding is an important challenge that relates to combinatorial search and has many applications, including warehouse management, robotics and computer games. Finding an optimal solution is NP-hard and raises scalability issues for optimal solvers. Interestingly, however, it is possible to check in linear time if an instance is solvable or not. These linear-time feasibility tests can be extended to provide path planners but to the best of the authorstextquoteright knowledge no such solver has been provided. This work first describes a path planner that is inspired by linear-time feasibility tests for multi-agent pathfinding. Initial experiments indicated reasonable scalability but worse path quality relative to existing suboptimal solutions. This led to the development of an algorithm that achieves both efficient running time and path quality relative to the alternatives and which finds a solution on available benchmarks. The paper outlines the relation of the final method to the feasibility tests and existing suboptimal planners. Experimental results evaluate the different algorithms, including an optimal solver. |
Dobson, A; Bekris, K Improving Sparse Roadmap Spanners Conference IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany, 2013. @conference{Dobson:2013ac, title = {Improving Sparse Roadmap Spanners}, author = {A Dobson and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/spars2.pdf}, year = {2013}, date = {2013-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Karlsruhe, Germany}, abstract = {Roadmap spanners have been proposed as a way to acquire sparse data structures that can efficiently answer path queries in continuous spaces with probabilistic completeness and asymptotic near-optimality guarantees. The current construction method, named SPARS, provides these properties by constructing in parallel a relatively dense asymptotically-optimal roadmap based on PRM*. This feature limits the methodtextquoterights benefits. This paper shows that it is possible to relax the conditions under which a sample is added to the spanner and provide the desired properties, while not requiring the use of a dense graph. A key aspect of SPARS is that the probability of adding nodes to the roadmap goes to zero over increasing iterations, which is maintained in the proposed extension. The paper describes the new algorithm, argues its theoretical properties and evaluates it against PRM* and the original SPARS algorithm. The experimental results suggest that the memory requirements of the method upon construction are dramatically reduced, while it returns competitive quality paths for the same construction time with PRM*. There is a small sacrifice in the size of the final spanner relative to SPARS but the new method still returns graphs orders of magnitudes smaller than PRM*, leading to very efficient online query resolution.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Roadmap spanners have been proposed as a way to acquire sparse data structures that can efficiently answer path queries in continuous spaces with probabilistic completeness and asymptotic near-optimality guarantees. The current construction method, named SPARS, provides these properties by constructing in parallel a relatively dense asymptotically-optimal roadmap based on PRM*. This feature limits the methodtextquoterights benefits. This paper shows that it is possible to relax the conditions under which a sample is added to the spanner and provide the desired properties, while not requiring the use of a dense graph. A key aspect of SPARS is that the probability of adding nodes to the roadmap goes to zero over increasing iterations, which is maintained in the proposed extension. The paper describes the new algorithm, argues its theoretical properties and evaluates it against PRM* and the original SPARS algorithm. The experimental results suggest that the memory requirements of the method upon construction are dramatically reduced, while it returns competitive quality paths for the same construction time with PRM*. There is a small sacrifice in the size of the final spanner relative to SPARS but the new method still returns graphs orders of magnitudes smaller than PRM*, leading to very efficient online query resolution. |
Marble, J; Bekris, K Asymptotically Near-Optimal Planning with Probabilistic Roadmap Spanners Journal Article IEEE Transactions on Robotics, 29 , pp. 432–444, 2013. @article{Marble:2013aa, title = {Asymptotically Near-Optimal Planning with Probabilistic Roadmap Spanners}, author = {J Marble and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/near_optimal.pdf}, year = {2013}, date = {2013-01-01}, journal = {IEEE Transactions on Robotics}, volume = {29}, pages = {432--444}, abstract = {Asymptotically optimal motion planners guarantee that solutions approach optimal as more iterations are performed. A recently proposed roadmap-based method, the PRM* approach, provides this desirable property and minimizes the computational cost of generating the roadmap. Even for this method, however, the roadmap can be slow to construct and quickly grows too large for storage or fast online query resolution, especially for relatively high-dimensional instances. In graph theory there are algorithms that produce sparse subgraphs, known as graph spanners, which guarantee near-optimal paths. This work proposes different alternatives for interleaving graph spanners with the asymptotically optimal PRM* algorithm. The first alternative follows a sequential approach, where a graph spanner algorithm is applied on the output roadmap of PRM*. The second one is an incremental method, where during the construction of the roadmap, certain edges are not considered as they are not necessary for the construction of a roadmap spanner. The result in both cases is an asymptotically near-optimal motion planning solution. Theoretical analysis and experiments performed on typical, geometric motion planning instances show that large reductions in construction time, roadmap density, and online query resolution time can be achieved with a small sacrifice of path quality through roadmap spanners.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Asymptotically optimal motion planners guarantee that solutions approach optimal as more iterations are performed. A recently proposed roadmap-based method, the PRM* approach, provides this desirable property and minimizes the computational cost of generating the roadmap. Even for this method, however, the roadmap can be slow to construct and quickly grows too large for storage or fast online query resolution, especially for relatively high-dimensional instances. In graph theory there are algorithms that produce sparse subgraphs, known as graph spanners, which guarantee near-optimal paths. This work proposes different alternatives for interleaving graph spanners with the asymptotically optimal PRM* algorithm. The first alternative follows a sequential approach, where a graph spanner algorithm is applied on the output roadmap of PRM*. The second one is an incremental method, where during the construction of the roadmap, certain edges are not considered as they are not necessary for the construction of a roadmap spanner. The result in both cases is an asymptotically near-optimal motion planning solution. Theoretical analysis and experiments performed on typical, geometric motion planning instances show that large reductions in construction time, roadmap density, and online query resolution time can be achieved with a small sacrifice of path quality through roadmap spanners. |
Dobson, A; Bekris, K A Study on the Finite-Time Near-Optimality Properties of Sampling-Based Motion Planners Inproceedings 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, Tokyo, Japan, November 3-7, 2013, pp. 1236–1241, 2013. @inproceedings{Dobson:2013aa, title = {A Study on the Finite-Time Near-Optimality Properties of Sampling-Based Motion Planners}, author = {A Dobson and K Bekris}, url = {https://doi.org/10.1109/iros.2013.6696508}, doi = {10.1109/IROS.2013.6696508}, year = {2013}, date = {2013-01-01}, booktitle = {2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, Tokyo, Japan, November 3-7, 2013}, pages = {1236--1241}, crossref = {DBLP:conf/iros/2013}, abstract = {Sampling-based algorithms have proven practical in solving motion planning challenges in relatively high-dimensional instances in geometrically complex workspaces. Early work focused on quickly returning feasible solutions. Only recently was it shown under which conditions these algorithms asymptotically return optimal or near-optimal solutions. These methods yield desired properties only in an asymptotic fashion, i.e., the properties are attained after infinite computation time. This work studies the finite-time properties of sampling-based planners in terms of path quality. The focus is on roadmap-based methods, due to their simplicity. This work illustrates that existing sampling-based planners which construct roadmaps in an asymptotically (near-)optimal manner exhibit a ``probably near-optimal'' property in finite time. This means that it is possible to compute a confidence value, i.e. a probability, regarding the existence of upper bounds for the length of the path returned by the roadmap as a function of the number of configuration space samples. This property can result in useful tools for determining existence of solutions and a probabilistic stopping criterion for PRM-like methods. These properties are validated through experimental trials.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Sampling-based algorithms have proven practical in solving motion planning challenges in relatively high-dimensional instances in geometrically complex workspaces. Early work focused on quickly returning feasible solutions. Only recently was it shown under which conditions these algorithms asymptotically return optimal or near-optimal solutions. These methods yield desired properties only in an asymptotic fashion, i.e., the properties are attained after infinite computation time. This work studies the finite-time properties of sampling-based planners in terms of path quality. The focus is on roadmap-based methods, due to their simplicity. This work illustrates that existing sampling-based planners which construct roadmaps in an asymptotically (near-)optimal manner exhibit a ``probably near-optimal'' property in finite time. This means that it is possible to compute a confidence value, i.e. a probability, regarding the existence of upper bounds for the length of the path returned by the roadmap as a function of the number of configuration space samples. This property can result in useful tools for determining existence of solutions and a probabilistic stopping criterion for PRM-like methods. These properties are validated through experimental trials. |
2012 |
Kimmel, A; Dobson, A; Littlefield, Z; Krontiris, A; Marble, J; Bekris, K Pracsys: An Extensible Architecture for Composing Motion Controllers and Planners Conference Simulation, Modeling and Programming for Autonomous Robots (SIMPAR), Tsukuba, Japan, 2012. @conference{Kimmel:2012ac, title = {Pracsys: An Extensible Architecture for Composing Motion Controllers and Planners}, author = {A Kimmel and A Dobson and Z Littlefield and A Krontiris and J Marble and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/pracsys.pdf}, year = {2012}, date = {2012-11-01}, booktitle = {Simulation, Modeling and Programming for Autonomous Robots (SIMPAR)}, address = {Tsukuba, Japan}, abstract = {This paper describes a software infrastructure for developing controllers and planners for robotic systems, referred here as PRACSYS. At the core of the software is the abstraction of a dynamical system, which, given a control, propagates its state forward in time. The platform simplifies the development of new controllers and planners and provides an extensible framework that allows complex interactions between one or many controllers, as well as motion planners. For instance, it is possible to compose many control layers over a physical system, to define multi-agent controllers that operate over many systems, to easily switch between different underlying controllers, and plan over controllers to achieve feedback-based planning. Such capabilities are especially useful for the control of hybrid and cyber-physical systems, which are important in many applications. The software is complementary and builds on top of many existing open-source contributions. It allows the use of different libraries as plugins for various modules, such as collision checking, physics-based simulation, visualization, and planning. This paper describes the overall architecture, explains important features and provides use-cases that evaluate aspects of the infrastructure.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper describes a software infrastructure for developing controllers and planners for robotic systems, referred here as PRACSYS. At the core of the software is the abstraction of a dynamical system, which, given a control, propagates its state forward in time. The platform simplifies the development of new controllers and planners and provides an extensible framework that allows complex interactions between one or many controllers, as well as motion planners. For instance, it is possible to compose many control layers over a physical system, to define multi-agent controllers that operate over many systems, to easily switch between different underlying controllers, and plan over controllers to achieve feedback-based planning. Such capabilities are especially useful for the control of hybrid and cyber-physical systems, which are important in many applications. The software is complementary and builds on top of many existing open-source contributions. It allows the use of different libraries as plugins for various modules, such as collision checking, physics-based simulation, visualization, and planning. This paper describes the overall architecture, explains important features and provides use-cases that evaluate aspects of the infrastructure. |
Dobson, A; Krontiris, A; Bekris, K Sparse Roadmap Spanners Conference Workshop on the Algorithmic Foundations of Robotics (WAFR), 2012. @conference{Dobson:2012ab, title = {Sparse Roadmap Spanners}, author = {A Dobson and A Krontiris and K Bekris}, url = {https://link.springer.com/chapter/10.1007/978-3-642-36279-8_17}, year = {2012}, date = {2012-06-01}, booktitle = {Workshop on the Algorithmic Foundations of Robotics (WAFR)}, pages = {279--296}, abstract = {Asymptotically optimal planners, such as PRM*, guarantee that solutions approach optimal as iterations increase. Roadmaps with this property, however, may grow too large. If optimality is relaxed, asymptotically near-optimal solutions produce sparser graphs by not including all edges. The idea stems from graph spanner algorithms, which produce sparse subgraphs that guarantee near-optimal paths. Existing asymptotically optimal and near-optimal planners, however, include all sampled configurations as roadmap nodes. Consequently, only infinite graphs have the desired properties. This work proposes an approach that provides the following asymptotic properties: (a) completeness, (b) near-optimality and (c) the probability of adding nodes to the spanner converges to zero as iterations increase. Thus, the method shows that finite-size data structures can have near-optimality properties. The method brings together ideas from various planners but deviates from existing integrations of prmstar with graph spanners. Simulations for rigid bodies show that the method indeed provides small roadmaps and results in faster query resolution. The rate of node addition is shown to decrease over time and the quality of solutions satisfies the theoretical bounds. Smoothing provides a more favorable comparison against alternatives with regards to path length.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Asymptotically optimal planners, such as PRM*, guarantee that solutions approach optimal as iterations increase. Roadmaps with this property, however, may grow too large. If optimality is relaxed, asymptotically near-optimal solutions produce sparser graphs by not including all edges. The idea stems from graph spanner algorithms, which produce sparse subgraphs that guarantee near-optimal paths. Existing asymptotically optimal and near-optimal planners, however, include all sampled configurations as roadmap nodes. Consequently, only infinite graphs have the desired properties. This work proposes an approach that provides the following asymptotic properties: (a) completeness, (b) near-optimality and (c) the probability of adding nodes to the spanner converges to zero as iterations increase. Thus, the method shows that finite-size data structures can have near-optimality properties. The method brings together ideas from various planners but deviates from existing integrations of prmstar with graph spanners. Simulations for rigid bodies show that the method indeed provides small roadmaps and results in faster query resolution. The rate of node addition is shown to decrease over time and the quality of solutions satisfies the theoretical bounds. Smoothing provides a more favorable comparison against alternatives with regards to path length. |
Dobson, A Provably Asymptotically Near-Optimal Motion Planning with Sparse Data Structures Masters Thesis 2012. @mastersthesis{Dobson:2012aa, title = {Provably Asymptotically Near-Optimal Motion Planning with Sparse Data Structures}, author = {A Dobson}, url = {https://people.cs.rutgers.edu/~kb572/pubs/DobsonMaster.pdf}, year = {2012}, date = {2012-06-01}, volume = {MS Thesis.}, abstract = {Asymptotically optimal planners, such as PRM*, guarantee that solutions approach optimal as iterations increase. Roadmaps with this property, however, may grow too large. If optimality is relaxed, asymptotically near-optimal solutions produce sparser graphs by not including all edges. The idea stems from graph spanner algorithms, which produce sparse subgraphs that guarantee near-optimal paths. Existing asymptotically optimal and near-optimal planners, however, include all sampled configurations as roadmap nodes. Consequently, only infinite graphs have the desired properties. This work proposes an approach that provides the following asymptotic properties: (a) completeness, (b) near-optimality and (c) the probability of adding nodes to the spanner roadmap converges to zero as iterations increase. Thus, the method suggests that finite-size data structures might have near-optimality properties. The method brings together ideas from various planners but deviates from existing integrations of PRM* with graph spanners. Simulations for rigid bodies show that the method indeed provides small roadmaps and results in faster query resolution. The rate of node addition is shown to decrease over time and the quality of solutions satisfies the theoretical bounds. Smoothing provides a more favorable comparison against alternatives with regards to path length.}, keywords = {}, pubstate = {published}, tppubtype = {mastersthesis} } Asymptotically optimal planners, such as PRM*, guarantee that solutions approach optimal as iterations increase. Roadmaps with this property, however, may grow too large. If optimality is relaxed, asymptotically near-optimal solutions produce sparser graphs by not including all edges. The idea stems from graph spanner algorithms, which produce sparse subgraphs that guarantee near-optimal paths. Existing asymptotically optimal and near-optimal planners, however, include all sampled configurations as roadmap nodes. Consequently, only infinite graphs have the desired properties. This work proposes an approach that provides the following asymptotic properties: (a) completeness, (b) near-optimality and (c) the probability of adding nodes to the spanner roadmap converges to zero as iterations increase. Thus, the method suggests that finite-size data structures might have near-optimality properties. The method brings together ideas from various planners but deviates from existing integrations of PRM* with graph spanners. Simulations for rigid bodies show that the method indeed provides small roadmaps and results in faster query resolution. The rate of node addition is shown to decrease over time and the quality of solutions satisfies the theoretical bounds. Smoothing provides a more favorable comparison against alternatives with regards to path length. |
Kimmel, A; Dobson, A; Bekris, K Maintaining Team Coherence under the Velocity Obstacle Framework Inproceedings International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2012, Valencia, Spain, June 4-8, 2012 (3 Volumes), pp. 247–256, 2012. @inproceedings{DBLP:conf/aamas/KimmelDB12, title = {Maintaining Team Coherence under the Velocity Obstacle Framework}, author = {A Kimmel and A Dobson and K Bekris}, url = {http://dl.acm.org/citation.cfm?id=2343611}, year = {2012}, date = {2012-06-01}, booktitle = {International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2012, Valencia, Spain, June 4-8, 2012 (3 Volumes)}, pages = {247--256}, crossref = {DBLP:conf/atal/2012}, abstract = {Many multi-agent applications may involve a notion of spatial coherence. For instance, simulations of virtual agents often need to model a coherent group or crowd. Alternatively, robots may prefer to stay within a pre-specified communication range. This paper proposes an extension of a decentralized, reactive collision avoidance framework, which defines obstacles in the velocity space, known as Velocity Obstacles (VOs), for coherent groups of agents. The extension, referred to in this work as a Loss of Communication Obstacle (LOCO), aims to maintain proximity among agents by imposing constraints in the velocity space and restricting the set of feasible controls. If the introduction of LOCOs results in a problem that is too restrictive, then the proximity constraints are relaxed in order to maintain collision avoidance. If agents break their proximity constraints, a method is applied to reconnect them. The approach is fast and integrates nicely with the Velocity Obstacle framework. It yields improved coherence for groups of robots connected through an input constraint graph that are moving with constant velocity. Simulated environments involving a single team moving among static obstacles, as well as multiple teams operating in the same environment, are considered in the experiments and evaluated for collisions, computational cost and proximity constraint maintenance. The experiments show that improved coherence is achieved while maintaining collision avoidance, at a small computational cost and path quality degradation.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Many multi-agent applications may involve a notion of spatial coherence. For instance, simulations of virtual agents often need to model a coherent group or crowd. Alternatively, robots may prefer to stay within a pre-specified communication range. This paper proposes an extension of a decentralized, reactive collision avoidance framework, which defines obstacles in the velocity space, known as Velocity Obstacles (VOs), for coherent groups of agents. The extension, referred to in this work as a Loss of Communication Obstacle (LOCO), aims to maintain proximity among agents by imposing constraints in the velocity space and restricting the set of feasible controls. If the introduction of LOCOs results in a problem that is too restrictive, then the proximity constraints are relaxed in order to maintain collision avoidance. If agents break their proximity constraints, a method is applied to reconnect them. The approach is fast and integrates nicely with the Velocity Obstacle framework. It yields improved coherence for groups of robots connected through an input constraint graph that are moving with constant velocity. Simulated environments involving a single team moving among static obstacles, as well as multiple teams operating in the same environment, are considered in the experiments and evaluated for collisions, computational cost and proximity constraint maintenance. The experiments show that improved coherence is achieved while maintaining collision avoidance, at a small computational cost and path quality degradation. |
Kimmel, A Composing Controllers for Team Coherence Maintenance with Collision Avoidance Masters Thesis 2012. @mastersthesis{Kimmel:2012aa, title = {Composing Controllers for Team Coherence Maintenance with Collision Avoidance}, author = {A Kimmel}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Kimmel_thesis.pdf}, year = {2012}, date = {2012-06-01}, volume = {MS Thesis.}, abstract = {Many multi-agent applications may involve a notion of spatial coherence. For in- stance, simulations of virtual agents often need to model a coherent group or crowd. Alternatively, robots may prefer to stay within a pre-specified communication range. This work proposes an extension of a decentralized, reactive collision avoidance frame- work, which defines obstacles in the velocity space, known as Velocity Obstacles (VOs), for coherent groups of agents. The extension, referred to in this work as a Loss of Communication Obstacle (LOCO), aims to maintain proximity among agents by imposing constraints in the velocity space and restricting the set of feasible controls. If the introduction of LOCOs results in a problem that is too restrictive, then the proximity constraints are relaxed in order to maintain collision avoidance. A weighted velocity selection scheme is utilized in order to steer agents towards their goals, as well as agents which are farther away and thus might be violating proximity constraints. The approach is fast and integrates nicely with the Velocity Obstacle framework. It is shown to yield improved coherence for groups of robots connected through an input constraint graph, while moving with constant velocity. The approach is evaluated for collisions, computational cost and proximity constraint maintenance through a series of simulated environments, which have single and multiple team variations. The experiments show that improved coherence is achieved while maintaining collision avoidance, at a small computational cost and path quality degradation. In order to experimentally validate new algorithms, such as the LOCO approach, having a software infrastructure capable of running a plethora of algorithms on many agents is needed. When moving from virtual agents to robotic systems, these algorithms take the form of a controller. Composing various controllers together to create a diverse testbed environment is also essential for the development process of new algorithms. Thus, this work additionally describes a software infrastructure for developing controllers and planners for robotic systems, referred to here as PRACSYS. At the core of the software is the abstraction of a dynamical system, which, given a control, propagates its state forward in time. The platform simplifies the development of new controllers and planners and provides an extensible framework that allows complex interactions between one or many controllers, as well as motion planners. For instance, it is possible to compose many control layers over a physical system, to define multi-agent controllers that operate over many systems, to easily switch between different underlying controllers, and plan over controllers to achieve feedback-based planning. Such capabilities are especially useful for the control of hybrid and cyber-physical systems, which are important in many applications. The software is complementary and builds on top of many existing open-source contributions. It allows the use of different libraries as plugins for various modules, such as collision checking, physics-based simulation, visualization, and planning. This work describes the overall architecture, explains important features and provides use-cases that evaluate aspects of the infrastructure.}, keywords = {}, pubstate = {published}, tppubtype = {mastersthesis} } Many multi-agent applications may involve a notion of spatial coherence. For in- stance, simulations of virtual agents often need to model a coherent group or crowd. Alternatively, robots may prefer to stay within a pre-specified communication range. This work proposes an extension of a decentralized, reactive collision avoidance frame- work, which defines obstacles in the velocity space, known as Velocity Obstacles (VOs), for coherent groups of agents. The extension, referred to in this work as a Loss of Communication Obstacle (LOCO), aims to maintain proximity among agents by imposing constraints in the velocity space and restricting the set of feasible controls. If the introduction of LOCOs results in a problem that is too restrictive, then the proximity constraints are relaxed in order to maintain collision avoidance. A weighted velocity selection scheme is utilized in order to steer agents towards their goals, as well as agents which are farther away and thus might be violating proximity constraints. The approach is fast and integrates nicely with the Velocity Obstacle framework. It is shown to yield improved coherence for groups of robots connected through an input constraint graph, while moving with constant velocity. The approach is evaluated for collisions, computational cost and proximity constraint maintenance through a series of simulated environments, which have single and multiple team variations. The experiments show that improved coherence is achieved while maintaining collision avoidance, at a small computational cost and path quality degradation. In order to experimentally validate new algorithms, such as the LOCO approach, having a software infrastructure capable of running a plethora of algorithms on many agents is needed. When moving from virtual agents to robotic systems, these algorithms take the form of a controller. Composing various controllers together to create a diverse testbed environment is also essential for the development process of new algorithms. Thus, this work additionally describes a software infrastructure for developing controllers and planners for robotic systems, referred to here as PRACSYS. At the core of the software is the abstraction of a dynamical system, which, given a control, propagates its state forward in time. The platform simplifies the development of new controllers and planners and provides an extensible framework that allows complex interactions between one or many controllers, as well as motion planners. For instance, it is possible to compose many control layers over a physical system, to define multi-agent controllers that operate over many systems, to easily switch between different underlying controllers, and plan over controllers to achieve feedback-based planning. Such capabilities are especially useful for the control of hybrid and cyber-physical systems, which are important in many applications. The software is complementary and builds on top of many existing open-source contributions. It allows the use of different libraries as plugins for various modules, such as collision checking, physics-based simulation, visualization, and planning. This work describes the overall architecture, explains important features and provides use-cases that evaluate aspects of the infrastructure. |
Fallah, N; Apostolopoulos, I; Bekris, K; Folmer, E ACM SIGCHI Conference on Human Factors in Computing Systems (CHI), Austin, TX, 2012. @conference{Fallah:2012aa, title = {The User As a Sensor: Navigating Users with Visual Impairments in Indoor Spaces Using Tactile Landmarks}, author = {N Fallah and I Apostolopoulos and K Bekris and E Folmer}, url = {http://www.cs.rutgers.edu/~kb572/pubs/userasasensor.pdf}, year = {2012}, date = {2012-05-01}, booktitle = {ACM SIGCHI Conference on Human Factors in Computing Systems (CHI)}, address = {Austin, TX}, abstract = {Indoor navigation systems for users who are visually impaired typically rely upon expensive physical augmentation of the environment or expensive sensing equipment; consequently few systems have been implemented. We present an indoor navigation system called Navatar that allows for localization and navigation by exploiting the physical characteristics of indoor environments, taking advantage of the unique sensing abilities of users with visual impairments, and minimalistic sensing achievable with low cost accelerometers available in smartphones. Particle filters are used to estimate the usertextquoterights location based on the accelerometer data as well as the user confirming the presence of anticipated tactile landmarks along the provided path. Navatar has a high possibility of large-scale deployment, as it only requires an annotated virtual representation of an indoor environment. A user study with six blind users determines the accuracy of the approach, collects qualitative experiences and identifies areas for improvement.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Indoor navigation systems for users who are visually impaired typically rely upon expensive physical augmentation of the environment or expensive sensing equipment; consequently few systems have been implemented. We present an indoor navigation system called Navatar that allows for localization and navigation by exploiting the physical characteristics of indoor environments, taking advantage of the unique sensing abilities of users with visual impairments, and minimalistic sensing achievable with low cost accelerometers available in smartphones. Particle filters are used to estimate the usertextquoterights location based on the accelerometer data as well as the user confirming the presence of anticipated tactile landmarks along the provided path. Navatar has a high possibility of large-scale deployment, as it only requires an annotated virtual representation of an indoor environment. A user study with six blind users determines the accuracy of the approach, collects qualitative experiences and identifies areas for improvement. |
Marble, J; Bekris, K Towards Small Asymptotically Near-Optimal Roadmaps Conference IEEE International Conference on Robotics and Automation (ICRA), Minnesota, MN, 2012. @conference{Marble:2012aa, title = {Towards Small Asymptotically Near-Optimal Roadmaps}, author = {J Marble and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/towards_small_optimal_roadmaps.pdf}, year = {2012}, date = {2012-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Minnesota, MN}, abstract = {An exciting recent development is the definition of sampling-based motion planners which guarantee asymptotic optimality. Nevertheless, roadmaps with this property may grow too large and lead to longer query resolution times. If optimality requirements are relaxed, existing asymptotically near-optimal solutions produce sparser graphs by removing redundant edges. Even these alternatives, however, include all sampled configurations as nodes in the roadmap. This work proposes a method, which can reject redundant samples but does provide asymptotic coverage and connectivity guarantees, while keeping local path costs low. Not adding every sample can significantly reduce the size of the final roadmap. An additional advantage is that it is possible to define a reasonable stopping criterion for the approach inspired by previous methods. To achieve these objectives, the proposed method maintains a dense graph that is used for evaluating the performance of the roadmap with regards to local path costs. Experimental results show that the method indeed provides small roadmaps, allowing for shorter query resolution times. Furthermore, smoothing the final paths results in an even more advantageous comparison against alternatives with regards to path quality.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } An exciting recent development is the definition of sampling-based motion planners which guarantee asymptotic optimality. Nevertheless, roadmaps with this property may grow too large and lead to longer query resolution times. If optimality requirements are relaxed, existing asymptotically near-optimal solutions produce sparser graphs by removing redundant edges. Even these alternatives, however, include all sampled configurations as nodes in the roadmap. This work proposes a method, which can reject redundant samples but does provide asymptotic coverage and connectivity guarantees, while keeping local path costs low. Not adding every sample can significantly reduce the size of the final roadmap. An additional advantage is that it is possible to define a reasonable stopping criterion for the approach inspired by previous methods. To achieve these objectives, the proposed method maintains a dense graph that is used for evaluating the performance of the roadmap with regards to local path costs. Experimental results show that the method indeed provides small roadmaps, allowing for shorter query resolution times. Furthermore, smoothing the final paths results in an even more advantageous comparison against alternatives with regards to path quality. |
Krontiris, A; Louis, S; Bekris, K Multi-Level Formation Roadmaps for Collision-Free Dynamic Shape Changes with Non-Holonomic Teams Conference IEEE International Conference on Robotics and Automation (ICRA - 2012), Minnesota, MN, 2012. @conference{Krontiris:2012aa, title = {Multi-Level Formation Roadmaps for Collision-Free Dynamic Shape Changes with Non-Holonomic Teams}, author = {A Krontiris and S Louis and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/ICRA12_2134_FI.pdf}, year = {2012}, date = {2012-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA - 2012)}, address = {Minnesota, MN}, abstract = {Teams of robots can utilize formations to accomplish a task, such as maximizing the observability of an environment while maintaining connectivity. In a cluttered space, however, it might be necessary to automatically change formation to avoid obstacles. This work proposes a path planning approach for non-holonomic robots, where a team dynamically switches formations to reach a goal without collisions. The method introduces a multi-level graph, which can be constructed offline. Each level corresponds to a different formation and edges between levels allow for formation transitions. All edges satisfy curvature bounds and clearance requirements from obstacles. During the online phase, the method returns a path for a virtual leader, as well as the points along the path where the team should switch formations. Individual agents can compute their controls using kinematic formation controllers that operate in curvilinear coordinates. The approach guarantees that it is feasible for the agents to follow the trajectory returned. Simulations show that the online cost of the approach is small. The method returns solutions that maximize the maintenance of a desired formation while allowing the team to rearrange its configuration in the presence of obstacles.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Teams of robots can utilize formations to accomplish a task, such as maximizing the observability of an environment while maintaining connectivity. In a cluttered space, however, it might be necessary to automatically change formation to avoid obstacles. This work proposes a path planning approach for non-holonomic robots, where a team dynamically switches formations to reach a goal without collisions. The method introduces a multi-level graph, which can be constructed offline. Each level corresponds to a different formation and edges between levels allow for formation transitions. All edges satisfy curvature bounds and clearance requirements from obstacles. During the online phase, the method returns a path for a virtual leader, as well as the points along the path where the team should switch formations. Individual agents can compute their controls using kinematic formation controllers that operate in curvilinear coordinates. The approach guarantees that it is feasible for the agents to follow the trajectory returned. Simulations show that the online cost of the approach is small. The method returns solutions that maximize the maintenance of a desired formation while allowing the team to rearrange its configuration in the presence of obstacles. |
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. |
Sajid, Q; Luna, R; Bekris, K Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives Inproceedings Fifth Annual Symposium on Combinatorial Search (SOCS), Niagara Falls, Ontario, Canada, 2012. @inproceedings{DBLP:conf/socs/SajidLB12, title = {Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives}, author = {Q Sajid and R Luna and K Bekris}, url = {https://ojs.aaai.org/index.php/SOCS/article/view/18243}, year = {2012}, date = {2012-01-01}, booktitle = {Fifth Annual Symposium on Combinatorial Search (SOCS)}, address = {Niagara Falls, Ontario, Canada}, crossref = {DBLP:conf/socs/2012}, abstract = {Multi-agent pathfinding is a challenging combinatorial problem that involves multiple agents moving on a graph from a set of initial nodes to a set of desired goals without inter-agent collisions. Searching the composite space of all agents has exponential complexity and does not scale well. Decoupled methods are more efficient but are generally incomplete. There are, however, polynomial time algorithms, which utilize single or few-agents primitives with completeness guarantees. One limitation of these alternatives is that the resulting solution is sequential, where only one agent moves at a time. Such solutions are of low quality when compared to methods where multiple agents can move simultaneously. This work proposes an algorithm for multi-agent pathfinding that utilizes similar single-agent primitives but allows all agents to move in parallel. The paper describes the algorithm and its properties. Experimental comparisons suggest that the resulting paths are considerably better than sequential ones, even after a post-processing, parallelization step, as well as solutions returned by decoupled and coupled alternatives. The experiments also suggest good scalability and competitive computational performance.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Multi-agent pathfinding is a challenging combinatorial problem that involves multiple agents moving on a graph from a set of initial nodes to a set of desired goals without inter-agent collisions. Searching the composite space of all agents has exponential complexity and does not scale well. Decoupled methods are more efficient but are generally incomplete. There are, however, polynomial time algorithms, which utilize single or few-agents primitives with completeness guarantees. One limitation of these alternatives is that the resulting solution is sequential, where only one agent moves at a time. Such solutions are of low quality when compared to methods where multiple agents can move simultaneously. This work proposes an algorithm for multi-agent pathfinding that utilizes similar single-agent primitives but allows all agents to move in parallel. The paper describes the algorithm and its properties. Experimental comparisons suggest that the resulting paths are considerably better than sequential ones, even after a post-processing, parallelization step, as well as solutions returned by decoupled and coupled alternatives. The experiments also suggest good scalability and competitive computational performance. |
2011 |
Krontiris, A; Bekris, K Using Minimal Communication to Improve Decentralized Conflict Resolution for Non-Holonomic Vehicles Conference IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-11), San Francisco, CA, 2011. @conference{Krontiris:2011ac, title = {Using Minimal Communication to Improve Decentralized Conflict Resolution for Non-Holonomic Vehicles}, author = {A Krontiris and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/min_communication_deconfliction_0.pdf}, year = {2011}, date = {2011-09-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-11)}, address = {San Francisco, CA}, abstract = {This work considers the problem of decentralized coordination between multiple non-holonomic vehicles, each navigating to a specified goal. By augmenting the Generalized Roundabout Policy (GRP), which guarantees collision avoidance, this paper improves the performance and liveness characteristics for such problems. These gains are achieved by integrating a second hybrid policy with GRP that updates the desired direction for each vehicle based on a dynamic priority scheme. In this scheme, minimalistic communication between vehicles is employed, such that information is periodically exchanged when changes in the high-level operating mode or prioritization occur. This information exchange is taking place only locally and data are exchanged only between neighboring vehicles. Additionally, each agent selects a control using only this local information and rules established by the two underlying hybrid automata. The proposed technique scales well due to its decentralized nature; the computational complexity depends on the maximum number of vehicles in communication range for a vehicle. This paper presents simulations which show that the proposed approach can solve problems faster than using GRP alone, as well as solve instances in which GRP fails to find a solution, with minimal communication and computational overhead.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This work considers the problem of decentralized coordination between multiple non-holonomic vehicles, each navigating to a specified goal. By augmenting the Generalized Roundabout Policy (GRP), which guarantees collision avoidance, this paper improves the performance and liveness characteristics for such problems. These gains are achieved by integrating a second hybrid policy with GRP that updates the desired direction for each vehicle based on a dynamic priority scheme. In this scheme, minimalistic communication between vehicles is employed, such that information is periodically exchanged when changes in the high-level operating mode or prioritization occur. This information exchange is taking place only locally and data are exchanged only between neighboring vehicles. Additionally, each agent selects a control using only this local information and rules established by the two underlying hybrid automata. The proposed technique scales well due to its decentralized nature; the computational complexity depends on the maximum number of vehicles in communication range for a vehicle. This paper presents simulations which show that the proposed approach can solve problems faster than using GRP alone, as well as solve instances in which GRP fails to find a solution, with minimal communication and computational overhead. |
Luna, R; Bekris, K Efficient and Complete Centralized Multi-Robot Path Planning Conference IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-11), San Francisco, CA, 2011. @conference{Luna:2011ab, title = {Efficient and Complete Centralized Multi-Robot Path Planning}, author = {R Luna and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/push_and_swap_iros.pdf}, year = {2011}, date = {2011-09-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-11)}, address = {San Francisco, CA}, abstract = {Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has exponential complexity and becomes computationally prohibitive for problems with just a few robots. This paper proposes an efficient and complete algorithm for solving a general class of multi-robot path planning problems, specifically those where there are at most n-2 robots in a connected graph of n vertices. This paper provides a full proof of completeness. The algorithm employs two primitives: "push", where a robot moves toward its goal until no progress can be made, and "swap", that allows two robots to swap positions without altering the position of any other robot. Additionally, this paper provides a smoothing procedure for improving solution quality. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique improves computation time and solution quality, while scaling to problems with 100s of robots, solving them in under 5 seconds.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has exponential complexity and becomes computationally prohibitive for problems with just a few robots. This paper proposes an efficient and complete algorithm for solving a general class of multi-robot path planning problems, specifically those where there are at most n-2 robots in a connected graph of n vertices. This paper provides a full proof of completeness. The algorithm employs two primitives: "push", where a robot moves toward its goal until no progress can be made, and "swap", that allows two robots to swap positions without altering the position of any other robot. Additionally, this paper provides a smoothing procedure for improving solution quality. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique improves computation time and solution quality, while scaling to problems with 100s of robots, solving them in under 5 seconds. |
Marble, J; Bekris, K Computing Spanners of Asymptotically Optimal Probabilistic Roadmaps Conference IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-11), San Francisco, CA, 2011. @conference{Marble:2011ab, title = {Computing Spanners of Asymptotically Optimal Probabilistic Roadmaps}, author = {J Marble and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/sequential_spanner.pdf}, year = {2011}, date = {2011-09-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-11)}, address = {San Francisco, CA}, abstract = {Asymptotically optimal motion planning algorithms guarantee solutions approach optimal as more iterations are performed. Nevertheless, roadmaps with this property can grow too large and unwieldy for fast online query resolution. In graph theory there are many algorithms that produce subgraphs, known as spanners, which have guarantees about path quality. Applying such an algorithm to a dense, asymptotically optimal roadmap produces a sparse, nao roadmap. Experiments performed on typical, geometric problems in SE(3) show that a large reduction in roadmap edges can be achieved with a small increase in path length. Online queries are answered much more quickly with similar results in terms of path quality. This also motivates future work that applies the technique incrementally so edges that won't increase path quality will never be added to the roadmap and won't be checked for collisions.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Asymptotically optimal motion planning algorithms guarantee solutions approach optimal as more iterations are performed. Nevertheless, roadmaps with this property can grow too large and unwieldy for fast online query resolution. In graph theory there are many algorithms that produce subgraphs, known as spanners, which have guarantees about path quality. Applying such an algorithm to a dense, asymptotically optimal roadmap produces a sparse, nao roadmap. Experiments performed on typical, geometric problems in SE(3) show that a large reduction in roadmap edges can be achieved with a small increase in path length. Online queries are answered much more quickly with similar results in terms of path quality. This also motivates future work that applies the technique incrementally so edges that won't increase path quality will never be added to the roadmap and won't be checked for collisions. |
Marble, J; Bekris, K Asymptotically Near-Optimal Is Good Enough for Motion Planning Conference Proc. of the 15th International Symposium on Robotics Research (ISRR-11), Flagstaff, AZ, 2011. @conference{Marble:2011aa, title = {Asymptotically Near-Optimal Is Good Enough for Motion Planning}, author = {J Marble and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/incremental_roadmap_spanner.pdf}, year = {2011}, date = {2011-08-01}, booktitle = {Proc. of the 15th International Symposium on Robotics Research (ISRR-11)}, address = {Flagstaff, AZ}, abstract = {Asymptotically optimal motion planning algorithms guarantee solutions approach optimal as more iterations are performed. Nevertheless, roadmaps with this property can be slow to construct and grow too large for storage or fast online query resolution. From graph theory, there are many algorithms that produce sparse subgraphs, known as spanners, which can guarantee near-optimal paths. In this work, a method for interleaving an incremental graph spanner algorithm with an asymptotically optimal motion planning algorithm is described. The result is an asymptotically near-optimal motion planning algorithm. Theoretical analysis and experiments performed on typical, geometric problems show that large reductions in construction time, roadmap density, and online query resolution time can be achieved with a small sacrifice of path quality. If smoothing is applied, the results are even more favorable for the near-optimal solution.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Asymptotically optimal motion planning algorithms guarantee solutions approach optimal as more iterations are performed. Nevertheless, roadmaps with this property can be slow to construct and grow too large for storage or fast online query resolution. From graph theory, there are many algorithms that produce sparse subgraphs, known as spanners, which can guarantee near-optimal paths. In this work, a method for interleaving an incremental graph spanner algorithm with an asymptotically optimal motion planning algorithm is described. The result is an asymptotically near-optimal motion planning algorithm. Theoretical analysis and experiments performed on typical, geometric problems show that large reductions in construction time, roadmap density, and online query resolution time can be achieved with a small sacrifice of path quality. If smoothing is applied, the results are even more favorable for the near-optimal solution. |
Luna, R; Bekris, K Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees Conference International Joint Conferences in Artificial Intelligence (IJCAI-11), Barcelona, Spain, 2011. @conference{Luna:2011ad, title = {Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees}, author = {R Luna and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/push_and_swap_ijcai.pdf}, year = {2011}, date = {2011-07-01}, booktitle = {International Joint Conferences in Artificial Intelligence (IJCAI-11)}, pages = {294--300}, address = {Barcelona, Spain}, abstract = {Cooperative path-finding can be abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. This paper proposes a fast algorithm that can provide completeness guarantees for a general class of problems without any assumptions about the graphtextquoterights topology. Specifically, the approach can address any solvable instance where there are at most n-2 agents in a graph of size n. The algorithm employs two primitives: a "push" operation where agents move towards their goals up to the point that no progress can be made, and a "swap" operation that allows two agents to swap positions without altering the configuration of other agents. Simulated experiments are provided on hard instances of cooperative path-finding, including comparisons against alternative methods. The results are favorable for the proposed algorithm and show that the technique scales to problems that require high levels of coordination, involving hundreds of agents.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Cooperative path-finding can be abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. This paper proposes a fast algorithm that can provide completeness guarantees for a general class of problems without any assumptions about the graphtextquoterights topology. Specifically, the approach can address any solvable instance where there are at most n-2 agents in a graph of size n. The algorithm employs two primitives: a "push" operation where agents move towards their goals up to the point that no progress can be made, and a "swap" operation that allows two agents to swap positions without altering the configuration of other agents. Simulated experiments are provided on hard instances of cooperative path-finding, including comparisons against alternative methods. The results are favorable for the proposed algorithm and show that the technique scales to problems that require high levels of coordination, involving hundreds of agents. |
Luna, R; Bekris, K Efficient and Complete Centralized Multi-Robot Path Planning Inproceedings Fourth Annual Symposium on Combinatorial Search, (SOCS), Castell de Cardona, Barcelona, Spain, 2011. @inproceedings{DBLP:conf/socs/LunaB11, title = {Efficient and Complete Centralized Multi-Robot Path Planning}, author = {R Luna and K Bekris}, url = {http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/view/4010}, year = {2011}, date = {2011-07-01}, booktitle = {Fourth Annual Symposium on Combinatorial Search, (SOCS)}, address = {Castell de Cardona, Barcelona, Spain}, crossref = {DBLP:conf/socs/2011}, abstract = {Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has exponential complexity and becomes computationally prohibitive for problems with just a few robots. This paper proposes an efficient and complete algorithm for solving a general class of multi-robot path planning problems, specifically those where there are at most n- 2 robots in a connected graph of n vertices. This paper provides a full proof of completeness. The algorithm employs two primitives: ``push'', where a robot moves toward its goal until no progress can be made, and ``swap'', that allows two robots to swap positions without altering the position of any other robot. Additionally, this paper provides a smoothing procedure for improving solution quality. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique improves computation time and solution quality, while scaling to problems with 100s of robots, solving them in under 5 seconds.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Multi-robot path planning is abstracted as the problem of computing a set of non-colliding paths on a graph for multiple robots. A naive search of the composite search space, although complete, has exponential complexity and becomes computationally prohibitive for problems with just a few robots. This paper proposes an efficient and complete algorithm for solving a general class of multi-robot path planning problems, specifically those where there are at most n- 2 robots in a connected graph of n vertices. This paper provides a full proof of completeness. The algorithm employs two primitives: ``push'', where a robot moves toward its goal until no progress can be made, and ``swap'', that allows two robots to swap positions without altering the position of any other robot. Additionally, this paper provides a smoothing procedure for improving solution quality. Simulated experiments compare the proposed approach with several other centralized and decoupled planners, and show that the proposed technique improves computation time and solution quality, while scaling to problems with 100s of robots, solving them in under 5 seconds. |
Li, Y; Bekris, K Learning Approximate Cost-To-Go Metrics to Improve Sampling-Based Motion Planning Conference International Conference on Robotics and Automation (ICRA), Shanghai, China, 2011. @conference{Li:2011aa, title = {Learning Approximate Cost-To-Go Metrics to Improve Sampling-Based Motion Planning}, author = {Y Li and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/approximate_costtogo_metrics_0.pdf}, year = {2011}, date = {2011-05-01}, booktitle = {International Conference on Robotics and Automation (ICRA)}, address = {Shanghai, China}, abstract = {Sampling-based planners have been shown to be effective by utilizing properties for quickly searching unexplored parts of the state space. Such desirable properties, however, depend on the availability of an appropriate metric, which is often difficult to be defined for important robotic systems, such as non-holonomic and underactuated ones. This paper investigates a general methodology to approximate optimum cost-to-go metrics by employing an offline learning phase in obstacle-free environments. The proposed method utilizes sampling to construct a dense graph that approximates the connectivity properties of the state space. This graph can be employed online to compute approximate distances between states using nearest neighbor queries and standard search algorithms, such as A*. Unfortunately, this process significantly increases the online cost of a sampling-based planner. The paper proceeds into investigating ways that allow the computationally efficient utilization of the learned metric during the planners online operation. One idea considered is the mapping of the sampled states into a higher-dimensional Euclidean space through multi-dimensional scaling so as to retain the relative distances represented by the sampled graph. Proof of concept simulations on a first-order car and on an illustrative example of an asymmetric state space, indicate that the approach has merit and can lead into more effective sampling-based algorithms.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Sampling-based planners have been shown to be effective by utilizing properties for quickly searching unexplored parts of the state space. Such desirable properties, however, depend on the availability of an appropriate metric, which is often difficult to be defined for important robotic systems, such as non-holonomic and underactuated ones. This paper investigates a general methodology to approximate optimum cost-to-go metrics by employing an offline learning phase in obstacle-free environments. The proposed method utilizes sampling to construct a dense graph that approximates the connectivity properties of the state space. This graph can be employed online to compute approximate distances between states using nearest neighbor queries and standard search algorithms, such as A*. Unfortunately, this process significantly increases the online cost of a sampling-based planner. The paper proceeds into investigating ways that allow the computationally efficient utilization of the learned metric during the planners online operation. One idea considered is the mapping of the sampled states into a higher-dimensional Euclidean space through multi-dimensional scaling so as to retain the relative distances represented by the sampled graph. Proof of concept simulations on a first-order car and on an illustrative example of an asymmetric state space, indicate that the approach has merit and can lead into more effective sampling-based algorithms. |
Krontiris, A; Louis, S; Bekris, K General Dynamic Formations for Non-Holonomic Systems along Planar Curvilinear Coordinates Conference IEEE International Conference on Robotics and Automation (ICRA), Shanghai, China, 2011. @conference{Krontiris:2011aa, title = {General Dynamic Formations for Non-Holonomic Systems along Planar Curvilinear Coordinates}, author = {A Krontiris and S Louis and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/general_curvilinear_formations.pdf}, year = {2011}, date = {2011-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Shanghai, China}, abstract = {This paper describes a general geometric method for planar formations of non-holonomic systems. The approach directly provides the feasible controls that each individual robot has to execute in order for the team to maintain the formation based on the controls of a reference agent. The reference agent can either be a virtual robot representing the entire team or a real leader-robot. In order to directly satisfy the non-holonomic constraints, the geometric reasoning takes place in curvilinear coordinates, defined by the curvature of the reference trajectory, instead of the typical rectilinear coordinates. The generality and contribution of the approach lies on the ability to define dynamic formations so as to smoothly switch between static ones, where the robots can change both of their relative coordinates as they move, and the ability to acquire a desired formation given an initial random configuration. Furthermore, it is possible to utilize this method to correct errors in the achieved configuration of the vehicles on the fly. Simulated experiments are presented to verify the correctness of the provided derivations.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This paper describes a general geometric method for planar formations of non-holonomic systems. The approach directly provides the feasible controls that each individual robot has to execute in order for the team to maintain the formation based on the controls of a reference agent. The reference agent can either be a virtual robot representing the entire team or a real leader-robot. In order to directly satisfy the non-holonomic constraints, the geometric reasoning takes place in curvilinear coordinates, defined by the curvature of the reference trajectory, instead of the typical rectilinear coordinates. The generality and contribution of the approach lies on the ability to define dynamic formations so as to smoothly switch between static ones, where the robots can change both of their relative coordinates as they move, and the ability to acquire a desired formation given an initial random configuration. Furthermore, it is possible to utilize this method to correct errors in the achieved configuration of the vehicles on the fly. Simulated experiments are presented to verify the correctness of the provided derivations. |
Luna, R Efficient Multi-Robot Path Planning in Discrete Spaces Masters Thesis University of Nevada, Reno, 2011. @mastersthesis{Luna:2011ac, title = {Efficient Multi-Robot Path Planning in Discrete Spaces}, author = {R Luna}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Luna_MS_2011.pdf}, year = {2011}, date = {2011-04-01}, volume = {MS Thesis}, address = {Reno}, school = {University of Nevada, Reno}, abstract = {Multi-robot path planning involves moving multiple robots from their unique starting positions to their unique goals in a common graph discretization. This problem appears in a variety of applications, including planetary exploration, warehouse management, intelligent transportation networks, assembly and disassembly, autonomous robotic mining, as well as computer games. Unfortunately, computing the optimal set of paths is NP-complete, making a naive search computationally prohibitive. Typical methods to solve this problem either consider the full composite robot, which guarantees optimality and completeness but suffers from exponential complexity, or decoupled approaches which compute very fast solutions by considering each robot individually, but suffer from deadlocks. The complexity versus completeness trade-off makes efficient coupled and decoupled solutions highly desirable, depending on the problem domain. This work presents three novel techniques for effectively solving multi-robot path planning instances. The first is related to intelligent transportation networks, and utilizes a distributed sensor network to compute and re-plan paths in a decoupled manner for hundreds of robots in real-time. The second algorithm is a centralized method that provides completeness for a sub-class of multi-robot problems by removing dependencies between robots using intermediate goals, and quickly solves the problem using a sequence of single robot paths. The third technique, also centralized, is complete for a more general class of problems, and employs sequential "push" and "swap" primitives to solve instances faster than state-of-the-art coupled and decoupled approaches.}, keywords = {}, pubstate = {published}, tppubtype = {mastersthesis} } Multi-robot path planning involves moving multiple robots from their unique starting positions to their unique goals in a common graph discretization. This problem appears in a variety of applications, including planetary exploration, warehouse management, intelligent transportation networks, assembly and disassembly, autonomous robotic mining, as well as computer games. Unfortunately, computing the optimal set of paths is NP-complete, making a naive search computationally prohibitive. Typical methods to solve this problem either consider the full composite robot, which guarantees optimality and completeness but suffers from exponential complexity, or decoupled approaches which compute very fast solutions by considering each robot individually, but suffer from deadlocks. The complexity versus completeness trade-off makes efficient coupled and decoupled solutions highly desirable, depending on the problem domain. This work presents three novel techniques for effectively solving multi-robot path planning instances. The first is related to intelligent transportation networks, and utilizes a distributed sensor network to compute and re-plan paths in a decoupled manner for hundreds of robots in real-time. The second algorithm is a centralized method that provides completeness for a sub-class of multi-robot problems by removing dependencies between robots using intermediate goals, and quickly solves the problem using a sequence of single robot paths. The third technique, also centralized, is complete for a more general class of problems, and employs sequential "push" and "swap" primitives to solve instances faster than state-of-the-art coupled and decoupled approaches. |
Apostolopoulos, I Integrating Minimalistic Localization and Navigation for People with Visual Impairments Masters Thesis University of Nevada, Reno, 2011. @mastersthesis{Apostolopoulos:2011aa, title = {Integrating Minimalistic Localization and Navigation for People with Visual Impairments}, author = {I Apostolopoulos}, url = {http://www.cs.rutgers.edu/~kb572/pubs/Apostolopoulos_MS_2011.pdf}, year = {2011}, date = {2011-04-01}, volume = {MS Thesis.}, school = {University of Nevada, Reno}, abstract = {Indoor localization and navigation systems for individuals with visual impairments (VI) typically rely upon extensive augmentation of the physical space or expensive sensors; thus, few systems have been adopted. This work describes a system able to guide people with VI through buildings using inexpensive sensors, such as accelerometers, which are available in portable devices like smart phones. This ap- proach introduces some challenges due to the limited computational power of the portable devices and the highly erroneous sensors. The method takes advantage of feedback from the human user, who confirms the presence of landmarks. The system calculates the location of the user in real time and uses it to provide audio instructions on how to reach the desired destination. A first set of experiments suggested that the accuracy of the localization depends on the type of directions provided and the availability of good transition and observation models that describe the user's behavior. During this initial set of experiments, the system was not executed in real time so the approach had to be improved. Towards an improved version of the method, a significant amount of computation was transferred offline in order to speed up the system's online execution. Inspired by results in multi-model estimation, this work employs multiple particle filters, where each one uses a different assumption for the user's average step length. This helps to adaptively estimate the value of this pa- rameter on the fly. The system simultaneously estimates the step length of the user, as it varies between different people, from path to path, and during the execution of the path. Experiments are presented that evaluate the accuracy of the location estimation process and of the integrated direction provision method. Sighted people, that were blindfolded, participated in these experiments.}, keywords = {}, pubstate = {published}, tppubtype = {mastersthesis} } Indoor localization and navigation systems for individuals with visual impairments (VI) typically rely upon extensive augmentation of the physical space or expensive sensors; thus, few systems have been adopted. This work describes a system able to guide people with VI through buildings using inexpensive sensors, such as accelerometers, which are available in portable devices like smart phones. This ap- proach introduces some challenges due to the limited computational power of the portable devices and the highly erroneous sensors. The method takes advantage of feedback from the human user, who confirms the presence of landmarks. The system calculates the location of the user in real time and uses it to provide audio instructions on how to reach the desired destination. A first set of experiments suggested that the accuracy of the localization depends on the type of directions provided and the availability of good transition and observation models that describe the user's behavior. During this initial set of experiments, the system was not executed in real time so the approach had to be improved. Towards an improved version of the method, a significant amount of computation was transferred offline in order to speed up the system's online execution. Inspired by results in multi-model estimation, this work employs multiple particle filters, where each one uses a different assumption for the user's average step length. This helps to adaptively estimate the value of this pa- rameter on the fly. The system simultaneously estimates the step length of the user, as it varies between different people, from path to path, and during the execution of the path. Experiments are presented that evaluate the accuracy of the location estimation process and of the integrated direction provision method. Sighted people, that were blindfolded, participated in these experiments. |
Krontiris, A Improving Controllers for Formations and Deconfliction among Non-Holonomic Vehicles Masters Thesis University of Nevada, Reno, 2011. @mastersthesis{Krontiris:2011ab, title = {Improving Controllers for Formations and Deconfliction among Non-Holonomic Vehicles}, author = {A Krontiris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/tdk_thesis.pdf}, year = {2011}, date = {2011-04-01}, volume = {MS Thesis.}, school = {University of Nevada, Reno}, abstract = {The first contribution of this work corresponds to a computationally efficient geometric method for simulating formations of systems with non-holonomic motion constraints. The proposed geometric reasoning takes place in curvilinear coordinates, which are defined by the curvature of the leadertextquoterights reference trajectory, in order to directly satisfy the constraints, instead of the typical rectilinear coordinates. The approach directly provides the feasible controls that each individual robot has to execute for the team to maintain the formation based on the controls of a reference agent, either a real leader or a virtual one. The methodtextquoterights generality lies on the ability to define dynamic formations so as to smoothly switch between different configurations, where the robots can change both of their relative curvilinear coordinates as they move. It is also possible to acquire a desired formation given an initial random configuration. Simulation results are provided that illustrate the feasibility of the approach. The second contribution corresponds to a motion coordination algorithm, where multiple non-holonomic vehicles are steered in a decentralized manner between assigned start and goal configurations so as to avoid collisions. The approach builds on top of a hybrid control law, known as Generalized Roundabout Policy, which ensures safety, without any communication between the robots. The focus of this work is on improving the performance and liveness features for such problems. Towards this objective, a new hybrid policy that updates the desired direction for each vehicle based on a dynamic priority scheme is proposed. Minimal communication between the various vehicles is employed for the dynamic priority scheme, where vehicles occasionally exchange information with their neighbors. The proposed method can solve decentralized motion coordination problems both faster and with less assumptions, that the Generalized Roundabout Policy, as suggested by simulations presented in this thesis.}, keywords = {}, pubstate = {published}, tppubtype = {mastersthesis} } The first contribution of this work corresponds to a computationally efficient geometric method for simulating formations of systems with non-holonomic motion constraints. The proposed geometric reasoning takes place in curvilinear coordinates, which are defined by the curvature of the leadertextquoterights reference trajectory, in order to directly satisfy the constraints, instead of the typical rectilinear coordinates. The approach directly provides the feasible controls that each individual robot has to execute for the team to maintain the formation based on the controls of a reference agent, either a real leader or a virtual one. The methodtextquoterights generality lies on the ability to define dynamic formations so as to smoothly switch between different configurations, where the robots can change both of their relative curvilinear coordinates as they move. It is also possible to acquire a desired formation given an initial random configuration. Simulation results are provided that illustrate the feasibility of the approach. The second contribution corresponds to a motion coordination algorithm, where multiple non-holonomic vehicles are steered in a decentralized manner between assigned start and goal configurations so as to avoid collisions. The approach builds on top of a hybrid control law, known as Generalized Roundabout Policy, which ensures safety, without any communication between the robots. The focus of this work is on improving the performance and liveness features for such problems. Towards this objective, a new hybrid policy that updates the desired direction for each vehicle based on a dynamic priority scheme is proposed. Minimal communication between the various vehicles is employed for the dynamic priority scheme, where vehicles occasionally exchange information with their neighbors. The proposed method can solve decentralized motion coordination problems both faster and with less assumptions, that the Generalized Roundabout Policy, as suggested by simulations presented in this thesis. |
Luna, R; Bekris, K An Efficient and Complete Approach for Cooperative Path-Finding Inproceedings Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011. @inproceedings{Luna:2011aa, title = {An Efficient and Complete Approach for Cooperative Path-Finding}, author = {R Luna and K Bekris}, url = {https://cdn.aaai.org/ojs/8041/8041-13-11569-1-2-20201228.pdf}, year = {2011}, date = {2011-01-01}, booktitle = {Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence}, crossref = {DBLP:conf/aaai/2011}, abstract = {Cooperative path-finding requires the computation of a set of compatible paths for multiple agents operating on a discrete roadmap. The goal of this problem is to navigate each agent to their unique target vertices without simultaneously occupying the same vertex or edge in the roadmap as any other agent. Such a formulation has applications in warehouse management, transportation networks, (dis)assembly, robotic mining, space exploration, and computer games. The problem of cooperative path-finding has been extensively studied in the literature, with coupled techniques that attempt to intelligently prune the search space into something more tractable while maintaining completeness, as well as decoupled techniques that plan for each agent independently and utilize sophisticated heuristics in order to avoid collisions along these paths. Coupled search techniques have been employed to separate large problems into fully coupled sub-problems (van den Berg et al. 2009), or segment the roadmap into smaller topologies with known characteristics (Ryan 2007) to solve the composite problem sequentially. Decoupled techniques employ heuristics that prioritize agents (Erdmann and Lozano-Perez 1986), or tune the velocities on precomputed paths (Kant and Zucker 1986). Modern approaches consider dynamic prioritization and windowed search (Silver 2005), or domain restriction to guarantee completeness and tractability (Wang and Botea 2009).}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Cooperative path-finding requires the computation of a set of compatible paths for multiple agents operating on a discrete roadmap. The goal of this problem is to navigate each agent to their unique target vertices without simultaneously occupying the same vertex or edge in the roadmap as any other agent. Such a formulation has applications in warehouse management, transportation networks, (dis)assembly, robotic mining, space exploration, and computer games. The problem of cooperative path-finding has been extensively studied in the literature, with coupled techniques that attempt to intelligently prune the search space into something more tractable while maintaining completeness, as well as decoupled techniques that plan for each agent independently and utilize sophisticated heuristics in order to avoid collisions along these paths. Coupled search techniques have been employed to separate large problems into fully coupled sub-problems (van den Berg et al. 2009), or segment the roadmap into smaller topologies with known characteristics (Ryan 2007) to solve the composite problem sequentially. Decoupled techniques employ heuristics that prioritize agents (Erdmann and Lozano-Perez 1986), or tune the velocities on precomputed paths (Kant and Zucker 1986). Modern approaches consider dynamic prioritization and windowed search (Silver 2005), or domain restriction to guarantee completeness and tractability (Wang and Botea 2009). |
2010 |
Grady, D K; Bekris, K; Kavraki, L Asynchronous Distributed Motion Planning with Safety Guarantees under Second-Order Dynamics Conference Workshop on Algorithmic Foundations of Robotics (WAFR), Singapore, 2010. @conference{Grady:2010fk, title = {Asynchronous Distributed Motion Planning with Safety Guarantees under Second-Order Dynamics}, author = {D K Grady and K Bekris and L Kavraki}, url = {http://www.cs.rutgers.edu/~kb572/pubs/asynchronous_coordination.pdf}, year = {2010}, date = {2010-12-01}, booktitle = {Workshop on Algorithmic Foundations of Robotics (WAFR)}, address = {Singapore}, abstract = {As robots become more versatile, they are increasingly found to operate together in the same environment where they must coordinate their motion in a distributed manner. Such operation does not present problems if the motion is quasi-static and collisions can be easily avoided. However, when the robots follow second-order dynamics, the problem becomes challenging even for a known environment. The setup in this work considers that each robot replans its own trajectory for the next replanning cycle. The planning process must guarantee the robot's safety by ensuring collision-free paths for the considered period and by not bringing the robot to states where collisions cannot be avoided in the future. This problem can be addressed through communication among the robots, but it becomes complicated when the replanning cycles of the different robots are not synchronized and the robots make planning decisions at different time instants. This paper shows how to guarantee the safe operation of multiple communicating second-order vehicles, whose replanning cycles do not coincide, through an asynchronous, distributed motion planning framework. The method is evaluated through simulations, where each robot is simulated on a different processor and communicates with its neighbors through message passing. The simulations confirm that the approach provides safety in scenarios with up to 48 robots with second-order dynamics in environments with obstacles, where collisions occur often without a safety framework.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } As robots become more versatile, they are increasingly found to operate together in the same environment where they must coordinate their motion in a distributed manner. Such operation does not present problems if the motion is quasi-static and collisions can be easily avoided. However, when the robots follow second-order dynamics, the problem becomes challenging even for a known environment. The setup in this work considers that each robot replans its own trajectory for the next replanning cycle. The planning process must guarantee the robot's safety by ensuring collision-free paths for the considered period and by not bringing the robot to states where collisions cannot be avoided in the future. This problem can be addressed through communication among the robots, but it becomes complicated when the replanning cycles of the different robots are not synchronized and the robots make planning decisions at different time instants. This paper shows how to guarantee the safe operation of multiple communicating second-order vehicles, whose replanning cycles do not coincide, through an asynchronous, distributed motion planning framework. The method is evaluated through simulations, where each robot is simulated on a different processor and communicates with its neighbors through message passing. The simulations confirm that the approach provides safety in scenarios with up to 48 robots with second-order dynamics in environments with obstacles, where collisions occur often without a safety framework. |
Luna, R; Bekris, K Network-Guided Multi-Robot Path Planning in Discrete Representations Conference IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Taipei, Taiwan, 2010. @conference{Luna:2010ab, title = {Network-Guided Multi-Robot Path Planning in Discrete Representations}, author = {R Luna and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/network_coordination_0.pdf}, year = {2010}, date = {2010-10-01}, booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, pages = {4596--4602}, address = {Taipei, Taiwan}, abstract = {This work deals with problems where multiple robots move on a roadmap guided by wireless nodes that form a communication network. The nodes compute paths for the robots within their communication range given information about robots only in their vicinity and communicating only with neighbors. The objective is to compute paths that are collisionfree, minimize the occurrence of deadlocks, as well as the time it takes to reach the robots goals. This paper formulates this challenge as a distributed constraint optimization problem. This formulation lends itself to a message-passing solution that guarantees collision-avoidance despite only local knowledge of the world by the network nodes. Simulations on benchmarks that cannot be solved with coupled or simple decoupled schemes are used to evaluate parameters and study the scalability, path quality and computational overhead of the approach.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } This work deals with problems where multiple robots move on a roadmap guided by wireless nodes that form a communication network. The nodes compute paths for the robots within their communication range given information about robots only in their vicinity and communicating only with neighbors. The objective is to compute paths that are collisionfree, minimize the occurrence of deadlocks, as well as the time it takes to reach the robots goals. This paper formulates this challenge as a distributed constraint optimization problem. This formulation lends itself to a message-passing solution that guarantees collision-avoidance despite only local knowledge of the world by the network nodes. Simulations on benchmarks that cannot be solved with coupled or simple decoupled schemes are used to evaluate parameters and study the scalability, path quality and computational overhead of the approach. |
Luna, R; Oyama, A; Bekris, K Network-Guided Multi-Robot Path Planning for Resource-Constrained Planetary Rovers Conference 10th International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS 2010), Sapporo, Japan, 2010. @conference{Luna:2010aa, title = {Network-Guided Multi-Robot Path Planning for Resource-Constrained Planetary Rovers}, author = {R Luna and A Oyama and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/network_coordination.pdf}, year = {2010}, date = {2010-08-01}, booktitle = {10th International Symposium on Artificial Intelligence, Robotics and Automation in Space (i-SAIRAS 2010)}, address = {Sapporo, Japan}, abstract = {Planetary exploration can benefit by the presence of multiple robots, which must be able to coordinate their paths and avoid collisions. This work proposes the use of a wireless network for the high-level path planning ofmultiple planetary rovers. In this setup, robots receive commands from the network nodes so as to maneuver between locations. Thus, robots can focus on tasks such as local obstacle avoidance and localization. This is desirable in space applications where robots are resource-constrained. Towards this objective, this paper presents a distributed path planning algorithm that is executed on the network nodes and provides collision-free paths for the robots on a precomputed roadmap. The method also aims to minimize the occurence of deadlocks and the time it takes for each robot to reach its goal. The approach follows a distributed constraint optimization formulation that lends itself to a decentralized, message-passing solution that is appropriate for network-guided navigation. Simulations are employed to evaluate the methods scalability and computational cost, as well as the quality of the resulting paths.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Planetary exploration can benefit by the presence of multiple robots, which must be able to coordinate their paths and avoid collisions. This work proposes the use of a wireless network for the high-level path planning ofmultiple planetary rovers. In this setup, robots receive commands from the network nodes so as to maneuver between locations. Thus, robots can focus on tasks such as local obstacle avoidance and localization. This is desirable in space applications where robots are resource-constrained. Towards this objective, this paper presents a distributed path planning algorithm that is executed on the network nodes and provides collision-free paths for the robots on a precomputed roadmap. The method also aims to minimize the occurence of deadlocks and the time it takes for each robot to reach its goal. The approach follows a distributed constraint optimization formulation that lends itself to a decentralized, message-passing solution that is appropriate for network-guided navigation. Simulations are employed to evaluate the methods scalability and computational cost, as well as the quality of the resulting paths. |
Bekris, K IEEE International Conference on Robotics and Automation (ICRA), Anchorage, AK, 2010. @workshop{Bekris:2010aa, title = {Avoiding Inevitable Collision States: Safety and Computational Efficiency in Replanning with Sampling-Based Algorithms}, author = {K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/ics_tradeoffs.pdf}, year = {2010}, date = {2010-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}, address = {Anchorage, AK}, abstract = {Safety concerns arise when planning for systems with dynamics among moving obstacles, where a collision-free trajectory leads to an Inevitable Collision State (ICS). Identifying whether a state is ICS, however, is computationally challenging. This has led to approximations, varying from conservative schemes, which never characterize an ICS as a safe state, to schemes with weaker guarantees but fast online resolution of an ICS query. The computational cost of the approach is critical in problems that require replanning. This report presents various alternatives for identifying whether a state is ICS from the related literature. It also discusses different ways for integrating such schemes with sampling-based planners in safe replanning frameworks so as to reduce the computational overhead of avoiding ICS.}, keywords = {}, pubstate = {published}, tppubtype = {workshop} } Safety concerns arise when planning for systems with dynamics among moving obstacles, where a collision-free trajectory leads to an Inevitable Collision State (ICS). Identifying whether a state is ICS, however, is computationally challenging. This has led to approximations, varying from conservative schemes, which never characterize an ICS as a safe state, to schemes with weaker guarantees but fast online resolution of an ICS query. The computational cost of the approach is critical in problems that require replanning. This report presents various alternatives for identifying whether a state is ICS from the related literature. It also discusses different ways for integrating such schemes with sampling-based planners in safe replanning frameworks so as to reduce the computational overhead of avoiding ICS. |
Li, Y; Bekris, K Balancing State-Space Coverage in Planning with Dynamics Conference IEEE International Conference on Robotics and Automation (ICRA10), Anchorage, AK, 2010. @conference{Li:2010aa, title = {Balancing State-Space Coverage in Planning with Dynamics}, author = {Y Li and K Bekris}, url = {http://www.cs.rutgers.edu/~kb572/pubs/balancing_statespace_coverage.pdf}, year = {2010}, date = {2010-05-01}, booktitle = {IEEE International Conference on Robotics and Automation (ICRA10)}, address = {Anchorage, AK}, abstract = {Sampling-based kinodynamic planners, such as the popular RRT algorithm, have been proposed as promising solutions to planning for systems with dynamics. Nevertheless, complex systems often raise significant challenges. In particular, the state-space exploration of sampling-based tree planners can be heavily biased towards a specific direction due to the presence of dynamics and underactuation. The premise of this paper is that it is possible to use statistical tools to learn quickly the effects of the constraints in the algorithm's state-space exploration during a training session. Then during the online operation of the algorithm, this information can be utilized so as to counter the undesirable bias due to the dynamics by appropriately adapting the control propagation step. The resulting method achieves a more balanced exploration of the state-space, resulting in faster solutions to planning challenges. The paper provides proof of concept experiments comparing against and improving upon the standard RRT using MATLAB simulations for (a) swinging up different versions of a 3-link Acrobot system with dynamics and (b) a second-order car-like system with significant drift.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } Sampling-based kinodynamic planners, such as the popular RRT algorithm, have been proposed as promising solutions to planning for systems with dynamics. Nevertheless, complex systems often raise significant challenges. In particular, the state-space exploration of sampling-based tree planners can be heavily biased towards a specific direction due to the presence of dynamics and underactuation. The premise of this paper is that it is possible to use statistical tools to learn quickly the effects of the constraints in the algorithm's state-space exploration during a training session. Then during the online operation of the algorithm, this information can be utilized so as to counter the undesirable bias due to the dynamics by appropriately adapting the control propagation step. The resulting method achieves a more balanced exploration of the state-space, resulting in faster solutions to planning challenges. The paper provides proof of concept experiments comparing against and improving upon the standard RRT using MATLAB simulations for (a) swinging up different versions of a 3-link Acrobot system with dynamics and (b) a second-order car-like system with significant drift. |