oru.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 14) Show all publications
Akbari, A., Lagriffoul, F. & Rosell, J. (2019). Combined heuristic task and motion planning for bi-manual robots. Autonomous Robots, 43(6), 1575-1590
Open this publication in new window or tab >>Combined heuristic task and motion planning for bi-manual robots
2019 (English)In: Autonomous Robots, ISSN 0929-5593, E-ISSN 1573-7527, Vol. 43, no 6, p. 1575-1590Article in journal (Refereed) Published
Abstract [en]

Planning efficiently at task and motion levels allows the setting of new challenges for robotic manipulation problems, like for instance constrained table-top problems for bi-manual robots. In this scope, the appropriate combination of task and motion planning levels plays an important role. Accordingly, a heuristic-based task and motion planning approach is proposed, in which the computation of the heuristic addresses a geometrically relaxed problem, i.e., it only reasons upon objects placements, grasp poses, and inverse kinematics solutions. Motion paths are evaluated lazily, i.e., only after an action has been selected by the heuristic. This reduces the number of calls to the motion planner, while backtracking is reduced because the heuristic captures most of the geometric constraints. The approach has been validated in simulation and on a real robot, with different classes of table-top manipulation problems. Empirical comparison with recent approaches solving similar problems is also reported, showing that the proposed approach results in significant improvement both in terms of planing time and success rate.

Place, publisher, year, edition, pages
Springer, 2019
Keywords
Combined task and motion planning, Robot manipulation, Geometric reasoning, Path planning
National Category
Computer Vision and Robotics (Autonomous Systems)
Identifiers
urn:nbn:se:oru:diva-75363 (URN)10.1007/s10514-018-9817-3 (DOI)000474366100017 ()2-s2.0-85055937575 (Scopus ID)
Note

Funding Agencies:

Spanish Government  FPI 2015  DPI2016-80077-R 

Swedish Knowledge Foundation (KKS) Project "Semantic Robots"

Available from: 2019-07-29 Created: 2019-07-29 Last updated: 2019-07-29Bibliographically approved
Lagriffoul, F., Dantam, N. T., Garrett, C., Akbari, A., Srivastava, S. & Kavraki, L. E. (2018). Platform-Independent Benchmarks for Task and Motion Planning. IEEE Robotics and Automation Letters, 3(4), 3765-3772
Open this publication in new window or tab >>Platform-Independent Benchmarks for Task and Motion Planning
Show others...
2018 (English)In: IEEE Robotics and Automation Letters, ISSN 2377-3766, E-ISSN 1949-3045, Vol. 3, no 4, p. 3765-3772Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018
Keywords
Performance evaluation and benchmarking, task planning, manipulation planning
National Category
Computer Vision and Robotics (Autonomous Systems)
Identifiers
urn:nbn:se:oru:diva-68581 (URN)10.1109/LRA.2018.2856701 (DOI)000441444700012 ()
Note

Funding Agencies:

Swedish Knowledge Foundation (KKS) project "Semantic Robots"  

NSF  IIS 1317849  CCF-1514372 

Spanish Government  DPI2016-80077-R 

Spanish Government through the Grant  FPI 2015 

Available from: 2018-08-27 Created: 2018-08-27 Last updated: 2018-08-27Bibliographically approved
Bidot, J., Karlsson, L., Lagriffoul, F. & Saffiotti, A. (2017). Geometric backtracking for combined task and motion planning in robotic systems. Artificial Intelligence, 247, 229-265
Open this publication in new window or tab >>Geometric backtracking for combined task and motion planning in robotic systems
2017 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 247, p. 229-265Article in journal (Refereed) Published
Abstract [en]

Planners for real robotic systems should not only reason about abstract actions, but also about aspects related to physical execution such as kinematics and geometry. We present an approach to hybrid task and motion planning, in which state-based forward-chaining task planning is tightly coupled with motion planning and other forms of geometric reasoning. Our approach is centered around the problem of geometric backtracking that arises in hybrid task and motion planning: in order to satisfy the geometric preconditions of the current action, a planner may need to reconsider geometric choices, such as grasps and poses, that were made for previous actions. Geometric backtracking is a necessary condition for completeness, but it may lead to a dramatic computational explosion due to the large size of the space of geometric states. We explore two avenues to deal with this issue: the use of heuristics based on different geometric conditions to guide the search, and the use of geometric constraints to prune the search space. We empirically evaluate these different approaches, and demonstrate that they improve the performance of hybrid task and motion planning. We demonstrate our hybrid planning approach in two domains: a real, humanoid robotic platform, the DLR Justin robot, performing object manipulation tasks; and a simulated autonomous forklift operating in a warehouse.

