2 Background

This section briefly describes (i) Building Information Modeling (BIM), (ii) the industry foundation classes (IFC), a standard for openBIM data exchange, and (iii) s(CASP), a goal-directed implementation of CASP.

3 Modeling vague concepts

We present now a proposal to represent vague concepts using s(CASP). The formal representation of legal norms to automate reasoning and/or check compliance is well known in the literature. There are several proposals for deterministic rules. However, none of the existing proposals, based on Prolog or standard ASP, can efficiently represent vague concepts due to unknown information, ambiguity, and/or administrative discretion.

In the room there is at least one window, and each window must be wider than 0.60 m. If the room is small, it can be between 0.50 and 0.60 m wide.

We can encode this norm using default negation:

However, without information on the size of the room or what is the criteria to consider that a room is small, it is not possible to determine whether the room is small and only the first rule would succeed.

To encode the absence of information we propose the use of the stable model semantics by Gelfond and Lifschitz (Reference Gelfond and Lifschitz1988), which makes it possible to reason about various scenarios simultaneously, for example, in the previous example we can consider two scenarios (models): in one a given room is small and in the other, it is not.

Example 4 (Example 3 (cont.)) Figure 1 models a hotel with eight rooms, for which we only know the size of three (lines 1-3). Following the patterns by Arias et al. (Reference Arias, Moreno-Rebato, Rodriguez-García and Ossowski2021), lines 8-9 make it possible to reason considering (i) unknown information (size of rooms r4 to r8), and/or (ii) vague concepts: line 5 states that a room smaller than 10 m $^2$ is small and line 6 states that a room larger than 20 m $^2$ is not small. However, it is not clear whether rooms with size between 10 and 20 m $^2$ are small or not. Line 8 captures that there is evidence that the room is small, line 9 captures the case when there is an explicit evidence (there is proof) that the room is not small, and lines 10-11 generate two possible models otherwise. Finally, determines whether a room is small or not based on evidence and/or assumptions: for room r1 the query returns , for r2 it returns , and for the other rooms it returns both alternatives: assuming that holds and assuming that holds.

Fig. 1. Code representing vague and unknown information (available at room.pl).

4 Modeling and manipulating 3D objects

We will now describe our proposal to model and manipulate geometrical information used to represent 3D objects which will be used to model buildings, infrastructures, etc. using constraints. Additionally, we show how the operations that manipulate these objects can also be used to infer new knowledge and/or to verify that geometrical data and non-geometrical information are consistent at each stage of the project development.

4.1 Representing 3D objects using linear equations

Any 3D object can be approximated as the union of convex shapes. The simplest shape to represent with linear equations is a box with edges parallel to the axes of coordinates. Assuming that $P_a$ and $P_b$ are opposing vertices with $P_a$ being the one closest to the coordinate origin, the box is a set of points P with coordinates (X, Y, Z) (resp. $(X_a, Y_a, Z_a)$ for $P_a$ and similarly for $P_b$ ) such that

\begin{equation*}X \geq X_a \land X < X_b \land Y \geq Y_a \land Y < Y_b\land Z \geq Z_a \land Z < Z_b\end{equation*}

Equations of this type can be easily managed using a simple linear constraint solver. In this paper, we use the well-known CLP(Q) solver by Holzbaur (Reference Holzbaur1995) ^{Footnote 1} and we represent such an object with the term where are variables adequately constrained as shown before. When a complex object has to be decomposed into convex shapes $S_i$ , we define this object as the set of points P such that $P \in S_1 \lor P \in S_2 \lor \dots \lor P \in S_n$ . Since CLP(Q) does not provide logical disjunction as part of the constraint solver’s operations, we explicitly represent the union of objects as a list of convex shapes , where encodes the variables that carry the constraints corresponding to the linear equations of each $S_i$ .

