Rethinking Motion Generation for Robots Operating in Human Workspaces
This project develops a new motion planning paradigm for enabling robots to work in the presence of humans or cooperatively with humans as co-workers. The paradigm is intended to be fast, reactive, and responsive to the requirements that arise from human-robot interaction. It involves the definition and subsequent implementation of constraints that encode properties of human-aware paths and can be translated to cost functions characterizing path quality. New motion planners are proposed. The operation of these planners is guided by constraints and their corresponding cost functions. The planners produce paths compatible with a given set of constraints. A mechanism to incorporate user feedback on the relative importance of constraints is provided and semi-autonomous operation of the robots is considered. Importantly, the planners are embedded in a novel hybrid-systems framework that allows a robot to automatically switch among planners, and hence behaviors, in order to take into account different constraints and user preferences that arise in the context of semi-autonomous operation. Besides the actual implementation of the planners on specific platforms, this project also disseminates all developed libraries and planners. Compatibility will the Robot Operating System (ROS) is provided for wide adoption, while tutorials at major conferences are planned. The training of graduate students and female undergraduate students are a central focus of this project.
This work has been supported by grant NSF NRI 1317849.
Related Publications
- Y. Wang, A. A. R. Newaz, J. D. Hernández, S. Chaudhuri, and L. E. Kavraki, “Online Partial Conditional Plan Synthesis for POMDPs With Safe-Reachability Objectives:
Methods and Experiments,” IEEE Transactions on Automation Science and Engineering, vol. 18, pp. 932–945, Jul. 2021.
BibTeX
@article{wang2021-online-partial-conditional-plan-synthesis, title = {Online Partial Conditional Plan Synthesis for POMDPs With Safe-Reachability Objectives: Methods and Experiments}, author = {Wang, Yue and Newaz, Abdullah Al Redwan and Hernández, Juan David and Chaudhuri, Swarat and Kavraki, Lydia E.}, journal = {IEEE Transactions on Automation Science and Engineering}, month = jul, year = {2021}, volume = {18}, pages = {932--945}, doi = {10.1109/TASE.2021.3057111}, abstract = {The framework of partially observable Markov decision processes (POMDPs) offers a standard approach to model uncertainty in many robot tasks. Traditionally, POMDPs are formulated with optimality objectives. In this article, we study a different formulation of POMDPs with Boolean objectives. For robotic domains that require a correctness guarantee of accomplishing tasks, Boolean objectives are natural formulations. We investigate the problem of POMDPs with a common Boolean objective: safe reachability, requiring that the robot eventually reaches a goal state with a probability above a threshold while keeping the probability of visiting unsafe states below a different threshold. Our approach builds upon the previous work that represents POMDPs with Boolean objectives using symbolic constraints. We employ a satisfiability modulo theories (SMTs) solver to efficiently search for solutions, i.e., policies or conditional plans that specify the action to take contingent on every possible event. A full policy or conditional plan is generally expensive to compute. To improve computational efficiency, we introduce the notion of partial conditional plans that cover sampled events to approximate a full conditional plan. Our approach constructs a partial conditional plan parameterized by a replanning probability. We prove that the failure rate of the constructed partial conditional plan is bounded by the replanning probability. Our approach allows users to specify an appropriate bound on the replanning probability to balance efficiency and correctness. Moreover, we update this bound properly to quickly detect whether the current partial conditional plan meets the bound and avoid unnecessary computation. In addition, to further improve the efficiency, we cache partial conditional plans for sampled belief states and reuse these cached plans if possible. We validate our approach in several robotic domains. The results show that our approach outperforms a previous policy synthesis approach for POMDPs with safe-reachability objectives in these domains.}, publisher = {Institute of Electrical and Electronics Engineers (IEEE)} }DetailsAbstract
The framework of partially observable Markov decision processes (POMDPs) offers a standard approach to model uncertainty in many robot tasks. Traditionally, POMDPs are formulated with optimality objectives. In this article, we study a different formulation of POMDPs with Boolean objectives. For robotic domains that require a correctness guarantee of accomplishing tasks, Boolean objectives are natural formulations. We investigate the problem of POMDPs with a common Boolean objective: safe reachability, requiring that the robot eventually reaches a goal state with a probability above a threshold while keeping the probability of visiting unsafe states below a different threshold. Our approach builds upon the previous work that represents POMDPs with Boolean objectives using symbolic constraints. We employ a satisfiability modulo theories (SMTs) solver to efficiently search for solutions, i.e., policies or conditional plans that specify the action to take contingent on every possible event. A full policy or conditional plan is generally expensive to compute. To improve computational efficiency, we introduce the notion of partial conditional plans that cover sampled events to approximate a full conditional plan. Our approach constructs a partial conditional plan parameterized by a replanning probability. We prove that the failure rate of the constructed partial conditional plan is bounded by the replanning probability. Our approach allows users to specify an appropriate bound on the replanning probability to balance efficiency and correctness. Moreover, we update this bound properly to quickly detect whether the current partial conditional plan meets the bound and avoid unnecessary computation. In addition, to further improve the efficiency, we cache partial conditional plans for sampled belief states and reuse these cached plans if possible. We validate our approach in several robotic domains. The results show that our approach outperforms a previous policy synthesis approach for POMDPs with safe-reachability objectives in these domains. - S. D. Butler, M. Moll, and L. E. Kavraki, “A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and
Maximum Constraints,” in Proceedings of Algorithmic Foundations of Robotics XII, 2020, vol. 13, pp. 368–383.
BibTeX
@inproceedings{butler2020, title = {A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints}, author = {Butler, Steven D. and Moll, Mark and Kavraki, Lydia E.}, booktitle = {Proceedings of Algorithmic Foundations of Robotics XII}, month = may, year = {2020}, volume = {13}, pages = {368--383}, doi = {10.1007/978-3-030-43089-4_24}, abstract = {This paper presents a new algorithm which generates time-optimal trajectories given a path as input. The algorithm improves on previous approaches by generically handling a broader class of constraints on the dynamics. It eliminates the need for heuristics to select trajectory segments that are part of the optimal trajectory through an exhaustive, but efficient search. We also present an algorithm for computing all achievable velocities at the end of a path given an initial range of velocities. This algorithm effectively computes bundles of feasible trajectories for a given path and is a first step toward a new generation of more efficient kinodynamic motion planning algorithms. We present results for both algorithms using a simulated WAM arm with a Barrett hand subject to dynamics constraints on joint torque, joint velocity, momentum, and end effector velocity. The new algorithms are compared with a state-of-the-art alternative approach.}, editor = {Goldberg, K. and Abbeel, P. and Bekris, K. and Miller, L.}, publisher = {Springer} }DetailsAbstract
This paper presents a new algorithm which generates time-optimal trajectories given a path as input. The algorithm improves on previous approaches by generically handling a broader class of constraints on the dynamics. It eliminates the need for heuristics to select trajectory segments that are part of the optimal trajectory through an exhaustive, but efficient search. We also present an algorithm for computing all achievable velocities at the end of a path given an initial range of velocities. This algorithm effectively computes bundles of feasible trajectories for a given path and is a first step toward a new generation of more efficient kinodynamic motion planning algorithms. We present results for both algorithms using a simulated WAM arm with a Barrett hand subject to dynamics constraints on joint torque, joint velocity, momentum, and end effector velocity. The new algorithms are compared with a state-of-the-art alternative approach. - R. Luna, M. Moll, J. M. Badger, and L. E. Kavraki, “A Scalable Motion Planner for High-Dimensional Kinematic Systems,” International Journal of Robotics Research, vol. 39, no. 4, pp. 361–388, Apr. 2020.
BibTeX
@article{luna2020a-scalable-motion-planner-for-high-dimensional, title = {A Scalable Motion Planner for High-Dimensional Kinematic Systems}, author = {Luna, Ryan and Moll, Mark and Badger, Julia M. and Kavraki, Lydia E.}, journal = {International Journal of Robotics Research}, month = apr, year = {2020}, volume = {39}, pages = {361--388}, doi = {10.1177/0278364919890408}, abstract = {Sampling-based algorithms are known for their ability to effectively compute paths for high-dimensional robots in relatively short times. The same algorithms, however, are also notorious for poor quality solution paths, particularly as the dimensionality of the system grows. This work proposes a new probabilistically complete sampling-based algorithm, XXL, specially designed to plan the motions of high-dimensional mobile manipulators and related platforms. Using a novel sampling and connection strategy that guides a set of points mapped on the robot through the workspace, XXL scales to realistic manipulator platforms with dozens of joints by focusing the search of the robot's configuration space to specific degrees-of-freedom that affect motion in particular portions of the workspace. Simulated planning scenarios with the Robonaut2 platform and planar kinematic chains confirm that XXL exhibits competitive solution times relative to many existing works while obtaining execution-quality solution paths. Solutions from XXL are of comparable quality to costaware methods even though XXL does not explicitly optimize over any particular criteria, and are computed in an order of magnitude less time. Furthermore, observations about the performance of sampling-based algorithms on high-dimensional manipulator planning problems are presented that reveal a cautionary tale regarding two popular guiding heuristics used in these algorithms, indicating that a nearly random search may outperform the state-of-the-art when defining such heuristics is known to be difficult.}, issue = {4} }DetailsAbstract
Sampling-based algorithms are known for their ability to effectively compute paths for high-dimensional robots in relatively short times. The same algorithms, however, are also notorious for poor quality solution paths, particularly as the dimensionality of the system grows. This work proposes a new probabilistically complete sampling-based algorithm, XXL, specially designed to plan the motions of high-dimensional mobile manipulators and related platforms. Using a novel sampling and connection strategy that guides a set of points mapped on the robot through the workspace, XXL scales to realistic manipulator platforms with dozens of joints by focusing the search of the robot’s configuration space to specific degrees-of-freedom that affect motion in particular portions of the workspace. Simulated planning scenarios with the Robonaut2 platform and planar kinematic chains confirm that XXL exhibits competitive solution times relative to many existing works while obtaining execution-quality solution paths. Solutions from XXL are of comparable quality to costaware methods even though XXL does not explicitly optimize over any particular criteria, and are computed in an order of magnitude less time. Furthermore, observations about the performance of sampling-based algorithms on high-dimensional manipulator planning problems are presented that reveal a cautionary tale regarding two popular guiding heuristics used in these algorithms, indicating that a nearly random search may outperform the state-of-the-art when defining such heuristics is known to be difficult. - E. Vidal Garcia, M. Moll, N. Palomeras, J. D. Hernández, M. Carreras, and L. E. Kavraki, “Online Multilayered Motion Planning with Dynamic Constraints for Autonomous Underwater
Vehicles,” in IEEE International Conference on Robotics and Automation, 2019, pp. 8936–8942. (Top-3 finalist for best student paper award)
BibTeX
@inproceedings{vidal2019online-multilayered-motion-planning, title = {Online Multilayered Motion Planning with Dynamic Constraints for Autonomous Underwater Vehicles}, author = {Vidal Garcia, Eduard and Moll, Mark and Palomeras, Narcis and Hern{\'a}ndez, Juan David and Carreras, Marc and Kavraki, Lydia E.}, booktitle = {{IEEE} International Conference on Robotics and Automation}, month = may, year = {2019}, pages = {8936--8942}, doi = {10.1109/ICRA.2019.8794009}, abstract = {Underwater robots are subject to complex hydrodynamic forces. These forces define how the vehicle moves, so it is important to consider them when planning trajectories. However, performing motion planning considering the dynamics on the robot's onboard computer is challenging due to the limited computational resources available. In this paper an efficient motion planning framework for AUV is presented. By introducing a loosely coupled multilayered planning design, our framework is able to generate dynamically feasible trajectories while keeping the planning time low enough for online planning. First, a fast path planner operating in a lower-dimensional projected space computes a lead path from the start to the goal configuration. Then, the lead path is used to bias the sampling of a second motion planner, which takes into account all the dynamic constraints. Furthermore, we propose a strategy for online planning that saves computational resources by generating the final trajectory only up to a finite horizon. By using the finite horizon strategy together with the multilayered approach, the sampling of the second planner focuses on regions where good quality solutions are more likely to be found, significantly reducing the planning time. To provide strong safety guarantees our framework also incorporates the conservative approximations of ICS. Finally, we present simulations and experiments using a real underwater robot to demonstrate the capabilities of our framework.}, keyword = {planning from high-level specifications, kinodynamic systems}, note = {(Top-3 finalist for best student paper award)} }DetailsAbstract
Underwater robots are subject to complex hydrodynamic forces. These forces define how the vehicle moves, so it is important to consider them when planning trajectories. However, performing motion planning considering the dynamics on the robot’s onboard computer is challenging due to the limited computational resources available. In this paper an efficient motion planning framework for AUV is presented. By introducing a loosely coupled multilayered planning design, our framework is able to generate dynamically feasible trajectories while keeping the planning time low enough for online planning. First, a fast path planner operating in a lower-dimensional projected space computes a lead path from the start to the goal configuration. Then, the lead path is used to bias the sampling of a second motion planner, which takes into account all the dynamic constraints. Furthermore, we propose a strategy for online planning that saves computational resources by generating the final trajectory only up to a finite horizon. By using the finite horizon strategy together with the multilayered approach, the sampling of the second planner focuses on regions where good quality solutions are more likely to be found, significantly reducing the planning time. To provide strong safety guarantees our framework also incorporates the conservative approximations of ICS. Finally, we present simulations and experiments using a real underwater robot to demonstrate the capabilities of our framework. - J. D. Hernández, M. Moll, and L. E. Kavraki, “Lazy Evaluation of Goal Specifications Guided by Motion Planning,” in Proceedings of the IEEE International Conference on Robotics and Automation, 2019, pp. 944–950.
BibTeX
@inproceedings{hernandez2019lazy-evaluation-of-goal-specifications, title = {Lazy Evaluation of Goal Specifications Guided by Motion Planning}, author = {Hern{\'a}ndez, Juan David and Moll, Mark and Kavraki, Lydia E.}, booktitle = {Proceedings of the {IEEE} International Conference on Robotics and Automation}, month = may, year = {2019}, pages = {944--950}, doi = {10.1109/ICRA.2019.8793570}, abstract = {Nowadays robotic systems are expected to share workspaces and collaborate with humans. In such collaborative environments, an important challenge is to ground or establish the correct semantic interpretation of a human request. Once such an interpretation is available, the request must be translated into robot motion commands in order to complete the desired task. Nonetheless, there are some cases in which a human request cannot be grounded to a unique interpretation, thus leading to an ambiguous request. A simple example could be to ask a robot to ``put a cup on the table,'' where multiple cups are available. In order to deal with this kind of ambiguous request, and therefore, to make the human-robot interaction easy and as seamless as possible, we propose a delayed or lazy variable grounding. Our approach uses a motion planner, which considers and determines the feasibility of the different valid groundings by representing them with goal regions. This new approach also includes a reward-penalty strategy, which attempts to prioritize those goal regions that are more promising to provide a final solution. We validate our approach by solving requests with multiple valid alternatives in both simulation and real-world experiments.}, keyword = {planning from high-level specifications, fundamentals of sampling-based motion planning} }DetailsAbstract
Nowadays robotic systems are expected to share workspaces and collaborate with humans. In such collaborative environments, an important challenge is to ground or establish the correct semantic interpretation of a human request. Once such an interpretation is available, the request must be translated into robot motion commands in order to complete the desired task. Nonetheless, there are some cases in which a human request cannot be grounded to a unique interpretation, thus leading to an ambiguous request. A simple example could be to ask a robot to “put a cup on the table,” where multiple cups are available. In order to deal with this kind of ambiguous request, and therefore, to make the human-robot interaction easy and as seamless as possible, we propose a delayed or lazy variable grounding. Our approach uses a motion planner, which considers and determines the feasibility of the different valid groundings by representing them with goal regions. This new approach also includes a reward-penalty strategy, which attempts to prioritize those goal regions that are more promising to provide a final solution. We validate our approach by solving requests with multiple valid alternatives in both simulation and real-world experiments. - Y. Wang, S. Chaudhuri, and L. E. Kavraki, “Point-Based Policy Synthesis for POMDPs with Boolean and Quantitative Objectives,” IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1860–1867, Apr. 2019.
BibTeX
@article{wang2019point-based-policy, title = {Point-Based Policy Synthesis for {POMDP}s with Boolean and Quantitative Objectives}, author = {Wang, Yue and Chaudhuri, Swarat and Kavraki, Lydia E.}, journal = {IEEE Robotics and Automation Letters}, month = apr, year = {2019}, volume = {4}, number = {2}, pages = {1860--1867}, doi = {10.1109/LRA.2019.2898045}, abstract = {Effectively planning robust executions under uncertainty is critical for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling many robot applications under uncertainty. We study POMDPs with two kinds of objectives: (1) boolean objectives for a correctness guarantee of accomplishing tasks and (2) quantitative objectives for optimal behaviors. For robotic domains that require both correctness and optimality, POMDPs with boolean and quantitative objectives are natural formulations. We present a practical policy synthesis approach for POMDPs with boolean and quantitative objectives by combining policy iteration and policy synthesis for POMDPs with only boolean objectives. To improve efficiency, our approach produces approximate policies by performing the point-based backup on a small set of representative beliefs. Despite being approximate, our approach maintains validity (satisfying boolean objectives) and guarantees improved policies at each iteration before termination. Moreover, the error due to approximation is bounded. We evaluate our approach in several robotic domains. The results show that our approach produces good approximate policies that guarantee task completion.}, keyword = {planning from high-level specifications} }DetailsAbstract
Effectively planning robust executions under uncertainty is critical for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling many robot applications under uncertainty. We study POMDPs with two kinds of objectives: (1) boolean objectives for a correctness guarantee of accomplishing tasks and (2) quantitative objectives for optimal behaviors. For robotic domains that require both correctness and optimality, POMDPs with boolean and quantitative objectives are natural formulations. We present a practical policy synthesis approach for POMDPs with boolean and quantitative objectives by combining policy iteration and policy synthesis for POMDPs with only boolean objectives. To improve efficiency, our approach produces approximate policies by performing the point-based backup on a small set of representative beliefs. Despite being approximate, our approach maintains validity (satisfying boolean objectives) and guarantees improved policies at each iteration before termination. Moreover, the error due to approximation is bounded. We evaluate our approach in several robotic domains. The results show that our approach produces good approximate policies that guarantee task completion. - K. He, M. Lahijanian, L. E. Kavraki, and M. Y. Vardi, “Automated Abstraction of Manipulation Domains for Cost-Based Reactive Synthesis,” IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 285–292, Apr. 2019.
BibTeX
@article{he2019automated-abstraction-of-manipulation, title = {Automated Abstraction of Manipulation Domains for Cost-Based Reactive Synthesis}, author = {He, K. and Lahijanian, M. and Kavraki, L. E. and Vardi, Moshe Y.}, journal = {IEEE Robotics and Automation Letters}, month = apr, year = {2019}, volume = {4}, number = {2}, pages = {285--292}, doi = {10.1109/LRA.2018.2889191}, abstract = {When robotic manipulators perform high-level tasks in the presence of another agent, e.g., a human, they must have a strategy that considers possible interferences in order to guarantee task completion and efficient resource usage. One approach to generate such strategies is called reactive synthesis. Reactive synthesis requires an abstraction, which is a discrete structure that captures the domain in which the robot and other agents operate. Existing works discuss the construction of abstractions for mobile robots through space decomposition; however, they cannot be applied to manipulation domains due to the curse of dimensionality caused by the manipulator and the objects. In this work, we present the first algorithm for automatic abstraction construction for reactive synthesis of manipulation tasks. We focus on tasks that involve picking and placing objects with possible extensions to other types of actions. The abstraction also provides an upper bound on path-based costs for robot actions. We combine this abstraction algorithm with our reactive synthesis planner to construct correct-by-construction plans. We demonstrate the power of the framework on examples of a UR5 robot completing complex tasks in face of interferences by a human.}, keyword = {planning from high-level specifications} }DetailsAbstract
When robotic manipulators perform high-level tasks in the presence of another agent, e.g., a human, they must have a strategy that considers possible interferences in order to guarantee task completion and efficient resource usage. One approach to generate such strategies is called reactive synthesis. Reactive synthesis requires an abstraction, which is a discrete structure that captures the domain in which the robot and other agents operate. Existing works discuss the construction of abstractions for mobile robots through space decomposition; however, they cannot be applied to manipulation domains due to the curse of dimensionality caused by the manipulator and the objects. In this work, we present the first algorithm for automatic abstraction construction for reactive synthesis of manipulation tasks. We focus on tasks that involve picking and placing objects with possible extensions to other types of actions. The abstraction also provides an upper bound on path-based costs for robot actions. We combine this abstraction algorithm with our reactive synthesis planner to construct correct-by-construction plans. We demonstrate the power of the framework on examples of a UR5 robot completing complex tasks in face of interferences by a human. - Z. Kingston, M. Moll, and L. E. Kavraki, “Exploring Implicit Spaces for Constrained Sampling-Based Planning,” International Journal of Robotics Research, vol. 38, no. 10-11, pp. 1151–1178, 2019.
BibTeX
@article{kingston2019exploring-implicit-spaces-for-constrained, title = {Exploring Implicit Spaces for Constrained Sampling-Based Planning}, author = {Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.}, journal = {International Journal of Robotics Research}, year = {2019}, volume = {38}, number = {10-11}, pages = {1151--1178}, doi = {10.1177/0278364919868530}, abstract = {We present a review and reformulation of manifold constrained sampling-based motion planning within a unifying framework, IMACS (Implicit MAnifold Configuration Space). IMACS enables a broad class of motion planners to plan in the presence of manifold constraints, decoupling the choice of motion planning algorithm and method for constraint adherence into orthogonal choices. We show that implicit configuration spaces defined by constraints can be presented to sampling-based planners by addressing two key fundamental primitives: sampling and local planning, and that IMACS preserves theoretical properties of probabilistic completeness and asymptotic optimality through these primitives. Within IMACS, we implement projection- and continutation-based methods for constraint adherence, and demonstrate the framework on a range of planners with both methods in simulated and realistic scenarios. Our results show that the choice of method for constraint adherence depends on many factors and that novel combinations of planners and methods of constraint adherence can be more effective than previous approaches. Our implementation of IMACS is open source within the Open Motion Planning Library and is easily extended for novel planners and constraint spaces.}, keyword = {fundamentals of sampling-based motion planning} }DetailsAbstract
We present a review and reformulation of manifold constrained sampling-based motion planning within a unifying framework, IMACS (Implicit MAnifold Configuration Space). IMACS enables a broad class of motion planners to plan in the presence of manifold constraints, decoupling the choice of motion planning algorithm and method for constraint adherence into orthogonal choices. We show that implicit configuration spaces defined by constraints can be presented to sampling-based planners by addressing two key fundamental primitives: sampling and local planning, and that IMACS preserves theoretical properties of probabilistic completeness and asymptotic optimality through these primitives. Within IMACS, we implement projection- and continutation-based methods for constraint adherence, and demonstrate the framework on a range of planners with both methods in simulated and realistic scenarios. Our results show that the choice of method for constraint adherence depends on many factors and that novel combinations of planners and methods of constraint adherence can be more effective than previous approaches. Our implementation of IMACS is open source within the Open Motion Planning Library and is easily extended for novel planners and constraint spaces. - J. D. Hernández, E. Vidal, M. Moll, N. Palomeras, M. Carreras, and L. E. Kavraki, “Online Motion Planning for Unexplored Underwater Environments using Autonomous
Underwater Vehicles,” Journal of Field Robotics, vol. 36, no. 2, pp. 370–396, 2019.
BibTeX
@article{hernandez2019online-motion-planning-auvs, title = {Online Motion Planning for Unexplored Underwater Environments using Autonomous Underwater Vehicles}, author = {Hern{\'a}ndez, Juan David and Vidal, Eduard and Moll, Mark and Palomeras, Narc{\'i}s and Carreras, Marc and Kavraki, Lydia E.}, journal = {Journal of Field Robotics}, year = {2019}, volume = {36}, pages = {370--396}, doi = {10.1002/rob.21827}, abstract = {We present an approach to endow an autonomous underwater vehicle (AUV) with the capabilities to move through unexplored environments. To do so, we propose a computational framework for planning feasible and safe paths. The framework allows the vehicle to incrementally build a map of the surroundings, while simultaneously (re)planning a feasible path to a specified goal. To accomplish this, the framework considers motion constraints to plan feasible 3D paths, i.e., those that meet the vehicle’s motion capabilities. It also incorporates a risk function to avoid navigating close to nearby obstacles. Furthermore, the framework makes use of two strategies to ensure meeting online computation limitations. The first one is to reuse the last best known solution to eliminate time-consuming pruning routines. The second one is to opportunistically check the states’ risk of collision. To evaluate the proposed approach, we use the Sparus II performing autonomous missions in different real-world scenarios. These experiments consist of simulated and in-water trials for different tasks. The conducted tasks include the exploration of challenging scenarios such as artificial marine structures, natural marine structures, and confined natural environments. All these applications allow us to extensively prove the efficacy of the presented approach, not only for constant-depth missions (2D), but, more importantly, for situations in which the vehicle must vary its depth (3D).}, issue = {2}, keyword = {other robotics} }DetailsAbstract
We present an approach to endow an autonomous underwater vehicle (AUV) with the capabilities to move through unexplored environments. To do so, we propose a computational framework for planning feasible and safe paths. The framework allows the vehicle to incrementally build a map of the surroundings, while simultaneously (re)planning a feasible path to a specified goal. To accomplish this, the framework considers motion constraints to plan feasible 3D paths, i.e., those that meet the vehicle’s motion capabilities. It also incorporates a risk function to avoid navigating close to nearby obstacles. Furthermore, the framework makes use of two strategies to ensure meeting online computation limitations. The first one is to reuse the last best known solution to eliminate time-consuming pruning routines. The second one is to opportunistically check the states’ risk of collision. To evaluate the proposed approach, we use the Sparus II performing autonomous missions in different real-world scenarios. These experiments consist of simulated and in-water trials for different tasks. The conducted tasks include the exploration of challenging scenarios such as artificial marine structures, natural marine structures, and confined natural environments. All these applications allow us to extensively prove the efficacy of the presented approach, not only for constant-depth missions (2D), but, more importantly, for situations in which the vehicle must vary its depth (3D). - F. Lagriffoul, N. Dantam, C. Garrett, A. Akbari, S. Srivastava, and L. E. Kavraki, “Platform-Independent Benchmarks for Task and Motion Planning,” IEEE Robotics and Automation Letters, vol. 3, no. 4, pp. 3765–3772, Oct. 2018.
BibTeX
@article{lagriffoul2018tmp-benchmarks, title = {Platform-Independent Benchmarks for Task and Motion Planning}, author = {Lagriffoul, Fabien and Dantam, Neil and Garrett, Caelan and Akbari, Aliakbar and Srivastava, Siddharth and Kavraki, Lydia E.}, journal = {IEEE Robotics and Automation Letters}, month = oct, year = {2018}, volume = {3}, pages = {3765--3772}, doi = {10.1109/LRA.2018.2856701}, abstract = {We present the first platform-independent evaluation method for task and motion planning (TAMP). Previously point, various problems have been used to test individual planners for specific aspects of TAMP. However, no common set of metrics, formats, and problems have been accepted by the community. We propose a set of benchmark problems covering the challenging aspects of TAMP and a planner-independent specification format for these problems. Our objective is to better evaluate and compare TAMP planners, foster communication, and progress within the field, and lay a foundation to better understand this class of planning problems.}, issue = {4}, keyword = {planning from high-level specifications; uncertainty} }DetailsAbstract
We present the first platform-independent evaluation method for task and motion planning (TAMP). Previously point, various problems have been used to test individual planners for specific aspects of TAMP. However, no common set of metrics, formats, and problems have been accepted by the community. We propose a set of benchmark problems covering the challenging aspects of TAMP and a planner-independent specification format for these problems. Our objective is to better evaluate and compare TAMP planners, foster communication, and progress within the field, and lay a foundation to better understand this class of planning problems. - N. T. Dantam, S. Chaudhuri, and L. E. Kavraki, “The Task Motion Kit,” Robotics and Automation Magazine, vol. 25, no. 3, pp. 61–70, Sep. 2018.
BibTeX
@article{dantam2018task-motion-kit, title = {The Task Motion Kit}, author = {Dantam, Neil T. and Chaudhuri, Swarat and Kavraki, Lydia E.}, journal = {Robotics and Automation Magazine}, month = sep, year = {2018}, volume = {25}, number = {3}, pages = {61--70}, doi = {10.1109/MRA.2018.2815081}, abstract = {Robots require novel reasoning systems to achieve complex objectives in new environments. Daily activities in the physical world combine two types of reasoning: discrete and continuous. For example, to set the table, the robot must make discrete decisions about which and in what order to pick objects, and it must execute these decisions by computing continuous motions to reach objects or desired locations. Robotics has traditionally treated these issues in isolation. Reasoning about discrete events is referred to as task planning, while reasoning about and computing continuous motions is in the realm of motion planning. However, several recent works have shown that separating task planning from motion planning is problematic. This article provides an introduction to task-motion planning (TMP), this concept tightly couples task planning and motion planning, producing a sequence of steps that can actually be executed by a real robot. The implementation and use of an open-source TMP framework tht is adaptable to new robots is also discussed.}, keyword = {planning from high-level specifications}, publisher = {IEEE} }DetailsAbstract
Robots require novel reasoning systems to achieve complex objectives in new environments. Daily activities in the physical world combine two types of reasoning: discrete and continuous. For example, to set the table, the robot must make discrete decisions about which and in what order to pick objects, and it must execute these decisions by computing continuous motions to reach objects or desired locations. Robotics has traditionally treated these issues in isolation. Reasoning about discrete events is referred to as task planning, while reasoning about and computing continuous motions is in the realm of motion planning. However, several recent works have shown that separating task planning from motion planning is problematic. This article provides an introduction to task-motion planning (TMP), this concept tightly couples task planning and motion planning, producing a sequence of steps that can actually be executed by a real robot. The implementation and use of an open-source TMP framework tht is adaptable to new robots is also discussed. - Muhayyuddin, M. Moll, L. E. Kavraki, and J. Rosell, “Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain
Environments,” IEEE Robotics and Automation Letters, vol. 3, no. 2, pp. 712–719, Apr. 2018.
BibTeX
@article{muhayyuddin2018randomized-physics-based-motion-planning, title = {Randomized Physics-based Motion Planning for Grasping in Cluttered and Uncertain Environments}, author = {Muhayyuddin and Moll, Mark and Kavraki, Lydia E. and Rosell, Jan}, journal = {IEEE Robotics and Automation Letters}, month = apr, year = {2018}, volume = {3}, number = {2}, pages = {712--719}, doi = {10.1109/LRA.2017.2783445}, abstract = {Planning motions to grasp an object in cluttered and uncertain environments is a challenging task, particularly when a collision-free trajectory does not exist and objects obstructing the way are required to be carefully grasped and moved out. This paper takes a different approach and proposes to address this problem by using a randomized physics-based motion planner that permits robot-object and object-object interactions. The main idea is to avoid an explicit high-level reasoning of the task by providing the motion planner with a physics engine to evaluate possible complex multi-body dynamical interactions. The approach is able to solve the problem in complex scenarios, also considering uncertainty in the objects' pose and in the contact dynamics. The work enhances the state validity checker, the control sampler and the tree exploration strategy of a kinody- namic motion planner called KPIECE. The enhanced algorithm, called p-KPIECE, has been validated in simulation and with real experiments. The results have been compared with an ontological physics-based motion planner and with task and motion planning approaches, resulting in a significant improvement in terms of planning time, success rate and quality of the solution path.}, keyword = {kinodynamic systems} }DetailsAbstract
Planning motions to grasp an object in cluttered and uncertain environments is a challenging task, particularly when a collision-free trajectory does not exist and objects obstructing the way are required to be carefully grasped and moved out. This paper takes a different approach and proposes to address this problem by using a randomized physics-based motion planner that permits robot-object and object-object interactions. The main idea is to avoid an explicit high-level reasoning of the task by providing the motion planner with a physics engine to evaluate possible complex multi-body dynamical interactions. The approach is able to solve the problem in complex scenarios, also considering uncertainty in the objects’ pose and in the contact dynamics. The work enhances the state validity checker, the control sampler and the tree exploration strategy of a kinody- namic motion planner called KPIECE. The enhanced algorithm, called p-KPIECE, has been validated in simulation and with real experiments. The results have been compared with an ontological physics-based motion planner and with task and motion planning approaches, resulting in a significant improvement in terms of planning time, success rate and quality of the solution path. - Y. Wang, S. Chaudhuri, and L. E. Kavraki, “Online Partial Conditional Plan Synthesis for POMDPs with Safe-Reachability
Objectives,” in Workshop on the Algorithmic Foundations of Robotics, 2018.
BibTeX
@inproceedings{wang2018partial, title = {Online Partial Conditional Plan Synthesis for POMDPs with Safe-Reachability Objectives}, author = {Wang, Yue and Chaudhuri, Swarat and Kavraki, Lydia E.}, booktitle = {Workshop on the Algorithmic Foundations of Robotics}, year = {2018}, abstract = {The framework of Partially Observable Markov Decision Processes (POMDPs) offers a standard approach to model uncertainty in many robot tasks. Traditionally, POMDPs are formulated with optimality objectives. However, for robotic domains that require a correctness guarantee of accomplishing tasks, boolean objectives are natural formulations. We study POMDPs with a common boolean objective: safe-reachability, which requires that, with a probability above a threshold, the robot eventually reaches a goal state while keeping the probability of visiting unsafe states below a different threshold. The solutions to POMDPs are policies or conditional plans that specify the action to take contingent on every possible event. A full policy or conditional plan that covers all possible events is generally expensive to compute. To improve efficiency, we introduce the notion of partial conditional plans that only cover a sampled subset of all possible events. Our approach constructs a partial conditional plan parameterized by a replanning probability. We prove that the probability of the constructed partial conditional plan failing is bounded by the replanning probability. Our approach allows users to specify an appropriate bound on the replanning probability to balance efficiency and correctness. We validate our approach in several robotic domains. The results show that our approach outperforms a previous approach for POMDPs with safe-reachability objectives in these domains.}, keyword = {planning from high-level specifications; uncertainty} }DetailsAbstract
The framework of Partially Observable Markov Decision Processes (POMDPs) offers a standard approach to model uncertainty in many robot tasks. Traditionally, POMDPs are formulated with optimality objectives. However, for robotic domains that require a correctness guarantee of accomplishing tasks, boolean objectives are natural formulations. We study POMDPs with a common boolean objective: safe-reachability, which requires that, with a probability above a threshold, the robot eventually reaches a goal state while keeping the probability of visiting unsafe states below a different threshold. The solutions to POMDPs are policies or conditional plans that specify the action to take contingent on every possible event. A full policy or conditional plan that covers all possible events is generally expensive to compute. To improve efficiency, we introduce the notion of partial conditional plans that only cover a sampled subset of all possible events. Our approach constructs a partial conditional plan parameterized by a replanning probability. We prove that the probability of the constructed partial conditional plan failing is bounded by the replanning probability. Our approach allows users to specify an appropriate bound on the replanning probability to balance efficiency and correctness. We validate our approach in several robotic domains. The results show that our approach outperforms a previous approach for POMDPs with safe-reachability objectives in these domains. - Y. Wang, S. Chaudhuri, and L. E. Kavraki, “Bounded Policy Synthesis for POMDPs with Safe-Reachability Objectives,” in Proceedings of the 17th International Conference on Autonomous Agents and
Multiagent Systems, Stockholm, Sweden, 2018, pp. 238–246.
BibTeX
@inproceedings{wang2018bounded-policy-synthesis, title = {Bounded Policy Synthesis for {POMDP}s with Safe-Reachability Objectives}, author = {Wang, Yue and Chaudhuri, Swarat and Kavraki, Lydia E.}, booktitle = {Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems}, year = {2018}, pages = {238--246}, abstract = {Planning robust executions under uncertainty is a fundamental challenge for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling uncertainty in many applications. In this work, we study POMDPs with safe-reachability objectives, which require that with a probability above some threshold, a goal state is eventually reached while keeping the probability of visiting unsafe states below some threshold. This POMDP formulation is different from the traditional POMDP models with optimality objectives and we show that in some cases, POMDPs with safe-reachability objectives can provide a better guarantee of both safety and reachability than the existing POMDP models through an example. A key algorithmic problem for POMDPs is policy synthesis, which requires reasoning over a vast space of beliefs (probability distributions). To address this challenge, we introduce the notion of a goal-constrained belief space, which only contains beliefs reachable from the initial belief under desired executions that can achieve the given safe-reachability objective. Our method compactly represents this space over a bounded horizon using symbolic constraints, and employs an incremental Satisfiability Modulo Theories (SMT) solver to efficiently search for a valid policy over it. We evaluate our method using a case study involving a partially observable robotic domain with uncertain obstacles. The results show that our method can synthesize policies over large belief spaces with a small number of SMT solver calls by focusing on the goal-constrained belief space.}, acmid = {3237424}, address = {Stockholm, Sweden}, keyword = {planning from high-level specifications; uncertainty}, series = {AAMAS 2018}, url = {http://dl.acm.org/citation.cfm?id=3237383.3237424} }DetailsAbstract
Planning robust executions under uncertainty is a fundamental challenge for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling uncertainty in many applications. In this work, we study POMDPs with safe-reachability objectives, which require that with a probability above some threshold, a goal state is eventually reached while keeping the probability of visiting unsafe states below some threshold. This POMDP formulation is different from the traditional POMDP models with optimality objectives and we show that in some cases, POMDPs with safe-reachability objectives can provide a better guarantee of both safety and reachability than the existing POMDP models through an example. A key algorithmic problem for POMDPs is policy synthesis, which requires reasoning over a vast space of beliefs (probability distributions). To address this challenge, we introduce the notion of a goal-constrained belief space, which only contains beliefs reachable from the initial belief under desired executions that can achieve the given safe-reachability objective. Our method compactly represents this space over a bounded horizon using symbolic constraints, and employs an incremental Satisfiability Modulo Theories (SMT) solver to efficiently search for a valid policy over it. We evaluate our method using a case study involving a partially observable robotic domain with uncertain obstacles. The results show that our method can synthesize policies over large belief spaces with a small number of SMT solver calls by focusing on the goal-constrained belief space. - N. T. Dantam, Z. K. Kingston, S. Chaudhuri, and L. E. Kavraki, “An Incremental Constraint-Based Framework for Task and Motion Planning,” International Journal of Robotics Research, vol. 37, no. 10, pp. 1134-1151. (Invited
Article), 2018.
BibTeX
@article{dantam2018incremental-tmp, title = {An Incremental Constraint-Based Framework for Task and Motion Planning}, author = {Dantam, Neil T. and Kingston, Zachary K. and Chaudhuri, Swarat and Kavraki, Lydia E.}, journal = {International Journal of Robotics Research, vol. 37, no. 10, pp. 1134-1151. (Invited Article)}, year = {2018}, doi = {10.1177/0278364918761570}, abstract = {We present a new constraint-based framework for task and motion planning (TMP). Our approach is extensible, probabilistically-complete, and offers improved performance and generality compared to a similar, state-of-the-art planner. The key idea is to leverage incremental constraint solving to efficiently incorporate geometric information at the task level. Using motion feasibility information to guide task planning improves scalability of the overall planner. Our key abstractions address the requirements of manipulation and object rearrangement. We validate our approach on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared to the benchmark planner and improved scalability from additional geometric guidance. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future.}, keyword = {planning from high-level specifications} }DetailsAbstract
We present a new constraint-based framework for task and motion planning (TMP). Our approach is extensible, probabilistically-complete, and offers improved performance and generality compared to a similar, state-of-the-art planner. The key idea is to leverage incremental constraint solving to efficiently incorporate geometric information at the task level. Using motion feasibility information to guide task planning improves scalability of the overall planner. Our key abstractions address the requirements of manipulation and object rearrangement. We validate our approach on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared to the benchmark planner and improved scalability from additional geometric guidance. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future. - K. He, M. Lahijanian, L. E. Kavraki, and M. Y. Vardi, “Reactive Synthesis For Finite Tasks Under Resource Constraints,” in 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, 2017, pp. 5326–5332.
BibTeX
@inproceedings{he-lahijanian2017reactive-manipulation, title = {Reactive Synthesis For Finite Tasks Under Resource Constraints}, author = {He, Keliang and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.}, booktitle = {2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}, month = sep, year = {2017}, pages = {5326--5332}, doi = {10.1109/IROS.2017.8206426}, abstract = {There are many applications where robots have to operate in environments that other agents can change. In such cases, it is desirable for the robot to achieve a given high- level task despite interference. Ideally, the robot must decide its next action as it observes the changes in the world, i.e. act reactively. In this paper, we consider a reactive planning problem for finite robotic tasks with resource constraints. The task is represented using a temporal logic for finite behaviors and the robot must achieve the task using limited resources under all possible finite sequences of moves of other agents. We present a formulation for this problem and an approach based on quantitative games. The efficacy of the approach is demonstrated through a manipulation case study.}, address = {Vancouver, BC}, keyword = {planning from high-level specifications}, publisher = {IEEE} }DetailsAbstract
There are many applications where robots have to operate in environments that other agents can change. In such cases, it is desirable for the robot to achieve a given high- level task despite interference. Ideally, the robot must decide its next action as it observes the changes in the world, i.e. act reactively. In this paper, we consider a reactive planning problem for finite robotic tasks with resource constraints. The task is represented using a temporal logic for finite behaviors and the robot must achieve the task using limited resources under all possible finite sequences of moves of other agents. We present a formulation for this problem and an approach based on quantitative games. The efficacy of the approach is demonstrated through a manipulation case study. - Z. Kingston, M. Moll, and L. E. Kavraki, “Decoupling Constraints from Sampling-Based Planners,” in Proceedings of the International Symposium of Robotics Research, Puerto Varas, Chile, 2017.
BibTeX
@inproceedings{kingston2017decoupling-constraints, title = {Decoupling Constraints from Sampling-Based Planners}, author = {Kingston, Zachary and Moll, Mark and Kavraki, Lydia E.}, booktitle = {Proceedings of the International Symposium of Robotics Research}, year = {2017}, abstract = {We present a general unifying framework for sampling-based motion planning under kinematic task constraints which enables a broad class of planners to compute plans that satisfy a given constraint function that encodes, e.g., loop closure, balance, and end-effector constraints. The framework decouples a planner’s method for exploration from constraint satisfaction by representing the implicit configuration space defined by a constraint function. We emulate three constraint satisfaction methodologies from the literature, and demonstrate the framework with a range of planners utilizing these constraint methodologies. Our results show that the appropriate choice of constrained satisfaction methodology depends on many factors, e.g., the dimension of the configuration space and implicit constraint manifold, and number of obstacles. Furthermore, we show that novel combinations of planners and constraint satisfaction methodologies can be more effective than previous approaches. The framework is also easily extended for novel planners and constraint spaces.}, address = {Puerto Varas, Chile}, keyword = {fundamentals of sampling-based motion planning} }DetailsAbstract
We present a general unifying framework for sampling-based motion planning under kinematic task constraints which enables a broad class of planners to compute plans that satisfy a given constraint function that encodes, e.g., loop closure, balance, and end-effector constraints. The framework decouples a planner’s method for exploration from constraint satisfaction by representing the implicit configuration space defined by a constraint function. We emulate three constraint satisfaction methodologies from the literature, and demonstrate the framework with a range of planners utilizing these constraint methodologies. Our results show that the appropriate choice of constrained satisfaction methodology depends on many factors, e.g., the dimension of the configuration space and implicit constraint manifold, and number of obstacles. Furthermore, we show that novel combinations of planners and constraint satisfaction methodologies can be more effective than previous approaches. The framework is also easily extended for novel planners and constraint spaces. - W. Baker, Z. Kingston, M. Moll, J. Badger, and L. E. Kavraki, “Robonaut 2 and You: Specifying and Executing Complex Operations,” in Proceedings of the IEEE Workshop on Advanced Robotics and its Social Impacts
(ARSO), Austin, TX, 2017.
BibTeX
@inproceedings{baker2017robonaut-2-and-you, title = {Robonaut 2 and You: Specifying and Executing Complex Operations}, author = {Baker, William and Kingston, Zachary and Moll, Mark and Badger, Julia and Kavraki, Lydia E.}, booktitle = {Proceedings of the IEEE Workshop on Advanced Robotics and its Social Impacts (ARSO)}, year = {2017}, doi = {10.1109/ARSO.2017.8025204}, abstract = {Crew time is a precious resource due to the expense of trained human operators in space. Efficient caretaker robots could lessen the manual labor load required by frequent vehicular and life support maintenance tasks, freeing astronaut time for scientific mission objectives. Humanoid robots can fluidly exist alongside human counterparts due to their form, but they are complex and high-dimensional platforms. This paper describes a system that human operators can use to maneuver Robonaut 2 (R2), a dexterous humanoid robot developed by NASA to research co-robotic applications. The system includes a specification of constraints used to describe operations, and the supporting planning framework that solves constrained problems on R2 at interactive speeds. The paper is developed in reference to an illustrative, typical example of an operation R2 performs to highlight the challenges inherent to the problems R2 must face. Finally, the interface and planner is validated through a case-study using the guiding example on the physical robot in a simulated microgravity environment. This work reveals the complexity of employing humanoid caretaker robots and suggest solutions that are broadly applicable.}, address = {Austin, TX}, keyword = {planning from high-level specifications} }DetailsAbstract
Crew time is a precious resource due to the expense of trained human operators in space. Efficient caretaker robots could lessen the manual labor load required by frequent vehicular and life support maintenance tasks, freeing astronaut time for scientific mission objectives. Humanoid robots can fluidly exist alongside human counterparts due to their form, but they are complex and high-dimensional platforms. This paper describes a system that human operators can use to maneuver Robonaut 2 (R2), a dexterous humanoid robot developed by NASA to research co-robotic applications. The system includes a specification of constraints used to describe operations, and the supporting planning framework that solves constrained problems on R2 at interactive speeds. The paper is developed in reference to an illustrative, typical example of an operation R2 performs to highlight the challenges inherent to the problems R2 must face. Finally, the interface and planner is validated through a case-study using the guiding example on the physical robot in a simulated microgravity environment. This work reveals the complexity of employing humanoid caretaker robots and suggest solutions that are broadly applicable. - S. Butler, M. Moll, and L. E. Kavraki, “A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and
Maximum Constraints,” in Proceedings of the Workshop on the Algorithmic Foundations of Robotics, 2016.
BibTeX
@inproceedings{butler2016a-general-algorithm-for-time-optimal-trajectory, title = {A General Algorithm for Time-Optimal Trajectory Generation Subject to Minimum and Maximum Constraints}, author = {Butler, Stephen and Moll, Mark and Kavraki, Lydia E.}, booktitle = {Proceedings of the Workshop on the Algorithmic Foundations of Robotics}, month = dec, year = {2016}, abstract = {This paper presents a new algorithm which generates time-optimal trajectories given a path as input. The algorithm improves on previous approaches by generically handling a broader class of constraints on the dynamics. It eliminates the need for heuristics to select trajectory segments that are part of the optimal trajectory through an exhaustive, but efficient search. We also present an algorithm for computing all achievable velocities at the end of a path given an initial range of velocities. This algorithm effectively computes bundles of feasible trajectories for a given path and is a first step toward a new generation of more efficient kinodynamic motion planning algorithms. We present results for both algorithms using a simulated WAM arm with a Barrett hand subject to dynamics constraints on joint torque, joint velocity, momentum, and end effector velocity. The new algorithms are compared with a state-of-the-art alternative approach.}, keyword = {kinodynamic systems} }DetailsAbstract
This paper presents a new algorithm which generates time-optimal trajectories given a path as input. The algorithm improves on previous approaches by generically handling a broader class of constraints on the dynamics. It eliminates the need for heuristics to select trajectory segments that are part of the optimal trajectory through an exhaustive, but efficient search. We also present an algorithm for computing all achievable velocities at the end of a path given an initial range of velocities. This algorithm effectively computes bundles of feasible trajectories for a given path and is a first step toward a new generation of more efficient kinodynamic motion planning algorithms. We present results for both algorithms using a simulated WAM arm with a Barrett hand subject to dynamics constraints on joint torque, joint velocity, momentum, and end effector velocity. The new algorithms are compared with a state-of-the-art alternative approach. - N. T. Dantam, K. Bøndergaard, M. A. Johansson, T. Furuholm, and L. E. Kavraki, “Unix Philosophy and the Real World: Control Software for Humanoid Robots,” Frontiers in Robotics and Artificial Intelligence, vol. 3, Mar. 2016.
BibTeX
@article{dantam2016unix, title = {Unix Philosophy and the Real World: Control Software for Humanoid Robots}, author = {Dantam, Neil T. and B{\o}ndergaard, Kim and Johansson, Mattias A. and Furuholm, Tobias and Kavraki, Lydia E.}, journal = {Frontiers in Robotics and Artificial Intelligence}, month = mar, year = {2016}, volume = {3}, doi = {10.3389/frobt.2016.00006}, abstract = {Robot software combines the challenges of general purpose and real-time software, requiring complex logic and bounded resource use. Physical safety, particularly for dynamic systems such as humanoid robots, depends on correct software. General purpose computation has converged on unix-like operating systems -- standardized as POSIX, the Portable Operating System Interface -- for devices from cellular phones to supercomputers. The modular, multi-process design typical of POSIX applications is effective for building complex and reliable software. Absent from POSIX, however, is an interproccess communication mechanism that prioritizes newer data as typically desired for control of physical systems. We address this need in the Ach communication library which provides suitable semantics and performance for real-time robot control. Although initially designed for humanoid robots, Ach has broader applicability to complex mechatronic devices -- humanoid and otherwise -- that require real-time coupling of sensors, control, planning, and actuation. The initial user space implementation of Ach was limited in the ability to receive data from multiple sources. We remove this limitation by implementing Ach as a Linux kernel module, enabling Ach's high-performance and latest-message-favored semantics within conventional POSIX communication pipelines. We discuss how these POSIX interfaces and design principles apply to robot software, and we present a case study using the Ach kernel module for communication on the Baxter robot.}, keyword = {other robotics} }DetailsAbstract
Robot software combines the challenges of general purpose and real-time software, requiring complex logic and bounded resource use. Physical safety, particularly for dynamic systems such as humanoid robots, depends on correct software. General purpose computation has converged on unix-like operating systems – standardized as POSIX, the Portable Operating System Interface – for devices from cellular phones to supercomputers. The modular, multi-process design typical of POSIX applications is effective for building complex and reliable software. Absent from POSIX, however, is an interproccess communication mechanism that prioritizes newer data as typically desired for control of physical systems. We address this need in the Ach communication library which provides suitable semantics and performance for real-time robot control. Although initially designed for humanoid robots, Ach has broader applicability to complex mechatronic devices – humanoid and otherwise – that require real-time coupling of sensors, control, planning, and actuation. The initial user space implementation of Ach was limited in the ability to receive data from multiple sources. We remove this limitation by implementing Ach as a Linux kernel module, enabling Ach’s high-performance and latest-message-favored semantics within conventional POSIX communication pipelines. We discuss how these POSIX interfaces and design principles apply to robot software, and we present a case study using the Ach kernel module for communication on the Baxter robot. - Y. Wang, N. T. Dantam, S. Chaudhuri, and L. E. Kavraki, “Task and Motion Policy Synthesis as Liveness Games,” in Proceedings of the International Conference on Automated Planning and Scheduling, 2016, pp. 536–540.
BibTeX
@inproceedings{wang2016task, title = {Task and Motion Policy Synthesis as Liveness Games}, author = {Wang, Yue and Dantam, Neil T. and Chaudhuri, Swarat and Kavraki, Lydia E.}, booktitle = {Proceedings of the International Conference on Automated Planning and Scheduling}, year = {2016}, pages = {536--540}, abstract = {We present a novel and scalable policy synthesis approach for robots. Rather than producing single-path plans for a static environment, we consider changing environments with uncontrollable agents, where the robot needs a policy to respond correctly over the infinite-horizon interaction with the environment. Our approach operates on task and motion domains, and combines actions over discrete states with continuous, collision-free paths. We synthesize a task and motion policy by iteratively generating a candidate policy and verifying its correctness. For efficient policy generation, we use grammars for potential policies to limit the search space and apply domain-specific heuristics to generalize verification failures, providing stricter constraints on policy candidates. For efficient policy verification, we construct compact, symbolic constraints for valid policies and employ a Satisfiability Modulo Theories (SMT) solver to check the validity of these constraints. Furthermore, the SMT solver enables quantitative specifications such as energy limits. The results show that our approach offers better scalability compared to a state-of-the-art policy synthesis tool in the tested benchmarks and demonstrate an order-of-magnitude speedup from our heuristics for the tested mobile manipulation domain.}, keyword = {planning from high-level specifications}, publisher = {AAAI}, url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13146} }DetailsAbstract
We present a novel and scalable policy synthesis approach for robots. Rather than producing single-path plans for a static environment, we consider changing environments with uncontrollable agents, where the robot needs a policy to respond correctly over the infinite-horizon interaction with the environment. Our approach operates on task and motion domains, and combines actions over discrete states with continuous, collision-free paths. We synthesize a task and motion policy by iteratively generating a candidate policy and verifying its correctness. For efficient policy generation, we use grammars for potential policies to limit the search space and apply domain-specific heuristics to generalize verification failures, providing stricter constraints on policy candidates. For efficient policy verification, we construct compact, symbolic constraints for valid policies and employ a Satisfiability Modulo Theories (SMT) solver to check the validity of these constraints. Furthermore, the SMT solver enables quantitative specifications such as energy limits. The results show that our approach offers better scalability compared to a state-of-the-art policy synthesis tool in the tested benchmarks and demonstrate an order-of-magnitude speedup from our heuristics for the tested mobile manipulation domain. - M. Lahijanian, M. R. Maly, D. Fried, L. E. Kavraki, H. Kress-Gazit, and M. Y. Vardi, “Iterative Temporal Planning in Uncertain Environments with Partial Satisfaction
Guarantees,” IEEE Transactions on Robotics, vol. 32, no. 3, pp. 583–599, 2016.
BibTeX
@article{lahijanian2016iterative, title = {Iterative Temporal Planning in Uncertain Environments with Partial Satisfaction Guarantees}, author = {Lahijanian, Morteza and Maly, Matthew R. and Fried, Dror and Kavraki, Lydia E. and Kress-Gazit, Hadas and Vardi, Moshe Y.}, journal = {IEEE Transactions on Robotics}, year = {2016}, volume = {32}, number = {3}, pages = {583--599}, doi = {10.1109/TRO.2016.2544339}, abstract = {This work introduces a motion-planning framework for a hybrid system with general continuous dynamics to satisfy a temporal logic specification consisting of co-safety and safety components in a partially unknown environment. The framework employs a multi-layered synergistic planner to generate trajectories that satisfy the specification and adopts an iterative replanning strategy to deal with unknown obstacles. When the discovery of an obstacle renders the specification unsatisfiable, a division between the constraints in the specification is considered. The co-safety component of the specification is treated as a soft constraint, whose partial satisfaction is allowed, while the safety component is viewed as a hard constraint, whose violation is forbidden. To partially satisfy the co-safety component, inspirations are taken from indoor-robotic scenarios, and three types of (unexpressed) restrictions on the ordering of sub-tasks in the specification are considered. For each type, a partial satisfaction method is introduced, which guarantees the generation of trajectories that do not violate the safety constraints while attending to partially satisfying the co-safety requirements with respect to the chosen restriction type. The efficacy of the framework is illustrated through case studies on a hybrid car-like robot in an office environment.}, keyword = {planning from high-level specifications} }DetailsAbstract
This work introduces a motion-planning framework for a hybrid system with general continuous dynamics to satisfy a temporal logic specification consisting of co-safety and safety components in a partially unknown environment. The framework employs a multi-layered synergistic planner to generate trajectories that satisfy the specification and adopts an iterative replanning strategy to deal with unknown obstacles. When the discovery of an obstacle renders the specification unsatisfiable, a division between the constraints in the specification is considered. The co-safety component of the specification is treated as a soft constraint, whose partial satisfaction is allowed, while the safety component is viewed as a hard constraint, whose violation is forbidden. To partially satisfy the co-safety component, inspirations are taken from indoor-robotic scenarios, and three types of (unexpressed) restrictions on the ordering of sub-tasks in the specification are considered. For each type, a partial satisfaction method is introduced, which guarantees the generation of trajectories that do not violate the safety constraints while attending to partially satisfying the co-safety requirements with respect to the chosen restriction type. The efficacy of the framework is illustrated through case studies on a hybrid car-like robot in an office environment. - J. D. Hernández, M. Moll, E. Vidal Garcia, M. Carreras, and L. E. Kavraki, “Planning Feasible and Safe Paths Online for Autonomous Underwater Vehicles in Unknown
Environments,” in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and
Systems, 2016, pp. 1313–1320.
BibTeX
@inproceedings{hernandez2016planning-feasible-and-safe-paths, title = {Planning Feasible and Safe Paths Online for Autonomous Underwater Vehicles in Unknown Environments}, author = {Hern{\'a}ndez, Juan David and Moll, Mark and Vidal Garcia, Eduard and Carreras, Marc and Kavraki, Lydia E.}, booktitle = {Proceedings of the {IEEE/RSJ} International Conference on Intelligent Robots and Systems}, year = {2016}, pages = {1313--1320}, doi = {10.1109/IROS.2016.7759217}, abstract = {We present a framework for planning collision-free and safe paths online for autonomous underwater vehicles (AUVs) in unknown environments. We build up on our previous work and propose an improved approach. While preserving its main modules (mapping, planning and mission handler), the framework now considers motion constraints to plan feasible paths, i.e., those that meet vehicle's motion capabilities. The new framework also incorporates a risk function to avoid navigating close to nearby obstacles, and reuses the last best known solution to eliminate time-consuming pruning routines. To evaluate this approach, we use the Sparus II AUV, a torpedo-shaped vehicle performing autonomous missions in a 2-dimensional workspace. We validate the framework's new features by solving tasks in both simulation and real-world in water trials and comparing results with our previous approach.}, keyword = {other robotics} }DetailsAbstract
We present a framework for planning collision-free and safe paths online for autonomous underwater vehicles (AUVs) in unknown environments. We build up on our previous work and propose an improved approach. While preserving its main modules (mapping, planning and mission handler), the framework now considers motion constraints to plan feasible paths, i.e., those that meet vehicle’s motion capabilities. The new framework also incorporates a risk function to avoid navigating close to nearby obstacles, and reuses the last best known solution to eliminate time-consuming pruning routines. To evaluate this approach, we use the Sparus II AUV, a torpedo-shaped vehicle performing autonomous missions in a 2-dimensional workspace. We validate the framework’s new features by solving tasks in both simulation and real-world in water trials and comparing results with our previous approach. - N. T. Dantam, Z. K. Kingston, S. Chaudhuri, and L. E. Kavraki, “Incremental Task and Motion Planning: A Constraint-Based Approach,” in Robotics: Science and Systems, 2016.
BibTeX
@inproceedings{dantam2016tmp, title = {Incremental Task and Motion Planning: A Constraint-Based Approach}, author = {Dantam, Neil T. and Kingston, Zachary K. and Chaudhuri, Swarat and Kavraki, Lydia E.}, booktitle = {Robotics: Science and Systems}, year = {2016}, doi = {10.15607/RSS.2016.XII.002}, abstract = {We present a new algorithm for task and motion planning (TMP) and discuss the requirements and abstractions necessary to obtain robust solutions for TMP in general. Our Iteratively Deepened Task and Motion Planning (IDTMP) method is probabilistically-complete and offers improved performance and generality compared to a similar, state-of-the-art, probabilistically-complete planner. The key idea of IDTMP is to leverage incremental constraint solving to efficiently add and remove constraints on motion feasibility at the task level. We validate IDTMP on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared to the benchmark planner and a four-times self-comparison speedup from our extensions. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future.}, keyword = {planning from high-level specifications} }DetailsAbstract
We present a new algorithm for task and motion planning (TMP) and discuss the requirements and abstractions necessary to obtain robust solutions for TMP in general. Our Iteratively Deepened Task and Motion Planning (IDTMP) method is probabilistically-complete and offers improved performance and generality compared to a similar, state-of-the-art, probabilistically-complete planner. The key idea of IDTMP is to leverage incremental constraint solving to efficiently add and remove constraints on motion feasibility at the task level. We validate IDTMP on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared to the benchmark planner and a four-times self-comparison speedup from our extensions. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future. - K. He, M. Lahijanian, L. E. Kavraki, and M. Y. Vardi, “Towards Manipulation Planning with Temporal Logic Specifications,” in Proceedings of the 2015 IEEE International Conference on Robotics and Automation
(ICRA), Seattle, WA, 2015, pp. 346–352.
BibTeX
@inproceedings{he-lahijanian2015towards-manipulation-planning, title = {Towards Manipulation Planning with Temporal Logic Specifications}, author = {He, Keliang and Lahijanian, Morteza and Kavraki, Lydia E. and Vardi, Moshe Y.}, booktitle = {Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA)}, month = may, year = {2015}, pages = {346--352}, doi = {10.1109/ICRA.2015.7139022}, abstract = {Manipulation planning from high-level task specifications, even though highly desirable, is a challenging problem. The large dimensionality of manipulators and complexity of task specifications make the problem computationally intractable. This work introduces a manipulation planning framework with linear temporal logic (LTL) specifications. The use of LTL as the specification language allows the expression of rich and complex manipulation tasks. The framework deals with the state-explosion problem through a novel abstraction technique. Given a robotic system, a workspace consisting of obstacles, manipulable objects, and locations of interest, and a co-safe LTL specification over the objects and locations, the framework computes a motion plan to achieve the task through a synergistic multi-layered planning architecture. The power of the framework is demonstrated through case studies, in which the planner efficiently computes plans for complex tasks. The case studies also illustrate the ability of the framework in intelligently moving away objects that block desired executions without requiring backtracking.}, address = {Seattle, WA}, keyword = {planning from high-level specifications}, publisher = {IEEE} }DetailsAbstract
Manipulation planning from high-level task specifications, even though highly desirable, is a challenging problem. The large dimensionality of manipulators and complexity of task specifications make the problem computationally intractable. This work introduces a manipulation planning framework with linear temporal logic (LTL) specifications. The use of LTL as the specification language allows the expression of rich and complex manipulation tasks. The framework deals with the state-explosion problem through a novel abstraction technique. Given a robotic system, a workspace consisting of obstacles, manipulable objects, and locations of interest, and a co-safe LTL specification over the objects and locations, the framework computes a motion plan to achieve the task through a synergistic multi-layered planning architecture. The power of the framework is demonstrated through case studies, in which the planner efficiently computes plans for complex tasks. The case studies also illustrate the ability of the framework in intelligently moving away objects that block desired executions without requiring backtracking. - M. Lahijanian, S. Almagor, D. Fried, L. E. Kavraki, and M. Y. Vardi, “This Time the Robot Settles for a Cost: A Quantitative Approach to Temporal Logic
Planning with Partial Satisfaction,” in Proceedings of The Twenty-Ninth AAAI Conference (AAAI-15), Austin, TX, 2015, pp. 3664–3671.
BibTeX
@inproceedings{lahijanian-almagor2015this-time-robot, title = {This Time the Robot Settles for a Cost: A Quantitative Approach to Temporal Logic Planning with Partial Satisfaction}, author = {Lahijanian, Morteza and Almagor, Shaull and Fried, Dror and Kavraki, Lydia E and Vardi, Moshe Y.}, booktitle = {Proceedings of The Twenty-Ninth AAAI Conference (AAAI-15)}, month = jan, year = {2015}, pages = {3664--3671}, abstract = {The specification of complex motion goals through temporal logics is increasingly favored in robotics to narrow the gap between task and motion planning. A major limiting factor of such logics, however, is their Boolean satisfaction condition. To relax this limitation, we introduce a method for quantifying the satisfaction of co-safe linear temporal logic specifications, and propose a planner that uses this method to synthesize robot trajectories with the optimal satisfaction value. The method assigns costs to violations of specifications from user-defined proposition costs. These violation costs define a distance to satisfaction and can be computed algorithmically using a weighted automaton. The planner utilizes this automaton and an abstraction of the robotic system to construct a product graph that captures all possible robot trajectories and their distances to satisfaction. Then, a plan with the minimum distance to satisfaction is generated by employing this graph as the high-level planner in a synergistic planning framework. The efficacy of the method is illustrated on a robot with unsatisfiable specifications in an office environment.}, address = {Austin, TX}, keyword = {uncertainty}, publisher = {AAAI}, url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/10001} }DetailsAbstract
The specification of complex motion goals through temporal logics is increasingly favored in robotics to narrow the gap between task and motion planning. A major limiting factor of such logics, however, is their Boolean satisfaction condition. To relax this limitation, we introduce a method for quantifying the satisfaction of co-safe linear temporal logic specifications, and propose a planner that uses this method to synthesize robot trajectories with the optimal satisfaction value. The method assigns costs to violations of specifications from user-defined proposition costs. These violation costs define a distance to satisfaction and can be computed algorithmically using a weighted automaton. The planner utilizes this automaton and an abstraction of the robotic system to construct a product graph that captures all possible robot trajectories and their distances to satisfaction. Then, a plan with the minimum distance to satisfaction is generated by employing this graph as the high-level planner in a synergistic planning framework. The efficacy of the method is illustrated on a robot with unsatisfiable specifications in an office environment. - C. Voss, M. Moll, and L. E. Kavraki, “A Heuristic Approach to Finding Diverse Short Paths,” in IEEE International Conference on Robotics and Automation, Seattle, WA, 2015, pp. 4173–4179.
BibTeX
@inproceedings{voss-moll2015heuristic-approach-to, title = {A Heuristic Approach to Finding Diverse Short Paths}, author = {Voss, Caleb and Moll, Mark and Kavraki, Lydia E}, booktitle = {IEEE International Conference on Robotics and Automation}, year = {2015}, pages = {4173--4179}, doi = {10.1109/ICRA.2015.7139774}, abstract = {We present an algorithm that seeks to find a set of diverse, short paths through a roadmap graph. The usefulness of a such a set is illustrated in robotic motion planning and routing applications wherein a precomputed roadmap of the environment is partially invalidated by some change, for example, relocation of obstacles or modification of the robot. Our algorithm employs the heuristic that configurations near each other are likely to be invalidated by the same change in the environment. To find short, diverse paths, the algorithm finds a detour that is the shortest path avoiding a selection of balls in the configuration space. Different collections of these balls, or simulated obstacles, yield different and diverse short paths. Paths may then be checked for validity as a cheap alternative to checking or reconstructing the entire roadmap. We describe a formal definition of path set diversity and several measures on which to evaluate our algorithm. We compare the speed and quality of our heuristic algorithm{\textquoteright}s results against an exact algorithm that computes the optimally shortest set of paths on the roadmap having a minimum diversity. We will show that, with a tolerable loss in path shortness, our algorithm produces equally diverse path sets orders of magnitude faster.}, address = {Seattle, WA}, keyword = {other robotics} }DetailsAbstract
We present an algorithm that seeks to find a set of diverse, short paths through a roadmap graph. The usefulness of a such a set is illustrated in robotic motion planning and routing applications wherein a precomputed roadmap of the environment is partially invalidated by some change, for example, relocation of obstacles or modification of the robot. Our algorithm employs the heuristic that configurations near each other are likely to be invalidated by the same change in the environment. To find short, diverse paths, the algorithm finds a detour that is the shortest path avoiding a selection of balls in the configuration space. Different collections of these balls, or simulated obstacles, yield different and diverse short paths. Paths may then be checked for validity as a cheap alternative to checking or reconstructing the entire roadmap. We describe a formal definition of path set diversity and several measures on which to evaluate our algorithm. We compare the speed and quality of our heuristic algorithm’s results against an exact algorithm that computes the optimally shortest set of paths on the roadmap having a minimum diversity. We will show that, with a tolerable loss in path shortness, our algorithm produces equally diverse path sets orders of magnitude faster. - M. Moll, I. A. Şucan, and L. E. Kavraki, “Benchmarking Motion Planning Algorithms: An Extensible Infrastructure for Analysis and
Visualization,” IEEE Robotics & Automation Magazine (Special Issue on Replicable and Measurable
Robotics Research), vol. 22, no. 3, pp. 96–102, 2015.
BibTeX
@article{moll-sucan2015benchmarking-motion-planning, title = {Benchmarking Motion Planning Algorithms: An Extensible Infrastructure for Analysis and Visualization}, author = {Moll, Mark and {\c S}ucan, Ioan A. and Kavraki, Lydia E}, journal = {IEEE Robotics \& Automation Magazine (Special Issue on Replicable and Measurable Robotics Research)}, year = {2015}, volume = {22}, number = {3}, pages = {96--102}, doi = {10.1109/MRA.2015.2448276}, abstract = {Sampling-based planning algorithms are widely used on many robot platforms. Within this class of algorithms, many variants have been proposed over the last 20 years, yet there is still no characterization of which algorithms are well-suited for which classes of problems. This has motivated us to develop a benchmarking infrastructure for motion planning algorithms. It consists of three main components. First, we have created an extensive benchmarking software framework that is included with the Open Motion Planning Library (OMPL), a C++ library that contains implementations of many sampling-based algorithms. Second, we have defined extensible formats for storing benchmark results. The formats are fairly straightforward so that other planning libraries could easily produce compatible output. Finally, we have created an interactive, versatile visualization tool for compact presentation of collected benchmark data. The tool and underlying database facilitate the analysis of performance across benchmark problems and planners.}, keyword = {fundamentals of sampling-based motion planning} }DetailsAbstract
Sampling-based planning algorithms are widely used on many robot platforms. Within this class of algorithms, many variants have been proposed over the last 20 years, yet there is still no characterization of which algorithms are well-suited for which classes of problems. This has motivated us to develop a benchmarking infrastructure for motion planning algorithms. It consists of three main components. First, we have created an extensive benchmarking software framework that is included with the Open Motion Planning Library (OMPL), a C++ library that contains implementations of many sampling-based algorithms. Second, we have defined extensible formats for storing benchmark results. The formats are fairly straightforward so that other planning libraries could easily produce compatible output. Finally, we have created an interactive, versatile visualization tool for compact presentation of collected benchmark data. The tool and underlying database facilitate the analysis of performance across benchmark problems and planners. - Z. Kingston, N. Dantam, and L. E. Kavraki, “Kinematically constrained workspace control via linear optimization,” in Proceedings of the IEEE-RAS 15th International Conference on Humanoid Robots
(Humanoids), 2015, pp. 758–764.
BibTeX
@inproceedings{kingston2015lc3, title = {Kinematically constrained workspace control via linear optimization}, author = {Kingston, Zachary and Dantam, Neil and Kavraki, Lydia E.}, booktitle = {Proceedings of the IEEE-RAS 15th International Conference on Humanoid Robots (Humanoids)}, year = {2015}, pages = {758--764}, doi = {10.1109/HUMANOIDS.2015.7363455}, abstract = {We present a method for Cartesian workspace control of a robot manipulator that enforces joint-level acceleration, velocity, and position constraints using linear optimization. This method is robust to kinematic singularities. On redundant manipulators, we avoid poor configurations near joint limits by including a maximum permissible velocity term to center each joint within its limits. Compared to the baseline Jacobian damped least-squares method of workspace control, this new approach honors kinematic limits, ensuring physically realizable control inputs and providing smoother motion of the robot. We demonstrate our method on simulated redundant and non-redundant manipulators and implement it on the physical 7-degree-of-freedom Baxter manipulator. We provide our control software under a permissive license.}, keyword = {other robotics} }DetailsAbstract
We present a method for Cartesian workspace control of a robot manipulator that enforces joint-level acceleration, velocity, and position constraints using linear optimization. This method is robust to kinematic singularities. On redundant manipulators, we avoid poor configurations near joint limits by including a maximum permissible velocity term to center each joint within its limits. Compared to the baseline Jacobian damped least-squares method of workspace control, this new approach honors kinematic limits, ensuring physically realizable control inputs and providing smoother motion of the robot. We demonstrate our method on simulated redundant and non-redundant manipulators and implement it on the physical 7-degree-of-freedom Baxter manipulator. We provide our control software under a permissive license. - D. K. Grady, M. Moll, and L. E. Kavraki, “Extending the Applicability of POMDP Solutions to Robotic Tasks,” IEEE Transactions on Robotics, vol. 31, no. 4, pp. 948–961, 2015.
BibTeX
@article{grady-moll2015extending-applicability-of, title = {Extending the Applicability of {POMDP} Solutions to Robotic Tasks}, author = {Grady, Devin K. and Moll, Mark and Kavraki, Lydia E.}, journal = {IEEE Transactions on Robotics}, year = {2015}, volume = {31}, number = {4}, pages = {948--961}, doi = {10.1109/TRO.2015.2441511}, abstract = {Partially-Observable Markov Decision Processes (POMDPs) are used in many robotic task classes from soccer to household chores. Determining an approximately optimal action policy for POMDPs is PSPACE-complete, and the exponential growth of computation time prohibits solving large tasks. This paper describes two techniques to extend the range of robotic tasks that can be solved using a POMDP. Our first technique reduces the motion constraints of a robot, and then uses state-of-the-art robotic motion planning techniques to respect the true motion constraints at runtime. We then propose a novel task decomposition that can be applied to some indoor robotic tasks. This decomposition transforms a long time horizon task into a set of shorter tasks. We empirically demonstrate the performance gain provided by these two techniques through simulated execution in a variety of environments. Comparing a direct formulation of a POMDP to solving our proposed reductions, we conclude that the techniques proposed in this paper can provide significant enhancement to current POMDP solution techniques, extending the POMDP instances that can be solved to include large, continuous-state robotic tasks.}, keyword = {uncertainty} }DetailsAbstract
Partially-Observable Markov Decision Processes (POMDPs) are used in many robotic task classes from soccer to household chores. Determining an approximately optimal action policy for POMDPs is PSPACE-complete, and the exponential growth of computation time prohibits solving large tasks. This paper describes two techniques to extend the range of robotic tasks that can be solved using a POMDP. Our first technique reduces the motion constraints of a robot, and then uses state-of-the-art robotic motion planning techniques to respect the true motion constraints at runtime. We then propose a novel task decomposition that can be applied to some indoor robotic tasks. This decomposition transforms a long time horizon task into a set of shorter tasks. We empirically demonstrate the performance gain provided by these two techniques through simulated execution in a variety of environments. Comparing a direct formulation of a POMDP to solving our proposed reductions, we conclude that the techniques proposed in this paper can provide significant enhancement to current POMDP solution techniques, extending the POMDP instances that can be solved to include large, continuous-state robotic tasks. - R. Luna, M. Lahijanian, M. Moll, and L. E. Kavraki, “Optimal and Efficient Stochastic Motion Planning in Partially-Known Environments,” in Proceedings of The Twenty-Eighth AAAI Conference on Artificial Intelligence, Quebec City, Canada, 2014, pp. 2549–2555.
BibTeX
@inproceedings{luna-lahijanian2014optimal-and-efficient, title = {Optimal and Efficient Stochastic Motion Planning in Partially-Known Environments}, author = {Luna, Ryan and Lahijanian, Morteza and Moll, Mark and Kavraki, Lydia E}, booktitle = {Proceedings of The Twenty-Eighth AAAI Conference on Artificial Intelligence}, month = jul, year = {2014}, pages = {2549--2555}, abstract = {A framework capable of computing optimal control policies for a continuous system in the presence of both action and environment uncertainty is presented in this work. The framework decomposes the planning problem into two stages: an offline phase that reasons only over action uncertainty and an online phase that quickly reacts to the uncertain environment. Offline, a bounded-parameter Markov decision process (BMDP) is employed to model the evolution of the stochastic system over a discretization of the environment. Online, an optimal control policy over the BMDP is computed. Upon the discovery of an unknown environment feature during policy execution, the BMDP is updated and the optimal control policy is efficiently recomputed. Depending on the desired quality of the control policy, a suite of methods is presented to incorporate new information into the BMDP with varying degrees of detail online. Experiments confirm that the framework recomputes high-quality policies in seconds and is orders of magnitude faster than existing methods.}, address = {Quebec City, Canada}, keyword = {uncertainty}, url = {http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8457} }DetailsAbstract
A framework capable of computing optimal control policies for a continuous system in the presence of both action and environment uncertainty is presented in this work. The framework decomposes the planning problem into two stages: an offline phase that reasons only over action uncertainty and an online phase that quickly reacts to the uncertain environment. Offline, a bounded-parameter Markov decision process (BMDP) is employed to model the evolution of the stochastic system over a discretization of the environment. Online, an optimal control policy over the BMDP is computed. Upon the discovery of an unknown environment feature during policy execution, the BMDP is updated and the optimal control policy is efficiently recomputed. Depending on the desired quality of the control policy, a suite of methods is presented to incorporate new information into the BMDP with varying degrees of detail online. Experiments confirm that the framework recomputes high-quality policies in seconds and is orders of magnitude faster than existing methods. - R. Luna, M. Lahijanian, M. Moll, and L. E. Kavraki, “Fast Stochastic Motion Planning with Optimality Guarantees using Local Policy
Reconfiguration,” in Proceedings of the IEEE International Conference on Robotics and Automation, Hong Kong, China, 2014, pp. 3013–3019.
BibTeX
@inproceedings{luna-lahijanian2014fast-stochastic-motion, title = {Fast Stochastic Motion Planning with Optimality Guarantees using Local Policy Reconfiguration}, author = {Luna, Ryan and Lahijanian, Morteza and Moll, Mark and Kavraki, Lydia E}, booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation}, month = may, year = {2014}, pages = {3013--3019}, doi = {10.1109/ICRA.2014.6907293}, abstract = {This work presents a framework for fast reconfiguration of local control policies for a stochastic system to satisfy a high-level task specification. The motion of the system is abstracted to a class of uncertain Markov models known as bounded-parameter Markov decision processes (BMDPs). During the abstraction, an efficient sampling-based method for stochastic optimal control is used to construct several policies within a discrete region of the state space in order for the system to transit between neighboring regions. A BMDP is then used to find an optimal strategy over the local policies by maximizing a continuous reward function; a new policy can be computed quickly if the reward function changes. The efficacy of the framework is demonstrated using a sequence of online tasks, showing that highly desirable policies can be obtained by reconfiguring existing local policies in just a few seconds.}, address = {Hong Kong, China}, keyword = {uncertainty} }DetailsAbstract
This work presents a framework for fast reconfiguration of local control policies for a stochastic system to satisfy a high-level task specification. The motion of the system is abstracted to a class of uncertain Markov models known as bounded-parameter Markov decision processes (BMDPs). During the abstraction, an efficient sampling-based method for stochastic optimal control is used to construct several policies within a discrete region of the state space in order for the system to transit between neighboring regions. A BMDP is then used to find an optimal strategy over the local policies by maximizing a continuous reward function; a new policy can be computed quickly if the reward function changes. The efficacy of the framework is demonstrated using a sequence of online tasks, showing that highly desirable policies can be obtained by reconfiguring existing local policies in just a few seconds. - M. Lahijanian, L. E. Kavraki, and M. Y. Vardi, “A Sampling-Based Strategy Planner for Nondeterministic Hybrid Systems,” in Proceedings of the International Conference on Robotics and Automation, Hong Kong, China, 2014, pp. 3005–3012.
BibTeX
@inproceedings{lahijanian-kavraki2014sampling-based-strategy-planner, title = {A Sampling-Based Strategy Planner for Nondeterministic Hybrid Systems}, author = {Lahijanian, Morteza and Kavraki, Lydia E and Vardi, Moshe Y.}, booktitle = {Proceedings of the International Conference on Robotics and Automation}, month = may, year = {2014}, pages = {3005--3012}, doi = {10.1109/ICRA.2014.6907292}, abstract = {This paper introduces a strategy planner for nondeterministic hybrid systems with complex continuous dynamics. The planner uses sampling-based techniques and game-theoretic approaches to generate a series of plans and decision choices that increase the chances of success within a fixed time budget. The planning algorithm consists of two phases: exploration and strategy improvement. During the exploration phase, a search tree is grown in the hybrid state space by sampling state and control spaces for a fixed amount of time. An initial strategy is then computed over the search tree using a game-theoretic approach. To mitigate the effects of nondeterminism in the initial strategy, the strategy improvement phase extends new tree branches to the goal, using the data that is collected in the first phase. The efficacy of this planner is demonstrated on simulation of two hybrid and nondeterministic car-like robots in various environments. The results show significant increases in the likelihood of success for the strategies computed by the two-phase algorithm over a simple exploration planner.}, address = {Hong Kong, China}, keyword = {uncertainty}, publisher = {IEEE} }DetailsAbstract
This paper introduces a strategy planner for nondeterministic hybrid systems with complex continuous dynamics. The planner uses sampling-based techniques and game-theoretic approaches to generate a series of plans and decision choices that increase the chances of success within a fixed time budget. The planning algorithm consists of two phases: exploration and strategy improvement. During the exploration phase, a search tree is grown in the hybrid state space by sampling state and control spaces for a fixed amount of time. An initial strategy is then computed over the search tree using a game-theoretic approach. To mitigate the effects of nondeterminism in the initial strategy, the strategy improvement phase extends new tree branches to the goal, using the data that is collected in the first phase. The efficacy of this planner is demonstrated on simulation of two hybrid and nondeterministic car-like robots in various environments. The results show significant increases in the likelihood of success for the strategies computed by the two-phase algorithm over a simple exploration planner. - R. Luna, M. Lahijanian, M. Moll, and L. E. Kavraki, “Asymptotically Optimal Stochastic Motion Planning with Temporal Goals,” in Proceedings of the Workshop on the Algorithmic Foundations of Robotics, Istanbul, Turkey, 2014.
BibTeX
@inproceedings{luna-lahijanian2014asymptotically-optimal-stochastic, title = {Asymptotically Optimal Stochastic Motion Planning with Temporal Goals}, author = {Luna, Ryan and Lahijanian, Morteza and Moll, Mark and Kavraki, Lydia E}, booktitle = {Proceedings of the Workshop on the Algorithmic Foundations of Robotics}, month = mar, year = {2014}, doi = {10.1007/978-3-319-16595-0_20}, abstract = {This work presents a planning framework that allows a robot with stochastic action uncertainty to achieve a high-level task given in the form of a temporal logic formula. The objective is to quickly compute a feedback control policy to satisfy the task specification with maximum probability. A top-down framework is proposed that abstracts the motion of a continuous stochastic system to a discrete, bounded- parameter Markov decision process (bmdp), and then computes a control policy over the product of the bmdp abstraction and a dfa representing the temporal logic specification. Analysis of the framework reveals that as the resolution of the bmdp abstraction becomes finer, the policy obtained converges to optimal. Simulations show that high-quality policies to satisfy complex temporal logic specifications can be obtained in seconds, orders of magnitude faster than existing methods.}, address = {Istanbul, Turkey}, keyword = {uncertainty} }DetailsAbstract
This work presents a planning framework that allows a robot with stochastic action uncertainty to achieve a high-level task given in the form of a temporal logic formula. The objective is to quickly compute a feedback control policy to satisfy the task specification with maximum probability. A top-down framework is proposed that abstracts the motion of a continuous stochastic system to a discrete, bounded- parameter Markov decision process (bmdp), and then computes a control policy over the product of the bmdp abstraction and a dfa representing the temporal logic specification. Analysis of the framework reveals that as the resolution of the bmdp abstraction becomes finer, the policy obtained converges to optimal. Simulations show that high-quality policies to satisfy complex temporal logic specifications can be obtained in seconds, orders of magnitude faster than existing methods. - S. Nedunuri, S. Prabhu, M. Moll, S. Chaudhuri, and L. E. Kavraki, “SMT-Based Synthesis of Integrated Task and Motion Plans for Mobile Manipulation,” in Proceedings of the IEEE International Conference on Robotics and Automation, 2014, pp. 655–662.
BibTeX
@inproceedings{nedunuri-prabhu2014smt-based-synthesis-of, title = {{SMT}-Based Synthesis of Integrated Task and Motion Plans for Mobile Manipulation}, author = {Nedunuri, Srinivas and Prabhu, Sailesh and Moll, Mark and Chaudhuri, Swarat and Kavraki, Lydia E}, booktitle = {Proceedings of the IEEE International Conference on Robotics and Automation}, year = {2014}, pages = {655--662}, doi = {10.1109/ICRA.2014.6906924}, abstract = {Satisfiability Modulo Theories (SMT) solvers have recently emerged as a core technology in automated reasoning about systems. In this paper, we demonstrate the utility of these solvers in integrated task and motion planning (ITMP) for robots performing mobile manipulation. Specifically, we present a system{\textendash}-called ROBOSYNTH{\textendash}-for integrated task and motion planning that uses discrete search based on SMT-solvers as a complement to motion planning algorithms. As far as we know, this is the first application of SMT-solving in ITMP. The inputs to our version of ITMP are: (1) a scene description that specifies the physical space that the robot manipulates; (2) a plan outline that syntactically defines a space of plausible integrated plans; and (3) a set of logical requirements that we want the generated plan to satisfy. Given these inputs, our method uses a motion planning algorithm to construct a discrete placement graph whose paths represent feasible, low-level motion plans. An SMT-solver is now used to symbolically explore the space of all integrated plans that correspond to paths in the placement graph, and also satisfy the constraints demanded by the plan outline and the requirements. We have evaluated our approach on a generalization of an ITMP problem investigated in prior work. The experiments demonstrate that our method is capable of generating inte- grated plans that are interesting in a qualitative sense. We also find the method to scale well with an increase in the number of objects and locations manipulated, as well as the size of the space of plausible integrated plans.}, keyword = {planning from high-level specifications} }DetailsAbstract
Satisfiability Modulo Theories (SMT) solvers have recently emerged as a core technology in automated reasoning about systems. In this paper, we demonstrate the utility of these solvers in integrated task and motion planning (ITMP) for robots performing mobile manipulation. Specifically, we present a system–-called ROBOSYNTH–-for integrated task and motion planning that uses discrete search based on SMT-solvers as a complement to motion planning algorithms. As far as we know, this is the first application of SMT-solving in ITMP. The inputs to our version of ITMP are: (1) a scene description that specifies the physical space that the robot manipulates; (2) a plan outline that syntactically defines a space of plausible integrated plans; and (3) a set of logical requirements that we want the generated plan to satisfy. Given these inputs, our method uses a motion planning algorithm to construct a discrete placement graph whose paths represent feasible, low-level motion plans. An SMT-solver is now used to symbolically explore the space of all integrated plans that correspond to paths in the placement graph, and also satisfy the constraints demanded by the plan outline and the requirements. We have evaluated our approach on a generalization of an ITMP problem investigated in prior work. The experiments demonstrate that our method is capable of generating inte- grated plans that are interesting in a qualitative sense. We also find the method to scale well with an increase in the number of objects and locations manipulated, as well as the size of the space of plausible integrated plans.