Place, publisher, year, edition, pages
Elsevier, 2017
Keywords
Combined task and motion planning; Task planning; Action planning; Path planning; Robotics; Geometric reasoning; Hybrid reasoning; Robot manipulation
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:oru:diva-48015 (URN)10.1016/j.artint.2015.03.005 (DOI)000401401600011 ()2-s2.0-84929590433 (Scopus ID)
Projects
GeRTSAUNA
Funder
EU, FP7, Seventh Framework Programme, 248273Knowledge Foundation
Available from: 2016-02-05 Created: 2016-02-05 Last updated: 2018-01-10Bibliographically approved
Mansouri, M., Lagriffoul, F. & Pecora, F. (2017). Multi Vehicle Routing with Nonholonomic Constraints and Dense Dynamic Obstacles. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS): . Paper presented at IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS 2017), Vancouver, BC, Canada, September 24-28, 2017 (pp. 3522-3529). Institute of Electrical and Electronics Engineers (IEEE)
Open this publication in new window or tab >>Multi Vehicle Routing with Nonholonomic Constraints and Dense Dynamic Obstacles
2017 (English)In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Institute of Electrical and Electronics Engineers (IEEE), 2017, p. 3522-3529Conference paper, Published paper (Refereed)
Abstract [en]

We introduce a variant of the multi-vehicle routing problem which accounts for nonholonomic constraints and dense, dynamic obstacles, called MVRP-DDO. The problem is strongly motivated by an industrial mining application. This paper illustrates how MVRP-DDO relates to other extensions of the vehicle routing problem. We provide an application-independent formulation of MVRP-DDO, as well as a concrete instantiation in a surface mining application. We propose a multi-abstraction search approach to compute an executable plan for the drilling operations of several machines in a very constrained environment. The approach is evaluated in terms of makespan and computation time, both of which are hard industrial requirements.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2017
Series
Proceedings of the ... IEEE/RSJ International Conference on Intelligent Robots and Systems, ISSN 2153-0858, E-ISSN 2153-0866
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:oru:diva-63515 (URN)10.1109/IROS.2017.8206195 (DOI)000426978203076 ()2-s2.0-85041951034 (Scopus ID)978-1-5386-2682-5 (ISBN)978-1-5386-2683-2 (ISBN)
Conference
IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS 2017), Vancouver, BC, Canada, September 24-28, 2017
Projects
Semantic Robots
Funder
Knowledge Foundation, 20140033
Note

Funding Agency:

Atlas Copco Rock Drills AB

Available from: 2017-12-21 Created: 2017-12-21 Last updated: 2018-06-11Bibliographically approved
Lagriffoul, F. (2016). Combining Task and Motion Planning. (Doctoral dissertation). Örebro: Örebro university
Open this publication in new window or tab >>Combining Task and Motion Planning
2016 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

This thesis addresses the problem of automatically computing, given a high-level goal description, a sequence of actions and motion paths for one or several robots to achieve that goal. Also referred to as CTAMP (Combining Task And Motion Planning), this problem may seem trivial at first glance, since efficient solutions have been found for its two underlying problems, namely task planning and motion planning. However, further consideration reveals that combining task and motion planning, in many cases, is not straightforward. We have identified two important issues which are addressed in this thesis.

The first issue originates in the fact that symbolic actions can be geometrically instantiated in multiple ways. Choosing a geometric instance for each action is not trivial, because a “wrong” choice may compromise the feasibility of subsequent actions. To address this issue, in the first part of the thesis we propose a mechanism for backtracking over geometric choices in the context of a partial symbolic plan. This process may greatly increase the complexity of CTAMP. Therefore, we also present a constraint-based approach for pruning out geometric configurations which violate a number of geometric constraints imposed by the action sequence, and by the kinematic models of robots. This approach has been tested with success on the real humanoid robotic platform Justin in the context of the GeRT1 project.

The second issue results from the necessity to interleave symbolic and geometric computations for taking geometric constraints into account at the symbolic level. Indeed, the symbolic search space forms an abstraction of the physical world, hence geometric constraints such as objects occlusions or kinematic constraints are not represented. However, interleaving both search processes is not a workable approach for large problem instances, because the resulting search space is too large. In the second part of the thesis, we propose a novel approach for decoupling symbolic and geometric search spaces, while keeping the symbolic level aware of geometric constraints. Culprit detection mechanisms are used for computing explanations for geometric failures, and these explanations are leveraged at the symbolic level for pruning the search space through inference mechanisms. This approach has been extensively tested in simulation, on different types of single and multiple robot systems.