Example 5. A 3D box whose defining vertices are $P_a$ and $P_b$ (represented, resp. as , is encoded as:

where the box is represented with a list that contains a single convex shape.

Most objects in the definition of a building are extruded 2D convex polygons, and therefore having an explicit operation for this case is useful and it illustrates the power of using CLP for modeling building structures.

Example 6. Given a 3D object defined by its base (a convex polygon determined by its vertices $A,B,C, \dots$ in clockwise order) and its height H, its representation is:

4.2 Operations on n-dimensional objects under CLP(Q)

In this section, we explain some basic operations (union, intersection, complement, and subtraction) to manipulate the 3D objects that describe the BIM project. Figure 2 shows a preliminary interface implemented using CLP(Q) with the following four predicates that can be used to manipulate shapes in any n-dimensional space: ^{Footnote 2}

• : Given two shapes ShA and ShB, it creates a new shape Union that is the union, that is, $Union = ShA \cup ShB$ . Since every shape is, in general, the union of simpler convex shapes (represented as a list thereof), Union can simply be represented as a list containing the convex shapes of ShA and ShB (line 2). Simplification (to, e.g. remove shapes contained inside other shapes) can be done, but we have not shown it here for simplicity.

• : Given two shapes ShA and ShB, it creates a new shape Intersection which is the intersection, that is, $Intersection = ShA \cap ShB$ (lines 5-6). This is computed with the union of the pairwise intersections of the shapes in ShA and ShB. Obtaining the intersection of two convex shapes is done by the CLP(Q) constraint solver, which determines the set of points that are in both shapes as those which satisfy the constraints of both shapes. In line 15, preserves the variables by generating a new set, . ^{Footnote 3}

• : Given a shape ShA, it creates a new shape Complement that contains every point in the n-dimensional space that is not in the shape ShA (lines 20-25). This is computed as the dual of ShA. From a logical point of view, it corresponds to the negation, so it is denoted as $Complement = \lnot\ ShA$ .

• : Given two shapes ShA and ShB, the subtraction is a new shape Subtraction that contains all points of ShA that are not in ShB, that is, $Subtraction = ShA \cap \lnot\ ShB$ (lines 28-39). To compute the subtraction of a convex shape from ShA, we iteratively narrow its n-dimensional space, $C_0$ , by selecting one convex shape from ShB, $Sh_i$ , and computing the intersection of $C_{i-1}$ and the complement of $Sh_i$ , that is, $C_i = C_{i-1} \cap \neg Sh_i$ . The execution finishes when all shapes have been selected or the $i^{th}$ shape covers the remaining space $C_{i-1}$ .

Fig. 2. Operations on an n-dimensional space using CLP(Q) spatial_clpq.pl.

Example 7. These operations can be used with n-dimensional shapes. For simplicity, let us consider 2D rectangles: r1 in yellow and r2 in blue):

Example 8. In addition, they can be combined to verify IFC properties and/or (non-)geometrical information contained in the BIM model. The predicate , in Example 3, can be defined from the geometry of and , that is, belongs to if the intersection returns a non-empty shape.

4.3 Operations on $\mathbf{n}$ -dimensional shapes under s(CASP)

We will now sketch how the main operations on n-dimensional objects can be defined using s(CASP). We will take advantage of its ability to execute ASP programs featuring variables with dense, unbounded domains. As a proof of concept, Figure 3 shows the encoding of the operations for 2-dimensional shapes, with slight differences in the representation of the objects and shapes w.r.t. the representation used under Prolog:

• The predicates for union, intersection, complement, and subtraction receive the identifiers of the object(s), instead of the list of convex shapes.

• A convex shape in n dimensions is an atom with $n+1$ arguments. Its first argument is the object identifier and the rest of the arguments are the variables used to define the convex shape, for example, a 2D shape is an atom of the form .

• The representation of the convex shapes is part of the program, for example, the rectangles r1 and r2 in Example 7 are defined with the clauses:

Fig. 3. Operations on a 2-dimensional space using s(CASP) spatial_scasp.pl.

This representation delegates the shape representation to be handled as part of the constraint store of the program. Therefore, a non-convex object is represented with several clauses, one for each convex shape, and a set of convex shapes is a set of answers obtained via backtracking.

