Earlier work has introduced ontologies to improve the performance of task and motion planning. However, these approaches have not explicitly used first-order axiomatizations for ontologies that are typically used for the specification of spatial constraints, such as mereotopologies. In this paper we demonstrate the application of new mereotopologies to automatically generate spatial constraints that prune the search space of task and motion planning, thereby enabling the semantic coupling of task and motion planning.
Within the factory of the future and the digital industrial transformation [1], the validation (under simulation or real experiment) of complex industrial scenarios (e.g. tasks performed by a manipulator or mobile robot in a cluttered environment) will become increasingly important. Updated products are increasingly integrated, and the tasks related to their life cycle management (e.g. manipulation performed by a human operator such as maintenance or assembly) are likely to be executed under very strong geometric constraints; therefore, industrial companies are expressing the need to validate these tasks at design stage, before manufacturing the corresponding physical prototypes. Such an approach allows the detection of errors as early as possible, reduced development times and costs, and the deployment of more environment-friendly production processes, as fewer defective physical prototypes would be built. To address these issues, we propose to develop new techniques based on the joint use of robotics (namely motion planning) and Artificial Intelligence (AI) techniques.
To validate the feasibility of the targeted scenarios, showing the feasibility of motion is key. Trajectory planning techniques developed by the robotics community since the 1980s [2] are widely used. Their limitations are mainly due to the complexity of the environment models used, which are traditionally purely geometric; neither the environment models nor the methods for exploring these models are based on information relating to the task to be performed. In a complex environment, automatic trajectory planners may require long computation times, fail, or explore or propose solutions of little relevance to the task to be performed. To address these limitations, recent work has focused on collaborative human/planner approaches, which only rarely enable continuous interaction [3][4] [5].
Recent work has demonstrated the utility of higher abstraction level data beyond the purely geometric data traditionally used [6], to improve semantic control on motion planning [7]. Other work has demonstrated the benefits of combining motion planning and learning techniques [ 8]. While these apporoaches have shown the necessity to consider jointly task and motion planning [9] [10] and the interest for using ontologies in robotic applications [11][12] (often to bridge the gap between low level motion planning and high level task planning), the integration of these AI and robotics techniques is still a challenge [13].
Previous work has indeed demonstrated use of ontologies within task and motion planning, but it has not made use of the full range of mereotopologies available, thereby limiting its usability and generalizability. The role of using spatial constraints in reducing the search space at the geometric level has been recognized, but this raises the question of the specification of the spatial constraints. In this paper we demonstrate the application of new mereotopologies to automatically generate spatial constraints that enable the semantic coupling of task and motion planning. We use a simple battery changing scenario to illustrate how the spatial constraints are generated from the mereotopology.
This paper is organized as follows: section 2 introduces related former works our contributions rely on. Section 3 presents our contribution, illustrated on a challenging and relevant use case. Section 4 summarizes our contributions and presents the next steps and perspectives of this work.
In this section, we review earlier work on ontologies and semantic coupling of task and motion planning (TAMP) in the context of assistance to manipulation in Virtual Reality (VR) [14], which forms the basis for the novel contributions presented in the current paper.
The first step in the semantic coupling of task and motion planning was to propose an approach for interactive and immersive motion planning using visuo-haptic guidance and addressing control sharing between the motion planner and the human operator [15]. To face to well-known limitations of automatic path planning [16] addressed in section 1, the proposed framework was improved by the involvement of higher abstraction level data for environment modelling and motion planning [16] (see figure 1).
Environment Modelling The environment is composed of two parts: rigid bodies (static or mobile obstacles) and free space. The rigid bodies model is composed of two layers: a geometrical layer where they are represented by classical geometric primitives (e.g. polyhedral models as in Figure 1 (a)), and a semantic layer associating to each rigid body high-abstraction text or numerical information (e.g. shape). The free space model is composed of 3 layers. The geometrical layer relies on the use of a quadtree in 2D or octree in 3D [17] (see Figure 1 (b)). The topological layer is based on a graph called topological graph (see Figure 1 (c)), which connects places (the arcs of the graph) and borders (the nodes). Each place and border is associated with a set of geometrical cells in the geometrical layer. The semantic layer (see Figure 1 (d)) is made of text or numerical attributes attached to the places and borders of the topological graph and describing the shape or the complexity to be crossed (e.g. level of clutter). Multi-level Path Planning Strategy The multi-level path planning strategy proposed uses the multi-layer environment model of free space and is based on 2 steps performed consecutively. First, coarse planning finds a (minimum cost) path within the topological graph. This topological path is made of topological steps, such that each step is composed of a place to cross and a border to reach. The semantic layer of the environment provides control on the topological planning through the definition of the costs associated to the nodes and arcs of the graph as functions of the semantic information associated to them (see Figure 1 (d)). Second, a fine planning step uses the geometrical models of the rigid bodies and of free-space to solve classical path planning queries for each topological step.
As current approaches focus on the validation of complex tasks to be performed under strong geometric constraints, the geometrical path planner used at the fine motion planning level described above is a well-known probabilistic algorithm, namely Rapidly-exploring Random Tree (RRT) [18], which performs a probabilistic exploration of free space to find a collision-free trajectory and iteratively and locally extends a roadmap. The RRT algorithm is probabilistically complete but does not guarantee finite-time solutions.
Nevertheless, merely showing the feasibility of motion is not enough to validate complex tasks, and it is necessary to consider task [19] and motion planning techniques jointly [20], to model and use task-oriented knowledge such as ontologies [21] to take into account spatial relations expressed at the task and/or motion planning levels.
Coupling Task and Motion Planning: In a first step towards semantically coupling task and motion planning, an original strategy was proposed for the semantic coupling of path planning and a primitive action of a task plan for the simulation of manipulation tasks in a virtual 3D environment [22]. The approach relies on the proposal of two original ontologies: a 3D environment ontology modelling the 3D environment according to the multi-level approach described above, and an ontology of action-specific knowledge defining the knowledge of the environment of a particular task, and the spatial knowledge that describes relative location between two objects, between an object and an area, and between two geometric elements. The proposed approach supports the automatic definition of path planning queries for the primitive actions of a task plan, together with task-related geometric constraints on these queries.
Figure 2 presents the global approach. Two important classes are involved: 1) the Primitive Action Specification (PAS) related to the primitive action identity (e.g. insert, put) and its parameters (manipulated object) together with spatial constraints expressed at the task level. and 2) the Path Planning Query Description (PPQD) related to the manipulated object, the start and goal configurations, and the geometric constraints on the motion planning query.
First, a PAS is generated automatically from the information related to the primitive task to be performed. A set of associated spatial constraints is manually assigned by a human operator. Then, the Path Planning Query Constructor generates a related path planning query description (PPQD). The manipulated object in this PPQD is directly extracted from the primitive action specification. The goal configuration is randomly sampled in the goal region. A reasoner is invoked to generate the related geometric constraints from the spatial constraints using predefined SWRL rules.
This approach allows the improvement of the state of the art from two points of view. First, it allows a very significant improvement of path planning performances (processing times, relevance of the proposed path) through better semantic control. Second, if compared to hard-coded geometric constraints, the proposed ontology-based approach introduces a more flexible way of defining geometric constraints through an inference process, and can be adapted to different applications of manipulation tasks.
Nervertheless, this work still suffers a number of limitations. The input spatial constraints are entered manually where it would be interesting to generate them automatically. Like other works dealing with the use of ontologies for robotics, it also faces the issue of the generic expression of the wide diversity of spatial constraints [23] [24] [25]. A use of the full range of mereotopologies available and an explicit use of first-order axiomatizations for ontologies that are typically used for the specification of spatial constraints might solve these difficulties.
The signature of the basic mereotopology Tmt ) consists of two primitive binary relations, parthood (P) and connection (C) [26]. The axioms of the theory1 state that connection is a reflexive and symmetric relation, while parthood is a reflexive, transitive, and anti-symmetric relation. In addition, if one individual is connected to another, then the first one is also connected to any individual which the second is part of.
In practice, most approaches to mereotopology use RCC8, which is a set of eight jointly exhaustive and pairwise disjoint binary relations representing mereotopological relationships between (ordered) pairs of individuals. The results of [27] show that the mereotopology MT corresponds to an extension of the first-order theory of the RCC8 composition table. This means that the underlying mereotopology for RCC8 used in such settings does not include any of the basic mereotopological principles (i.e., supplementation, atomicity, extensibility, and closure under sum and product), since these principles are not axioms in MT. 2.2.1. Connected Induced Subgraph Mereotopology In many domains (such as manufacturing assemblies, molecular structure, gene sequences, and convex time intervals) the assumption that any two underlapping elements have a sum is not valid. Instead, mereological sums must be connected objects. However, there has been little work in providing an axiomatization of such a nonclassical mereology. Based on the observation that the underlying structures in these domains are represented by graphs, we propose a new mereotopology that axiomatizes the connected induced subgraph containment ordering for a graph, and then identify an axiomatization of the mereology that is a module of the mereotopology.
In the mereotopology Tcisco_mt 2, the sum of two elements exists iff they are connected. A key insight is that the underlying structure that specifies an object is a graph, and all parts of the object correspond to connected induced subgraphs of that graph [28]. We therefore introduce the parthood and connection structure on the set of connected induced subgraphs of a graph and use this as the basis for the mereotopology for inferring spatial constraints. 1colore.oor.net/combined_mereotopology/mt.clif 2colore.oor.net/combined_mereotopology/cisco_mt.clif
The primary application of mereotopologies is through the automatic generation of spatial constraints that can prune the search space so that only topologically feasible paths are considered. For example, if x is externally connected to y, and y is a tangential part of z, then we can use RCC8 to infer that x is connected to z. The use of mereotopology improves the semantic coupling of task and motion planning within the framework presented in section 2.1, by providing enhanced reasoning with the spatial constraints at the task level and geometric constraints at the motion level.
To illustrate these potential benefits, let us consider the following case study: the replacement of 2 cylindrical batteries in a container (see figure 3). This example is non trivial because it requires the explicit representation of mereology, topology and orientation. The batteries must be inserted in a specific direction to respect polarity. It is also relevant to illustrate the necessity to couple task and motion planning. The targeted task may give way to diverse task plans, while the order in which we remove and insert the batteries has a significant impact on accessiblity.
A battery is oriented, i.e. has a base and a knob, and so is a battery slot in the container, as it is equipped with a spring at one end, and an indentation at the other end. The expression of mereotopological constraints at the task level (the battery is inserted inside a given slot) allows the automatic generation of mereotopological constraints expressing that the battery should be inserted so that the base is in contact with the spring, and the knob is in contact with the indentation.
The expression of such inferred constraints also supports the inference of knowledge and constraints at the geometric motion planning level. First, the fact that the base is in contact with the spring, and the knob is in contact with the indentation, will allow to determine an acceptable ifnal geometric configuration (or a set of these) for the manipulated battery. This paves the way for improved pruning of the search space for the motion planning algorithms involved by discarding irrelevant geometric configurations (from an orientation point of view for example, in our case here).
We define the scenario as a set of first order logic axioms. Axiom (
EC(battery, compartment)
∀x, y EC(x, spring) ∧ EC(y, spring) ⊃ (x = y)
(
This is followed by the next proposition which states the possible goal states - otherwise known as combinations of connections between the battery and the compartment. The correct combination would have the compartment indent connected to the battery knob, and the compartment spring connected to the battery base. From these constraints, we can use Prover9 to derive Tcisco_mt ∪ Σbattery |= EC(indent, knob) ∨ EC(spring, base)
In this paper, we have presented how the application of the full range of mereotopologies available and an explicit use of first-order axiomatizations for ontologies that are typically used for the specification of spatial constraints improves the semantic coupling of task and motion planning for robotic tasks or for the assistance to manipulation.
Next steps for this work will consist in improving the architecture presented in figure 2 by integrating: 1) a process for the (automatic) expression of task-related mereotopological constraints 2) a process extracting geometric information from the environment model to be used in the inference of geometric constraints on the motion planning (e.g. geometric locations of "contact points" from the CAD model of the environment) and 3) a process inferring geometric constraints on the motion planning process from the (mereotopological) spatial constraints expressed at the task level
The complete approach will be validated on the use case presented in section 3. In the longer term, the approach should be extended to the semantic coupling of motion planning and a complete task plan (not merely a primitive action), in a robotic context, then in the context of interactive and immersive simulation in VR. doi:10.1016/j.jmsy.2021.03.006. [2] J. Latombe, Robot Motion Planning, The Springer International Series in Engineering and Computer Science, Springer US, 2012. URL: https://books.google.ca/books?id= nQ7aBwAAQBAJ. [3] D. Flavigné, M. Taïx, E. Ferre, Interactive motion planning for assembly tasks, ROMAN 2009 - The 18th IEEE International Symposium on Robot and Human Interactive Communication (2009) 430–435. [4] N. Blin, M. Taïx, P. Fillatreau, J.-Y. Fourquet, Tuning interaction in motion planning with contact, in: 2016 25th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN), 2016. doi:10.1109/ROMAN.2016.7745231. [5] S. Patil, R. Alterovitz, Interactive motion planning for steerable needles in 3d environments with obstacles, in: 2010 3rd IEEE RAS and EMBS International Conference on Biomedical Robotics and Biomechatronics, BioRob 2010, 2010, pp. 893 – 899. doi:10.1109/BIOROB. 2010.5625965. [6] R. Iacob, D. Popescu, P. Mitrouchev, Assembly/disassembly analysis and modeling techniques: A review, Strojniski Vestnik 58 (2012) 653–664. doi:10.5545/sv-jme.2011. 183. [7] D. Belter, J. Wietrzykowski, P. Skrzypczyn´ski, Employing natural terrain semantics in motion planning for a multi-legged robot, Journal of Intelligent and Robotic Systems 93 (2019). doi:10.1007/s10846-018-0865-x. [8] E. Pairet, C. Chamzas, Y. R. Petillot, L. Kavraki, Path planning for manipulation using experience-driven random trees, IEEE Robotics and Automation Letters 6 (2021) 3295– 3302. doi:10.1109/lra.2021.3063063. [9] A. M. Wells, N. T. Dantam, A. Shrivastava, L. E. Kavraki, Learning feasibility for task and motion planning in tabletop environments, IEEE Robotics and Automation Letters 4 (2019) 1255–1262. [10] T. Pan, A. M. Wells, R. Shome, L. E. Kavraki, A general task and motion planning framework for multiple manipulators, in: 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE Press, 2021, p. 3168–3174. URL: https://doi. org/10.1109/IROS51168.2021.9636119. doi:10.1109/IROS51168.2021.9636119. [11] A. Olivares-Alarcos, S. Foix, S. Borgo, Guillem Alenyà,, Ocra – an ontology for collaborative robotics and adaptation, Computers in Industry 138 (2022) 103627. URL: https://www.sciencedirect.com/science/article/pii/S0166361522000227. doi:https://doi. org/10.1016/j.compind.2022.103627. [12] R. Bernardo, J. M. Sousa, P. J. Gonçalves, A novel framework to improve motion planning of robotic systems through semantic knowledge-based reasoning, Computers and Industrial Engineering 182 (2023) 109345. URL: https://www.sciencedirect.com/science/article/pii/ S0360835223003698. doi:https://doi.org/10.1016/j.cie.2023.109345. [13] H. Guo, F. Wu, Y. Qin, R. Li, K. Li, K. Li, Recent trends in task and motion planning for robotics: A survey, ACM Comput. Surv. (2023). URL: https://doi.org/10.1145/3583136. doi:10.1145/3583136, just Accepted. [14] S. Cailhol, P. Fillatreau, Z. Yingshen, J.-Y. Fourquet, A hierarchic approach for path planning in virtual reality, International Journal for Interactive Design and Manufacturing (IJIDeM) 9 (2015). doi:10.1007/s12008-015-0272-5. [15] N. Ladeveze, J.-Y. Fourquet, B. Puel, M. Taïx, Haptic assembly and disassembly task assistance using interactive path planning, in: 2009 IEEE Virtual Reality Conference, 2009, pp. 19 – 25. doi:10.1109/VR.2009.4810993. [16] S. Cailhol, P. Fillatreau, Z. Yingshen, J.-Y. Fourquet, Multi-layer path planning control for the simulation of manipulation tasks: Involving semantics and topology, Robotics and Computer-Integrated Manufacturing 57 (2019) 17–28. doi:10.1016/j.rcim.2018.10. 010. [17] R. Fisher, T. Breckon, K. Dawson-Howe, A. Fitzgibbon, C. Robertson, E. Trucco, C. Williams, B: Fisher/Dictionary of Computer Vision and Image Processing, 2016, pp. 25–39. doi:10.1002/9781119286462.ch3. [18] S. M. LaValle, Rapidly-exploring random trees : a new tool for path planning, The annual research report (1998). [19] M. Ghallab, D. S. Nau, P. Traverso, Automated Planning and Acting, Cambridge University
Press, 2016. [20] A. Akbari, F. Lagriffoul, J. Rosell, Combined heuristic task and motion planning for bi-manual robots, Auton. Robots 43 (2019) 1575–1590. URL: https://doi.org/10.1007/ s10514-018-9817-3. doi:10.1007/s10514-018-9817-3. [21] Muhayyuddin, A. Aliakbar, J. Rosell, Ontological physics-based motion planning for manipulation, 2015 IEEE 20th Conference on Emerging Technologies & Factory Automation (ETFA) (2015) 1–7. URL: https://api.semanticscholar.org/CorpusID:2195730. [22] Y. Zhao, P. Fillatreau, L. Elmhadhbi, H. Karray, B. Archimède, Semantic coupling of path planning and a primitive action of a task plan for the simulation of manipulation tasks in a virtual 3d environment, Robotics and Computer-Integrated Manufacturing 73 (2022) 102255. doi:10.1016/j.rcim.2021.102255. [23] A. Borrmann, J. Hyvärinen, E. Rank, Spatial constraints in collaborative design processes, Proceedings of the International Conference on Intelligent Computing in Engineering (2009). [24] L. Belouaer, M. Bouzid, A.-I. Mouaddib, Spatial knowledge in planning language, in:
International Conference on Knowledge Engineering and Ontology Development, 2011. [25] G. Touya, S. Balley, C. Duchêne, K. Jaara, N. Regnauld, N. Gould, Towards an ontology of spatial relations and relational constraints, in: 15th ICA workshop on generalisation and multiple representation, 2012. [26] R. Casati, A. C. Varzi, Parts and Places: The Structures of Spatial Representation, The MIT Press, 2003. URL: https://doi.org/10.7551/mitpress/5253.001.0001. doi:10.7551/ mitpress/5253.001.0001. [27] B. Aameri, M. Grüninger, Location ontologies based on mereotopological pluralism,
Applied Ontology 15 (2020) 135–184. [28] M. Grüninger, C. Chui, Y. Ru, J. Thai, A mereology for connected structures, in: Formal Ontology in Information Systems, IOS Press, 2020, pp. 171–185.