Place, publisher, year, edition, pages
Örebro: Örebro university, 2016. p. 194
Series
Örebro Studies in Technology, ISSN 1650-8580 ; 67
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:oru:diva-46994 (URN)978-91-7529-113-0 (ISBN)
Public defence
2016-01-29, Teknikhuset, Hörsal T, Örebro universitet, Fakultetsgatan 1, Örebro, 13:15 (English)
Opponent
Supervisors
Available from: 2015-12-08 Created: 2015-12-08 Last updated: 2018-01-10Bibliographically approved
Lagriffoul, F. & Andres, B. (2016). Combining task and motion planning: a culprit detection problem. The international journal of robotics research, 35(8), 890-927
Open this publication in new window or tab >>Combining task and motion planning: a culprit detection problem
2016 (English)In: The international journal of robotics research, ISSN 0278-3649, E-ISSN 1741-3176, Vol. 35, no 8, p. 890-927Article in journal (Refereed) Published
Abstract [en]

Solving problems combining task and motion planning requires searching across a symbolic search space and a geometricsearch space. Because of the semantic gap between symbolic and geometric representations, symbolic sequences of actionsare not guaranteed to be geometrically feasible. This compels us to search in the combined search space, in which frequentbacktracks between symbolic and geometric levels make the search inefficient. We address this problem by guiding symbolicsearch with rich information extracted from the geometric level through culprit detection mechanisms.

Place, publisher, year, edition, pages
London, United Kingdom: Sage Publications, 2016
Keywords
Combined Task and Motion Planning, Manipulation Planning
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:oru:diva-48000 (URN)10.1177/0278364915619022 (DOI)000380018600002 ()2-s2.0-84977141089 (Scopus ID)
Funder
EU, European Research Council, 248273
Available from: 2016-02-05 Created: 2016-02-05 Last updated: 2018-07-09Bibliographically approved
Lagriffoul, F., Dimitrov, D., Bidot, J., Saffiotti, A. & Karlsson, L. (2014). Efficiently combining task and motion planning using geometric constraints. The international journal of robotics research, 33(14), 1726-1747
Open this publication in new window or tab >>Efficiently combining task and motion planning using geometric constraints
Show others...
2014 (English)In: The international journal of robotics research, ISSN 0278-3649, E-ISSN 1741-3176, Vol. 33, no 14, p. 1726-1747Article in journal (Refereed) Published
Abstract [en]

We propose a constraint-based approach to address a class of problems encountered in combined task and motion planning (CTAMP), which we call kinematically constrained problems. CTAMP is a hybrid planning process in which task planning and geometric reasoning are interleaved. During this process, symbolic action sequences generated by a task planner are geometrically evaluated. This geometric evaluation is a search problem per se, which we refer to as geometric backtrack search. In kinematically constrained problems, a significant computational effort is spent on geometric backtrack search, which impairs search at the task level. At the basis of our approach to address this problem, is the introduction of an intermediate layer between task planning and geometric reasoning. A set of constraints is automatically generated from the symbolic action sequences to evaluate, and combined with a set of constraints derived from the kinematic model of the robot. The resulting constraint network is then used to prune the search space during geometric backtrack search. We present experimental evidence that our approach significantly reduces the complexity of geometric backtrack search on various types of problem.

Keywords
Manipulation planning, combining task and motion planning, geometric reasoning
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:oru:diva-40158 (URN)10.1177/0278364914545811 (DOI)000345707000002 ()2-s2.0-84914173646 (Scopus ID)
Note

Funding Agency:

EU FP7 project "Generalizing Robot Manipulation Tasks" (GeRT) 248273

Available from: 2015-01-08 Created: 2015-01-07 Last updated: 2018-01-11Bibliographically approved
Lagriffoul, F., Karlsson, L., Bidot, J. & Saffiotti, A. (2013). Combining Task and Motion Planning is Not Always a Good Idea. In: : . Paper presented at 2013 Robotics: Science and Systems Conference (Workshop "Combined Robot Motion Planning and AI Planning for Practical Applications").
Open this publication in new window or tab >>Combining Task and Motion Planning is Not Always a Good Idea
2013 (English)Conference paper, Published paper (Refereed)
Abstract [en]