Example 9 (Cont. Example 7) Let us consider the queries used in Example 7 under s(CASP) with the encoding in Figure 3.

5 Tracing (non)-monotonic changes in BIM models

Let us adapt the example presented by Arias et al. (Reference Arias, Carro, Salazar, Marple and Gupta2018) in Section 4.1, where different data sources may provide inconsistent data, and a stream reasoner, based on s(CASP), decides whether the data is valid or not depending on how reliable are the sources.

Here, instead of streams, we consider models. A shared model is updated by different experts, and updated models have to be merged to generate the next model in the chain.

• If a gas boiler is used, the ventilation must be natural. ^{Footnote 4}

• If an electric boiler is used, the ventilation could be either natural or mechanical.

Initially, the shared BIM model has no ventilation or boiler restrictions. Later on, the architect modifies the model by reducing the size of the window in such a way that ventilation cannot be considered natural any longer due to the new size. To comply with the fire safety regulation (and maintain the consistency of the model) the architect selects an electric heating boiler. Simultaneously, the engineer modifies the model by selecting a gas boiler because it is more efficient than an electric boiler. This would force ventilation to be natural.

Finally, when attempting to merge the updated models, an inconsistency is detected and the integration fails. A naive approach would broadcast the inconsistency to the architect and engineer, but we propose using a continuous integration reasoner to determine who is the expert whose opinion prevails and make a decision based on that. The other party needs then to be notified to confirm the adjustments.

Figure 4 sketches a continuous integration reasoner, adapted from the paper by Arias et al. (Reference Arias, Carro, Salazar, Marple and Gupta2018) and the encoding of Example 10 (Bim_CI.pl). Its goal is the detection of inconsistency in pieces of information provided by the different stakeholders. And then, depending on a given criterion (e.g. their responsibility/expertise), it would determine which data is valid (and eventually who should amend that inconsistency). Data labels are represented as , where tells us the degree of confidence in ; hides how priorities are encoded in the data (in this case, the higher the priority, the more level of confidence); and determines, in lines 13–16, which data items are inconsistent (in this case, and ). Lines 1–11, alone, define the reasoner rules: states that a data label is valid if it is not canceled by another data label with more confidence. ^{Footnote 5} In this encoding the confidence relationship uses constraints, that instead of being checked afterward prune the search, but it is possible to define more complex rules, that is, to determine who is more expert/confident depending on the data itself (e.g. for discrepancies in the dimensions of a beam, the structural engineer is the expert).

Fig. 4. Code of the BIM continuous integration with an example.

Lines 17–19 define that initially, holds for all , but when the engineer selects and this data has more confidence, so the query returns: , because is more reliable than , , and . If we consider that the architect selection has more confidence than the engineer’s (by adding lines 20–21), the query , returns: , , , , and . Note that now the answer is not valid. Finally, by adding (line 22), we observe that answer is not valid. As we mentioned before, s(CASP) also provides justification trees for each answer (Bim_CI.txt) to support the inferred conclusions so the user can check and/or validate the correctness of the final results.

6 Evaluation

The reasoner and benchmarks used in this paper are available at https://gitlab.software.imdea.org/joaquin.arias/spatial, and/or at http://platon.etsii.urjc.es/ jarias/papers/spatial-iclp22. They were run on a macOS 11.6.4 laptop with an Intel Core i7 at 2,6 GHz. under Ciao Prolog version 1.19-480-gaa9242f238 (https://ciao-lang.org/) and/or under s(CASP) version 0.21.10.09 (https://gitlab.software.imdea.org/ciao-lang/scasp).

A direct performance comparison of our prototype with implementations in other tools may not be meaningful because they do not support the representation of vague concepts and/or continuous quantities. ASP4BIM by Li et al. (Reference Li, Teizer and Schultz2020) overcomes most of the limitations of previous tools (see Section 7) but, since it is built on top of clingo, it inherits limitations already pointed out by Arias et al. (Reference Arias, Carro, Chen and Gupta2022).

