In this paper, we propose a novel approach that combines logic programming with ontological reasoning. The proposed approach enables the use of ontological terms directly within logic programs. We demonstrate the usefulness of the proposed approach using a case-study of sensor-task matchmaking. Description Logic (DL) is a decidable fragment of First Order Logic (FOL) [2]. It constitutes the formal background for OWL-DL, the decidable fragment of the Web Ontology Language (OWL) [7]. However, DL is not sufficient on its own to solve many real-life problems. For example, some rules may not be expressed in DL. In order to represent rules in an ontology, rule languages such as Semantic Web Rule Language (SWRL) [1] have been proposed. In the design of Semantic Web languages, decidability has been one of the main concerns. To achieve decidability, these languages enforce limitations on expressiveness. OWL ensures decidability by defining its DL equivalent subset; similarly we can ensure decidability of SWRL using only DL-safe rules [4]. Existing reasoners such as Pellet [6] provide ontological reasoning services based on these restrictions. However, because of these limitations, many logical axioms and rules cannot be expressed using OWL-DL and SWRL [1]. On the other hand, languages like Prolog [8] provide very expressive declarative Logic Programming (LP) frameworks. Unlike OWL and SWRL, Prolog adopts the closed-world assumption through negation as failure and enables complex data structures and arbitrary programing constructs [8]. In this paper, we propose Ontological Logic Programming (OLP)1 , a novel approach that combines LP with DL-based ontological reasoning. An OLP program can dynamically import various ontologies and use the terms (i.e., classes, properties, and individuals) in these ontologies directly within an OLP program. The interpretation of these terms are delegated to an ontology reasoner during interpretation of the OLP program.
Our choice of LP language is Prolog and in this work, we use a pure Java
implementation, tuProlog [
:- op(550,xfy,’:’). eval((O:G)):- dl reasoner((O:G)). eval(assert((O:G))):- assert into ontology((O:G)). eval(retract((O:G))):- retract from ontology((O:G)). eval(not(G)):- not(eval(G)). eval((G1,G2)):- eval(G1),eval(G2). eval((G1;G2)):- eval(G1);eval(G2). eval(G):- not(complex(G)),(clause(G,B),eval(B);
not(clause(G, )),call(G)). complex(G):- G=not( );G=( , );G=( ; );G=( : );
G=assert( : );G=retract( : ).
Fig. 2. Prolog meta-interpretter for OLP interpreter.
During the interpretation of an OLP program, when a predicate in prefix:name format is encountered, the DL reasoner below the LP layer in the OLP stack is queried to get direct or inferred facts about the predicate in the underlying ontologies. For example, when the meta-interpreter encounters vin:hasFlavor(D,R) during its interpretation of an OLP program, it queries the DL reasoner, because vin:hasFlavor is an ontological predicate. The hasFlavor predicate is defined in the wine ontology, so the reasoner interprets its semantics to infer direct and derived facts about it. Using this inferred knowledge, the variables D and R are unified with the appropriate terms from the ontology. Then, using these unifications, the interpretation of the OLP program is resumed. Therefore, we can directly use the concepts and properties from ontologies while writing logic programs and the direct and derived facts are imported from the ontology through a reasoner when necessary. In this way, OLP enables us to combine the advantages of logic programming (e.g., complex data types/structures, negation by failure and so on) and ontological reasoning. Moreover, logic programming aspect enables us to easily extend the OLP interpreter so as to provide, together with answers, explanations of the reasoning which took place. 3
In order to ground the description of OLP, in this section we introduce a real-world
problem domain and shows how OLP has been used to provide an effective solution to
it. The International Technology Alliance 3 (ITA) is a research program initiated by the
UK Ministry of Defence and the US Army Research Laboratory. ITA focuses on the
research problems related to wireless and sensor networks. One of these research
problems is the selection of appropriate sensing resources for Intelligence, Surveillance,
Target Acquisition and Reconnaissance (ISTAR) tasks 4. In order to solve this
problem, we have previously implemented a system called Sensor Assignment to Missions
(SAM) [
toAccomplish Operation Mission
isA Platform
Capability provides Asset mounts attachedTo isA
System isA Sensor
Task Constant_Survailance isA hasOperationalRequirement
Road Surveillance
IMINT_Capability hasIntel igenceRequirement type road_surveillance_inst hasIntel igenceRequirement
hasIntel igenceRequirement hasOperationalRequirement
PHOTOINT RADINT High Altitude
We show, in Figure 3, a part of the ontology for the ISTAR domain. In the ontology, the Asset concept represents the resources that could be allocated to tasks. The Platform and System concepts are both assets, but systems may be attached to platforms. Sensors are a specialisation of systems. A sensor needs to be mounted on a platform to work properly. On the other hand, not all platforms can mount every type of sensors. For example, to be used, a radar sensor must be mounted on Unmanned Aerial Vehicles (UAVs), however only specific UAVs such Global Hawk can mount this type of sensors.
A task may require capabilities, which are provided by the assets. In order to achieve a task, we need to deploy specific assets that provide the required capabilities. Capability requirements of a task are divided into two categories: the first concerns operational capabilities provided by the platforms, and the second concerns intelligence capabilities provided by the sensors attached to a platform. Figure 3 shows Road Surveillance task, which has one operational requirement, namely Constant Surveillance, and one intelligence requirement, namely Imagery Intelligence (IMINT). As shown in the figure, an instance of this task is then defined with two more intelligence requirements (Radar Intelligence and Photographical Intelligence) and an additional operational requirement (High Altitude). We use the term Deployable Configuration to refer a set of assets required to achieve a task. A deployable configuration of a task is composed of a deployable platform and a set of sensors. A deployable platform provides all operational capabilities required by the task. Similarly, the sensors in the deployable configuration provide all the intelligence capabilities required by the task. Furthermore, the deployable platform should have an ability to mount these sensors. Therefore, there is a dependency between the platform and the sensors in a deployable configuration. 3.2
The first version of SAM [
%import http://www.csd.abdn.ac.uk/∼murat/ita/istar.owl getConfigurations(T,[P|S]):deployablePlatform(T,P), extendSolution(T,P,[],S). deployablePlatform(T,P):istar:‘Platform’(P), not((istar:‘requireOperationalCapability’(T,C),
not(istar:‘provideCapability’(P,C)))). extendSolution(T,P,Prev,Next):requireSensor(T,P,Prev,X), istar:‘mounts’(P,X), A=[X|Prev], extendSolution(T,P,A,Next). extendSolution(T,P,S,S):
not(requireCapability(T,P,S, )). requireSensor(T,P,S,X):requireCapability(T,P,S,C), istar:‘provideCapability’(X,C). requireCapability(T,P,S,C):istar:‘requireCapability’(T,C), not(provideCapability(S,C)), not(provideCapability([P],C)). provideCapability([Y|Tail],C):istar:‘provideCapability’(Y,C),!; provideCapability(Tail,C).
Fig. 4. OLP program to compute deployable configurations.
We have compared the OLP-based matchmaker with the exhaustive search approach in terms of time consumption. For this purpose, we randomly created 908 tasks using the ISTAR ontology. Figure 5 shows our results, where the x-axis is the maximum number of items in deployable configurations and y-axis is the average time consumed by each approach to find all of the deployable configurations of a task. When the maximum size of deployable configurations increases, the OLP-based approach outperforms the exhaustive search approach significantly; time consumption of the exhaustive search increases exponentially while that of the proposed approach looks mostly linear. These results are intuitive because the OLP program of Figure 4 is based on the idea that the search space can be significantly reduced using domain knowledge (i.e, dependencies between sensors and platforms; not every types of sensors can be used with a specific type platform). Using this principle, at each iteration, it rules out many combinations and significantly reduces the time required to compute deployable configurations. 3
4 Maximum DC Size 5 6
In this paper, we have proposed a novel tool that combines Logic Programming with Ontological Reasoning. Unlike similar approaches in the literature, our approach delegates interpretation of ontological predicates to an ontology reasoner during the execution of logic programs. Hence, it takes the full advantage of both ontological reasoning and logic programming without any compromise in expressiveness. Using a case-study, we have demonstrated how the proposed approach can be used to solve sensor-task matchmaking problem in an efficient and practical way.