Combining task and motion planning requires tointerleave causal and geometric reasoning, in order to guaranteethe plan to be executable in the real world. The resulting searchspace, which is the cross product of the symbolic search spaceand the geometric search space, is huge. Systematically calling ageometric reasoner while evaluating symbolic actions is costly. Onthe other hand, geometric reasoning can prune out large parts ofthis search space if geometrically infeasible actions are detectedearly. Hence, we hypothesized the existence of a search depthlevel, until which geometric reasoning can be interleaved withsymbolic reasoning with tractable combinatorial explosion, whilekeeping the benefits of this pruning. In this paper, we propose asimple model that proves the existence of such search depth level,and validate it empirically through experiments in simulation

National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:oru:diva-30821 (URN)
Conference
2013 Robotics: Science and Systems Conference (Workshop "Combined Robot Motion Planning and AI Planning for Practical Applications")
Funder
EU, FP7, Seventh Framework Programme
Available from: 2013-09-16 Created: 2013-09-16 Last updated: 2018-01-18Bibliographically approved
Karlsson, L., Bidot, J., Lagriffoul, F., Saffiotti, A., Hillenbrand, U. & Schmidt, F. (2012). Combining task and path planning for a humanoid two-arm robotic system. In: Marcello Cirillo, Brian Gerkey, Federico Pecora, Mike Stilman (Ed.), TAMPRA 2012: Proceedings of the Workshop on Combining Task and Motion Planning for Real-World Applications. Paper presented at 2012 TAMPRA Workshop, June 26, 2012, Atibaia, São Paulo, Brazil (pp. 13-20).
Open this publication in new window or tab >>Combining task and path planning for a humanoid two-arm robotic system
Show others...
2012 (English)In: TAMPRA 2012: Proceedings of the Workshop on Combining Task and Motion Planning for Real-World Applications / [ed] Marcello Cirillo, Brian Gerkey, Federico Pecora, Mike Stilman, 2012, p. 13-20Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Research subject
Computer and Systems Science
Identifiers
urn:nbn:se:oru:diva-24401 (URN)
Conference
2012 TAMPRA Workshop, June 26, 2012, Atibaia, São Paulo, Brazil
Projects
GeRT
Funder
EU, FP7, Seventh Framework Programme, 248273
Available from: 2012-08-14 Created: 2012-08-14 Last updated: 2019-04-10Bibliographically approved
Lagriffoul, F., Dimitrov, D., Saffiotti, A. & Karlsson, L. (2012). Constraint propagation on interval bounds for dealing with geometric backtracking. In: Proceedings of  the 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2012): . Paper presented at 25th IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)OCT 07-12, 2012, Algarve, Spain (pp. 957-964). Institute of Electrical and Electronics Engineers (IEEE)
Open this publication in new window or tab >>Constraint propagation on interval bounds for dealing with geometric backtracking
2012 (English)In: Proceedings of  the 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2012), Institute of Electrical and Electronics Engineers (IEEE), 2012, p. 957-964Conference paper, Published paper (Refereed)
Abstract [en]

The combination of task and motion planning presents us with a new problem that we call geometric backtracking. This problem arises from the fact that a single symbolic state or action can be geometrically instantiated in infinitely many ways. When a symbolic action cannot begeometrically validated, we may need to backtrack in thespace of geometric configurations, which greatly increases thecomplexity of the whole planning process. In this paper, weaddress this problem using intervals to represent geometricconfigurations, and constraint propagation techniques to shrinkthese intervals according to the geometric constraints of the problem. After propagation, either (i) the intervals are shrunk, thus reducing the search space in which geometric backtracking may occur, or (ii) the constraints are inconsistent, indicating then infeasibility of the sequence of actions without further effort. We illustrate our approach on scenarios in which a two-arm robot manipulates a set of objects, and report experiments that show how the search space is reduced.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2012
Series
IEEE International Conference on Intelligent Robots and Systems, ISSN 2153-0858
Keywords
robotics, planning
National Category
Computer Vision and Robotics (Autonomous Systems)
Research subject
Computer and Systems Science
Identifiers
urn:nbn:se:oru:diva-24398 (URN)10.1109/IROS.2012.6385972 (DOI)000317042701078 ()2-s2.0-84872299916 (Scopus ID)978-1-4673-1736-8 (ISBN)
Conference
25th IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)OCT 07-12, 2012, Algarve, Spain
Projects
GeRT
Funder
EU, FP7, Seventh Framework Programme
Available from: 2012-08-14 Created: 2012-08-14 Last updated: 2018-01-12Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-8631-7863

Search in DiVA

Show all publications