Firstly, let us use the program room.pl (Figure 1). As we mentioned in Section 3, it returns independent answers under s(CASP), that is, for the query we obtain a total of 14 partial models: one for room r1, another for room r2, and two for each of other six rooms. On the other hand, the same program under clingo (room.clingo) generates 64 models: all possible combinations such as and appear in all of them and for each room rX, 32 models contains , while the other 32 models contains . The exponential explosion in the number of models generated by clingo reduces the comprehensibility of the results (for 16 rooms it generates 16,384 models, while s(CASP) generates only 30 models). Moreover, the goal-directed evaluation of s(CASP) not only makes it possible to reason about specific rooms, but it also generates the corresponding justification, for example, room_r1.txt and room_r1.html for room r1.

Secondly, to validate the benefits of our proposal dealing with geometric information, we have implemented a spatial reasoner, in collaboration with VisuaLynk Oy, based on the spatial interface described in Figure 2. This spatial reasoner includes a graphic interface that translates the constraints back into geometry and generates 3D images with the results for the queries using x3d. ^{Footnote 6} The benchmarks used are: (i) the ERDC: Duplex Apartment Model ERDC D-001 produced in Weimar, Germany for a design competition, and (ii) the Trapelo St. Office (IFC4 Edition), a 3-story office building where Revit HQ in Waltham is, which consists of three models (Architecture, MEP, and Structure).

For the evaluation, we translated the IFC files of the models to convert the geometrical data (and IFC labels) of the 286 objects of the Duplex and approximately 5000 objects of the Office Building (3639 objects in the architecture model and 1322 objects in the structure model) into Prolog facts. We defined a predicate , where the first argument is the IFC label, the second is the identifier, the third and fourth are the lower and higher points of the bounding box (resp.), and the fifth depends on the file (in the duplex file it is the centroid point of the box, in the architecture model of the office is “arq,” and in the structure model of the office is “str”). Several queries, for both models, are available at duplex.pl and office.pl. Let us comment a few of them:

Fig. 5. Images in x3d corresponding to the Duplex and Office BIM models.

The current development of the BIM reasoner is a proof of concept in which no optimization techniques have been applied. Nevertheless, the results from a performance point of view are also satisfactory. The query in Example 12 found the first beam with uncovered parts in 0.104 seconds and evaluates the whole office, by selecting 691 beams from a total of 3639 objects in the architecture model and detecting the 511 beams not covered by the more than 1300 objects in the structure model, in 48 seconds ^{Footnote 7}

7 Related work

Many logic-based proposals have been developed to overcome the limitations of the IFC format and automated tools based on IFC, such as Solibri Model Checker (SMC) and the Corenet BIM e-Submission by Singapore Government (2016) to be adapted to different regulations. These limitations have been attacked using different approaches:

• Extended query languages to handle IFC data, such as BimSPARQL, by Zhang et al. (Reference Zhang, Beetz and de Vries2018), that extends SPARQL with (i) a set of functions modeled using the Web Ontology Language (OWL), (ii) a set of transformation rules to map functions to IFC data, and (iii) a module for geometrical related functions. However, they require to pre-process the geometrical information contained in the model and/or have limitations to infer new knowledge, for example, the shortest path between two rooms.

• Minimal proof-of-concept tools, such as the safety checker by Zhang et al. (Reference Zhang, Teizer, Lee, Eastman and Venugopal2013), the acoustic rule checker by Pauwels et al. (Reference Pauwels, Van Deursen, Verstraeten, De Roo, De Meyer, Van De Walle and Van Campenhout2011), and BIMRL by Solihin (Reference Solihin2015), that show improved reasoning capabilities of w.r.t. commercial off-the-shelf BIM Sofware. However, all report limitations in the representation of geometrical information and/or in the flexibility of the proposal to adapt the code and/or the evaluation engine for different scenarios.

