An Approach to Compose Shapes Described Qualitatively: A Proof-of-Concept Albert Pich and Zoe Falomir 1 Extended Abstract This paper presents a proof-of-concept towards solving spatial reasoning tests which deal with object composition. This approach is inspired by the Qualitative Shape Descriptor (QSD) by Falomir et al. (2013), the juxtaposition scheme QSD- Jux by Museros et al. (2011) and the framework Point-Line-Circuit-Area (PLCA) by Takahashi et al. (2015). This new approach, LogC-QSD, uses circuits to describe networks of composed objects and QSD to describe the shape of the boundary of the resulting composition. LogC-QSD differs from QSD-Jux in the use of circuits to describe networks between the composed objects. LogC- QSD can juxtapose more than two objects using different connections (i.e. only one point connection). And LogC-QSD differs from PLCA by describing of the shape of the objects and the circuit qualitatively. Attributes as angles, lengths, or convexities are not described in PLCA. As a proof-of-concept, the presented approach has been implemented using Prolog programming language, which is based on Horn clauses and 1st order logic. The testing framework has been SWI-Prolog (Wielemaker et al., 2012) and promising results are obtained. 1.1 Overview of LogC-QSD Target objects The target objects of LogC-QSD are those which can be described with QSD, that is, a two-dimensional object with at least three relevant points in its boundary. Thus, a set of relevant points, denoted by {P0 , P1 , ..., PN }, N 3, determines the shape of the object. Each relevant point Pi is described depending on the relation appearing between Pi and the previous point, Pi 1 , and Pi and the following point, Pi+1 . And each QSDi is composed by a set of four features, which are defined as: QSDi (Pi 1 , Pi , Pi+1 ) =< ECi , Ai |TCi ,Ci , Li > where, - EC refers to the Edge Connection, which can be line line, line curve, curve line, curve curve or curvature point depending if the point is connecting lines, curves, or it is a curvature point; - A refers to the Angle at the relevant point and takes the following values very-acute (va), half-right (hr), acute (a), right (r), obtuse (o), 3-quarters-right (tqr), very-obtuse (vo), plane(pl). - TC refers to the Type of Curvature and takes the following values very acute, acute, semicircular, plane, very plane. - C refers to the convexity at the point Pi and takes the values: concave (cv), convex (cx) and plane (pl). - L refers to the length of the edge between Pi 1 and Pi and takes the vales: smaller-short (ss), short (s), larger-short (ls), quarter-longest (ql), smaller-medium (sm), medium (m), larger-medium (lm), half-longest (hl), smaller-long (sl), long(l), larger-long (ll), and longest (lst). The QSD descriptions of the objects appearing in the Fig. 1 objects are: ?- get_QSD_List(objectA,A). A = [[p1,line-line,r,cx,m],[p2,line-line,r,cx,m],[p3,line-line,r,cx,m],[p4,line-line,r,cx,m]] . Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A.M. Olteteanu, Z. Falomir (eds.): Proceedings of ProSocrates 2017: Symposium on Problem-solving, Creativity and Spatial Reasoning in Cognitive Systems, at Delmenhorst, Germany, July 2017, published at http://ceur-ws.org 40 (a) Object A (b) Object B Fig. 1 Examples of objects described by QSD. That means that objectA has 4 points (p1 , p2 , p3 , p4 ) which are described using QSD, the description of p1 mean that it connects two lines (line-line), has a right angle (r), the angle defined is convex (cx) and the length is medium (m). The rest of the points have the same description. In the same way, the object B is described. ?- get_QSD_List(objectB,B). B= [[q1,line-line,a,cx,m], [q2,line-line,a,cx,hl], [q3,line-line,r,cx,m]]. Connections between Objects The connections are described qualitatively according to their features and cover objects connected by edges or by points. A composition between two objects always have a pair of connections, which are defined as follows: Ci (A, B) =< KC , PA |LA , PB |LB , AC >, i = {1, 2} where: - KC is the kind of connection between the points or lines; - PA |LA is the point or line of the object A involved in the connection; - PB |LB is the point or line of the object B involved in the connection; - AC is the exterior angle of the connection that only takes values when the same point belongs to both pair of connec- tions. Fig. 2 shows some Connections as examples: point-point (p-p), point-line (p-l) and line-point (l-p). (a) Objects A and B (b) Objects C and D (c) Objects E and F Fig. 2 Kinds of connections: (a) point-point/point-point; (b) point-point/point-point; (c) point-line/line-point. Let us name (A, B),(C, D) and (E, F) as the pair of objects in the previous Figure, then their connections can be defined as: • C1 (A, B) = (point point, p2, q1), C2 (A, B) = (point point, q3, p3); • C1 (C, D) = (point point, p2, q4, right), C2 (C, D) = (point point, q4, p2, right); • C1 (E, F) = (point line, p3, f 4, acute),C2 (E, F) = (line point, f 4, p3, obtuse). That is, A and B are connected in C1 by points p2 and q1 and also in C2 by points q3 and p3 . Then, C and D are connected in C1 by p2 and q4 and also in C2 by q4 and p2 , note that even if the same points are involved, two QSD descriptions are required for the same point since it connects different pairs of points, that is, QSD(p1, [p2, q4], q1) 6= QSD(q3, [q4, p2], p3). Furthermore, as the same point belongs to both connections, an exterior angle is required. The objects E and F are connected in C1 by p3 and f 4 and also in C2 by f4 and p3 , as mentioned before, two descriptions are needed since QSD(p2, [ f 4, p3], q1) 6= QSD(q4, [p3, f 4], p4), as well as an exterior angle. 41 Logic Composition of QSD (LogC-QSD) A Logic Composition of objects described qualitatively (LogC-QSD) is defined as follows. Given two objects, A and B, described according the Qualitative Shape Descriptor (Falomir et al., 2013) (QSDA , QSDB ) and the connections between them (C(A, B)) the QSD description of the composed object is obtained. LogC(QSDA , QSDB ,C(A, B)) = QSDAB The result is another QSD description, QSDAB , that can be composed again. In general, the LogC-QSD can compose N objects, requiring the composition of two objects at a time. The LogC-QSD concerns two steps. In the fist one, a network describing the composition of objects is built. In the second step the network is characterized regarding: (i) the QSD of the provided objects, (ii) the kind of connections, and (iii) the new composed features of angle, convexity and length in the object connection. Object Composition Network This network is built by the edges of the objects and the kind of connections between them. Depending on the kind of connection happening between the objects, a different procedure is followed. As QSD describes the objects by their points in a clockwise order, the LogC-QSD also follow this convention. The network is constructed according to the next steps: 1. Starting from the first object, A, from the first relevant point to the point or line involved in the first connection, all the edges are stored to the resulting network QSDN ; 2. When a connection happens, the kind of connection and the pair of edges involved are stored together. In general, if a point (pi ) is involved in the connection the following edge (ei = (pi , pi+1 )) is stored. Otherwise, if a line is involved, the edge which contains this line is stored; 3. The rest of the edges from the next object, B, are stored in QSDN until the next connection is reached; 4. The step 2 is repeated in the opposite order, that is, from the second object, B, to the first object, A; 5. Finally, the rest of the edges from the first object are stored in QSDN . As an example, the construction of the composition network of objects in Fig. 3 is presented. Note that this network is constructed progressively taking the objects in pairs as it is explained next. Fig. 3 Composition of the objects A,B,C and D from left to right. ?- network(A,p3,B,f4,NAB). NAB = [e1, e2, [p-l,e3, f4], f1, f2, f3, [l-p,f4,e3], e3, e4]. When calculating the composition network between the first object in Fig. 3, A, and the second object, B, the results show that: the edges e1 and e2 are stored in the network (QSDNAB ), then the point p3 is reached, which belongs to the point-line (p-l) connection,so the kind of connection together with the following edge to the point involved in the connection (e3 ) and the edge which contains the line ( f4 ) are stored, that is, [p-l,e3 , f4 ]. Then, the rest of the object B is stored until the line involved in the connection ( f 4) is reached, and f1 , f2 and f3 are stored. Then, a line-point (l-p) connection is happening, so, following the same process as before, the kind of connection together with the edge which contains the line involved, and the following edge to the point involved (e3 ) are stored, that is, [l-p, f4 , e3 ]. Finally, the rest of the edges (e3 , e4 ) from the object A are stored. ?- network(NAB,f2,C,g3,NABC). NXY = [e1, e2, [p-l,e3, f4], f1, [p-p,f2,g1], g2, [p-p,g3,f2], f3, [l-p,f4,e3], e3, e4]. 42 The same process is followed in the composition between the third object in Fig. 3, C, and the previously obtained composition network (QSDNAB ). That is, e1 , e2 , [p l, e3 , f4 ], f1 are stored, then a point-point (p-p) connection is reached and stored together with the corresponding edges, [p p, f2 , g1 ], then the rest of the object C (g2 ) is stored until the second connection [p p, g3 , f2 ] is reached and stored, and finally the rest of the previously composed network ( f 3, [l p, f4 , e3 ], e3 , e4 ) is stored. ?- network(NABC,g1,D,s1,NABCD). NABCD = [e1, e2,[p-l,e3, f4], f1, [p-p,f2,g1],[l-p,g1,h1],h2,[p-p,h3,g2],[p-p,g3,f3], [l-p,f4,e3],e3,e4]. Finally, the composition network between the fourth object in Fig. 3, D, and the previous composition network (QSDNABC ) is constructed in the same way. Describing the QSD of the Object Composition Network In this second step, the obtained network is characterized regarding: (i) the QSD of the provided objects, (ii) the kind of connections, and (iii) the new composed features (i.e. edge-connection, angle, convexity and length) defined for the connections. For any edge that does not take part in a connection, the source point of the edge is chosen and its QSD description is obtained from the knowledge base. For example, given e1 = (p1 , p2 ), the characterization of p1 is obtained: ?- edge(e1,PSource,_), hasQSDpoint(objectA,PSource,_,_,EC,A,C,L). PSource=p1, EC=line-line, A=r, C=cx, L=l. The QSD corresponding to the point p1 is obtained: [line-line,right,convex,a] For the edges with connections, the following distinctions are made: • If the two connections define a slope. Then, the important feature to analyze is the length: – If the connected edges have the same lenght, the composition operation finishes composing the angle and convexity at the connection points. – If the connected edges have different length, then these lengths must be added or subtracted, depending on the case, and the angles must be also calculated. • If the same point belongs to the pair of connections between two objects, an external Angle is needed, otherwise infinite possibilities can be found. For the connection pair line-point [l-p,g1 , h1 ], the endpoint of g1 and the source point of h1 are taken, obtaining r2 and s1 respectively. For example, for the connection pair point-point [p-p,h3 , g2 ], the source point of the edges are chosen and its QSD description is stored, obtaining: ?- hasQSDpoint(objectD,s3,_,_,TC,Angle,Convexity,Length). PSource=s3, TC=line-line, Angle=hr, Convexity=cx, Length=l. ?- hasQSDpoint(objectC,r2,_,_,TC,Angle,Convexity,Length). PSource=r2, TC=line-line, Angle=hr, Convexity=cx, Length=lst. Then, the features edges connected, angles and convexities are composed according to the composition tables. In this case, the length is taken from the point s3 . ?- compose_ec(line-line,line-line,EC). EC=line-line. ?- compose_angles(hr,cx,hr,cx,Angle,Convexity). Angle=r, Convexity=cx. Therefore, the QSD of the composed point (s3 , r2 ) = [line-line, right, convex, a] is obtained. For the connection pair line-point [l-p,g1 , h1 ], the endpoint of g1 and the source point of h1 are taken, obtaining r2 and s1 respectively. ?- hasQSDpoint(objectC,r2,_,_,EC,A,C,L). PSource=r2, EC=line-line, A=hr, C=cx, L=lst. ?- hasQSDpoint(objectD,s1,_,_,EC,A,C,L). PSource=s3, EC=line-line, A=r, C=cx, L=hl. The feature edges connected (EC) is operated as before, the angles and convexities from s1 are composed with the plane angle, without requiring an exterior angle, and the lengths are composed, requiring a subtraction/decomposition between 43 r2 and s1 . Note that the same composition tables are used for the subtraction/decomposition operation, only changing the order of the variables. ?- compose_ec(line-line,line-line,EC) EC=line-line. ?- compose_angles(r,cx,pl,pl,A,C). A=r, C=cv. ?- compose_length(hl,L,lst). L=hl. And the QSD of the composed point (g1 , s1 ) is defined as [line-line, right, concave, hb]. After characterizing the network, the resulting QSDR description is obtained as follows. ?- features_Points(NABCD,FP). FP = [[p1,line-line,r,cx,l], [p2,line-line,r,cx,l], [[p3,f4],line-line,v-a,cv,l], [q1,r,cx,hl], [[q2,r1],tqr,cx,l], [[g1,s1],r,cv,hl], [s2,hr,cx,hl], [[s3,r2],r,cx,l], [[r3,q3],pl,pl,l], [q4,r,cx,l], [[f4,p3],a,cv,s], [p4,r,cx,l]]. Finally, the points with plane angles are removed and their lengths are composed. The result obtained is the following: ?- remove_Planes(FP,QSD). QSD = [[p1,line-line,r,cx,a], [p2,line-line,right,cx,a], [[p3,f4],line-line,v-a,cv,a], [q1,r,cx,hb], [[q2,r1],tqr,cx,a], [[g1,s1],r,cv,hb], [s2,hr,cx,hb], [[s3,r2],r,cx,a], [q4,r,cx,b_a], [[f4,p3],a,cv,c], [p4,r,cx,a]]. When some connections are not specified, the LogC-QSD approach return all the possibles compositions that satisfy those who are specified. Likewise, if no connection is specified, the LogC-QSD approach obtains all the possible compo- sitions between the objects. The application is also able to discard impossible compositions and offers feedback about the reason of discarding. Motivation and Future Work The motivation of the LogC-QSD approach is to develop algorithms of spatial reasoning able to solve object composition tasks cognitively. Traditional algorithms in AI solve puzzles using heuristics and lots of computational effort since they find the correct solution. As this is not a cognitive solution, that is, it is not usually applied by humans, this paper explores how spatial logics can improve common reasoning about space. Furthermore, since the target objects of the LogC-QSD are described qualitatively and the implementation is based on logics, the LogC-QSD is able to provide feedback that can be understood by humans. As future work, the LogC-QSD approach intends to improve spatial logic reasoning in intelligent systems (i.e. video game, robotic agents, etc.). Acknowledgements The support by the project Cognitive Qualitative Descriptions and Applications (CogQDA) funded by the Central Research Development Fund (CRDF) at University of Bremen through the 04-Independent Projects for Postdocs action and the European Erasmus+ Internship program are very acknowledged. References Falomir, Z., Gonzalez-Abril, L., Museros, L., and Ortega, J. (2013). Measures of similarity between objects from a quali- tative shape description. Spat. Cogn. Comput., 13:181 – 218. Museros, L., Falomir, Z., Gonzalez-Abril, L., and Velasco, F. (2011). A qualitative shape description scheme for generating new manufactured shapes. In 25th International Workshop on Qualitative Reasoning (QR), co-located at the 22nd Joint International Conference on Artificial Intelligence (IJCAI), Barcelona, Spain. Takahashi, K., Goto, M., and Miwa, H. (2015). Construction of a planar PLCA expression: A qualitative treatment of spatial data. In Agents and Artificial Intelligence - 7th International Conference, ICAART 2015, Lisbon, Portugal, January 10-12, 2015, Revised Selected Papers, pages 298–315. Wielemaker, J., Schrijvers, T., Triska, M., and Lager, T. (2012). SWI-Prolog. TPLP, 12(1-2):67–96. 44