• Translation of building regulation into computer-executable formats, such as KBimCode by Lee et al. (Reference Lee, Lee, Park and Kim2016) which transcribes the Korean Building Act to evaluate building permit requirements. However, they report difficulties to translate vague concepts such as accessible routes (key information such as the function of a room is needed to derive the “accessible routes”).

To overcome the limitations of these approaches, we propose using a goal-directed implementation of CASP, because Prolog and bottom-up implementations of CASP have limitations to modeling vague concepts and geometrical information simultaneously:

• Prolog: Since Prolog is based on the least fixed point semantics, the different answers generated by independent clauses correspond to a single model and are simultaneously true.onsider a program containing the facts and . If is invoked in different parts of the program, it may assign two different sizes to the same room, which is against the intended interpretation of . It is not possible to restrict to have only one of the two possible sizes everywhere in the program. Additional care (e.g. explicit parameters) is needed to force this consistency. Moreover, it is not easy to make use of default negation in Prolog, since its negation as failure rule has to be restricted to ground calls (e.g. the query in Example 1 is unsound under SLDNF) and it may not terminate in the presence of non-stratified negation (e.g. the query in Example 2 does not terminate under SLDNF). While there exist implementations of Prolog, such as XSB with tabled negation, that compute logic programs according to the well-founded semantics (WFS), the truth value of atoms under WFS can be undefined, for example, the query in Example 2 under WFS returns undefined.

• CASP: While a goal-directed implementation of ASP provides the relevant partial model, standard ASP systems that require a grounding phase in the presence of multiple even loops, for example, a unique vague concept referred to various objects, may generate a combinatorial explosion in the number of valid stable models, reducing the comprehensibility of the results. Moreover, these systems cannot (easily) handle an unbound and/or dense domain due to the grounding phase. Variable domains induced by constraints can be unbound and, therefore, infinite (e.g. with or ). Even if they are bound, they can contain an infinite number of elements (e.g. in or ). These problems have been attacked using different techniques:

  • — Translation-based methods, such as EZCSP by Balduccini and Lierler (Reference Balduccini and Lierler2017), convert both ASP and constraints into a theory that is executed in an SMT solver-like manner. However, the translation may result in a large propositional representation or weak propagation strength.

  • — Extensions of ASP systems with constraint propagators, such as clingcon by Banbara et al. (Reference Banbara, Kaufmann, Ostrowski and Schaub2017), and clingo[DL,LP], generate and propagate new constraints during the search. However, they are restricted to finite domain solvers and/or incrementally generate ground models, lifting the upper bounds for some parameters.

Since the grounding phase causes a loss of communication from the elimination of variables, the execution methods for CASP systems are complex. Explicit hooks sometimes are needed in the language, for example, the required built-in of EZCSP, so that the ASP solver and the constraint solver can communicate. More details on standard CASP systems can be found in the paper by Lierler (Reference Lierler2021).

Finally, let us analyze a recent proposal for safety analysis, ASP4BIM by Li et al. (Reference Li, Teizer and Schultz2020), which is built on top of clingo, a state-of-the-art ASP solver. ASP4BIM overcomes most of the limitations of previous BIM logic-based approaches by (i) defining spatial aggregates in ASP, (ii) maintaining geometries in ASP through a specialized geometry database extended to support the real arithmetic resolution and specialized spatial optimizations, and (iii) formalizing 3D BIM safety compliance analysis within ASP. However, it inherits the limitations of ASP solvers, which require a grounding phase, when dealing with dense/unbounded domains (needed to represent time, dimensions, etc.) and/or understanding the answers due to the number, size, or readability of the resulting models. While the limitation of dealing with dense domains can be overcome by using discrete domains, for example, using integers to represent time-steps instead of continuous-time, it involves certain drawbacks: as pointed out by Arias et al. (Reference Arias, Carro, Salazar, Marple and Gupta2018) this shortcut may impact performance (by increasing execution run-time of clingo by orders of magnitude) and/or may make a program succeed with wrong answers (due to the rounding in ASP).