In this paper, we present a generic framework for knowledge management and automated reasoning (KMARF) as an enabler for intelligent adaptive systems. KMARF targets multiple reasoning problem classes (such as planning, verication and optimization) that can share the same underlying system state representation. e idea behind KMARF is to automatically select an appropriate problem solver based on a formalized reasoning expertise in the knowledge base, and convert a problem denition to a problem solver-readable format. Automation of the reasoning process reduces operational costs and enables the system to operate in dynamic environment conditions. We demonstrate our approach using a transportation planning use case.
Internet of ings (IoT)-based systems in general use a vast amount
of heterogeneous data streams and information (e.g., behavioral
models) that need to be analyzed, combined and actioned upon. is
creates a complexity that is unsustainable by only human
management and therefore, automation is a requirement. One of the rst
steps towards automation is formalization of knowledge extracted
from the dierent sources such as sensor networks, documents,
tools and from system experts. Since all the states of the system
and the environment cannot be predicted at design time, there is a
need for developing intelligent , self-adaptive systems which learn
to adjust their behavior in response to the environment. To do
this, one needs to leverage the learnings from articial intelligence
and cognitive technologies research that aim at building intelligent
systems that know about their world and are able to automatically
draw conclusions and act upon them, as humans do. A fundamental
assumption in this research is that knowledge is represented in a
tangible form (usually via ontologies), suitable for processing by
dedicated reasoning engines [
In this paper, we present a Knowledge Management and Automated Reasoning Framework (KMARF), which targets multiple reasoning problems. e purpose of KMARF is to (a) reduce system development and deployment time, by reusing as much knowledge as possible, such as domain models, behaviors and reasoning mechanisms, and (b) reduce operational costs by enabling systems during run-time to automatically decide how to adapt to changes in their contexts and environments, with minimal or no human interaction.
e strong point of KMARF is the particular way in which it relies on a knowledge model that combines both declarative and procedural knowledge. is combination allows the system to automatically do extensive analysis and provide answers to dierent reasoning questions, such as “what is the (optimal) strategy for reaching a given state?”, “can the system end-up in an unsafe state?”, “how much prot can the system generate aer a given amount of time?”. On top of this KMARF supports system self-adaption by selecting appropriate problem solvers and their parameters upon encountering any performance degradation. For example, the system may use KMARF in order to switch from preplanned to reactive operations due to insucient time to replan and changed environment conditions. In the rst case the system will use an oine planner as a problem solver, and in the laer case it might use a local decision maker based on the current environment inputs. In order to use problem solvers specialized in solving specic classes of reasoning problems, KMARF can be extended with model transformation rules that translate from our knowledge model to the targeted problem solver model.
KMARF is suitable for large scale IoT based systems, and so far we have applied it on the Intelligent Transport Systems (ITS) domain. As an illustration example, we consider a transportation planning problem i.e., how to transport passengers or goods with a minimal cost. A cost can be e.g., the traveled distance, the time needed for transportation of each of the passengers or goods, or the number of buses or trucks required for transportation. e answer to the task may be a plan i.e., a sequence of steps for the system to perform in order to reach the goal state. In case the task cannot be performed the answer from KMARF could be a reason why the task cannot be performed, as well as a possible solution, which could be to increase the number of vehicles.
In the literature, there exist several reference architectures for
development of self-adaptive systems, such as MAPE-K [
In brief, our contribution is threefold:
An architecture of a generic framework for knowledge management and automated reasoning (Section 2.1) A knowledge model for representing both declarative and procedural system knowledge in a machine-readable form (Section 2.2).
A prototype implementation of the KMARF architecture (Section 3). 2
In this section, we introduce our Knowledge Management and Automated Reasoning Framework by describing its architecture and the knowledge model that it relies on. KMARF is targeting multiple reasoning problem classes (such as planning, verication and optimization) that can share the same underlying state representation. is enables reusability of knowledge and reasoning methods across dierent domains, thus KMARF reduces operational costs and supports systems operation in changing environment conditions. 2.1
A high-level conceptual view of the architecture of the framework is depicted in Figure 1. e main components of KMARF are the Perception Engine, the Knowledge Base, the Reasoner, the Interpreter and the Actuation Engine.
e Knowledge Base is responsible for representing aspects of
the domain under consideration (such as objects or concepts,
instances and states) and their relations, in well dened, machine
processable syntax and unambiguous semantics. e format of
the knowledge stored in the knowledge base complies with the
knowledge model introduced in Section 2.2, and one of the possible
formats is RDF/OWL [
e Reasoner is used for solving reasoning problems. Reasoning
in context of this paper is dened as the process of solving problems
related to planning, verication, optimization, etc. By relating a
goal query to a meta-reasoning expertise1 stored in the knowledge
base the Inference Engine draws a conclusion about an
appropriate method or a problem solver, and relevant prior knowledge for
solving a given problem. e goal query can be initiated by the
user or the Inference Engine itself based on comparison between
expected and actual system states. For example, if the goal query is
1Meta-reasoning is reasoning about reasoning, i.e., it is comprised of computational
processes concerned with the operation and regulation of other computational
processes within the same entity [
State1
is_bus(b25)
is_bus_stop(bs1)
is_passeger(p1)
at(p1, bs1)
capacity(b25, 23)
waiting(p1, min(2))
to reach a certain goal, the inference engine will look up the
knowledge base and deduce that a Planner should be used to generate
a strategy to reach that goal. Additionally, given that most of the
planners accept planning problems in Planning Domain Denition
Language (PDDL) [
Since the physical world is not entirely predictable KMARF needs to take into consideration that there might be changes in the information stored in the knowledge base. e Perception Engine is responsible, when needed, to push new knowledge from the environment (i.e., predicates) in the knowledge base. Additionally, when executing the strategy the Interpreter works tightly with the Reasoner. In case there are any changes in the expected state of the system the Reasoner sends a replanning request to the Planner. 2.2
e Knowledge Model Aer introducing the architecture of KMARF, we can move on presenting its knowledge model that combines both declarative and procedural knowledge.
Syntax. We model declarative knowledge by describing discrete states of a system. One such state may represent the current state, and the others may describe either previous system states or hypothetical states that the system may end up in the future. In this context we do not strictly apply the notion of time, i.e., the system may change its state instantly. However, the order of states is important as it describes how the system evolves and may explain the reasons behind its progress.
A state is represented by an (implicitly conjunctive) set of predicates fP1; P2; :::g expressing the facts known about the state. Each predicate is a compound term that has a form of Pi ¹a1; a2; :::; an º, where Pi is a predicate’s functor specied as a literal, i.e., a sequence of characters, and aj jj 2 »1::n¼ are the arguments. e number of arguments n is called arity of the predicate. If n = 0, then Pi denotes a simple atomic fact. If n > 0, then Pi denotes a factual relation between its n arguments. e arguments of predicates may include: numbers denoting literal quantity; literals denoted by sequence of alphanumeric characters that start from a lower case character fa; b; c; :::g that represent objects or concepts in the domain (e.g., car may represent “a car” ); d lr o w l a e R actuating
state changes model states and transformation transitions rules meta-reasoning
expertise
goal query goal query UI stop
planner problem model checker format problem format ... Model Checker property proof strategy
expected state sensing
predicates
Knowledge Base domain and reasoning expertise human expertise user specified goal compound terms of the form Ti ¹a1; a2; :::; an º that may have one or many arguments, which can be numbers, literals or compound terms (e.g., velocity¹car ; kmh¹50ºº may stand for “the velocity of the car car is 50 km/h”).
An example shown in Figure 2 contains a state State1 dened using a set of six predicates fis bus; is bus stop; is passeger ; at ; capacity; waitingg. e arguments of the rst three predicates declare existence of bus b25, bus stop bs1, and passenger p1 accordingly. e fourth predicate states that passenger p1 is at bus stop bs1. e h predicate indicates that bus b25 has 23 available places. e last predicate declares a fact that passenger p1 has been waiting at the bus stop from last two minutes.
e procedural knowledge is modeled as a collection of specications of potential transitions between states. A transition specication consists of a precondition, a computation, and an action. Precondition and action both have the same syntax as the state, i.e., they are represented as a set of predicates, except the following two dierences. Variables denoted by sequences of alphanumeric characters starting from a capital leer fX ; Y ; Z ; :::g are allowed in arguments of predicates and compound terms in both precondition and action. e action predicates are restricted to the set fadd; delete g. Intuitively, action predicates denote the procedures performed with a state when a transition is performed. Computation is an ordered list of eect free function calls, i.e. they do not modify the state and are only used during the processing of the transition. e arguments of a function call may be numbers, literals, variables, and functions. If a function returns a value, the last argument of a function call is a variable that holds it. e result of a function call may be used as an argument in subsequent function calls of the computation or in the action.
Example in Figure 3 demonstrates specication of a transition T ransition1 that allows a system to evolve from state State2 to state State3 dened in Figure 2. Aer matching the precondition, the computation checks if a passenger has been waiting for less than 20 minutes and if there is enough capacity to onboard a passenger, it decreases the bus capacity by 1. e action removes the passenger Precondition is_bus(B) is_bus_stop(S) is_passeger(P) at(P, S) at(B, S) capacity(B, C) waiting(P, min(Y))
Transition1
Computation less_than(Y, 20) greater_than(C, 0) decrease(C, 1, NC)
Action delete(waiting(P, U(Y)) delete(at(P, S)) add(at(P, B)) delete(capacity(B, C)) add(capacity(B, NC)) waiting predicate, updates passenger location and available bus capacity value.
By dening the rule consequents as add and delete operations on
the knowledge base itself, we allow for a self-referential rule-based
system [
Semantics. We formalize semantics of literals, compound terms and predicates by associating meanings to their symbols. For example, we use the predicate at ¹p1; bs1º to model the fact that a passenger p1 is at the bus stop bs1. We say that the meaning of at is to represent a close spacial relationship between its two arguments.
We dene semantics of our knowledge model in terms of a transition system. Formally, a transition system is a tuple ¹S; T ; !º, where S is a set of states, T is a set of transition specication names, and ! is set of state transitions (i.e., a subset of S T S). e fact that T r ansit ion1 ¹State1; T ransition1; State2º 2 ! is wrien as State1 ! State2, and represents a transition between a source state State1 and a destination state State2 by applying transition specication T ransition1.
In order for a transition specication to be applied its precondition must match the source state and its computation must succeed. e semantics of matching the precondition with a state are formalized by dening a logical unication between predicates of the precondition and the predicates of the state, as follows. We unify every predicate in the precondition with all the predicates from the state, and use variables substitutions in subsequent unication of the remaining precondition predicates. If the unication of all precondition predicates with the state predicates succeeds, the computed variable substitution is used in the computation and the action, as explained below. Obviously, there can be multiple matches of a precondition with a source state. In this case, every match will produce a transition in ! given that the corresponding computation succeeds.
e meaning of the computation is evaluation of its functions in the order of specication. We use denotational semantics to dene the meaning of a function F as a set of ordered tuples
f< a11; :::; an1 1; an1 >; :::; < am1 ; :::; amn 1; amn >g; where ai1; :::; ain 1 are function arguments, and ain is the value returned by F given those arguments. A function call F ¹a1; :::; an 1; an º is the process of nding such an for given a1; :::; an 1 that there is a tuple < a1j; :::; anj 1; anj > in the denition of F for some j. If there is no such tuple found, the function call fails. Otherwise, the function call succeeds and the value of anj is assigned to a corresponding variable. If the returned value an is of boolean type, i.e. it belongs to the set ftrue; f alse g, then the function succeeds if an = true and fails if an = f alse. A computation succeeds if all the function calls in it succeed. Otherwise, the computation fails.
e semantics of the transition action execution are dened by two operations. e rst operation instantiates predicates in the action by applying computed variable substitution to them. is means that all the variables in the action predicates are replaced with the corresponding values from the variable substitution. e second operation copies all the predicates from the source state to the destination state, and for every predicate in the action we perform the following procedures on the destination state: if the instantiated predicate symbol is add, then its argument is treated as a predicate, and it is added to the destination state; if the instantiated predicate symbol is delete, then its argument is treated as a predicate, and it is removed from the destination state. 3
IMPLEMENTATION is section describes current progress towards a prototype implementation of the KMARF architecture illustrated in Figure 1. e implementation targets a large problem area in ITS known as “transportation planning”, which we dene as the schedules generated for a set of vehicles to pickup and alight people or cargo along one or more routes, within a given amount of time (see also Section 1). e transport planning problem includes a set of connected vehicles, for example buses or trucks, and a central coordinating function that computes the schedule and transmits it to these vehicles2. In this implementation we assume that the Inference Engine component has already deduced that a Planner should be used to solve the transportation planning problem, using meta-reasoning expertise 2Correct interpretation of the schedule rests on the vehicles, which can be partially or completely autonomous or they may also have human drivers. and user query data supplied from the Knowledge Base and the user interface components respectively.
Figure 4 shows the components of the implemented system. One
of the components implemented is the Knowledge Base, which
contains model transformation rules for PDDL language as well as states
and transition models that are based on a set of ontologies that the
authors have dened in [
e authors have released the current implementation of the
Knowledge Base and PDDL Generator as open-source, available for
the community to use [
In this paper, we introduce a generic framework for knowledge management and automated reasoning (KMARF) as an enabler for intelligent adaptive systems. Given a stimulus as a problem statement, KMARF automatically performs reasoning, selects appropriate problem solvers, and allows the system to adapt to changes in its context and environment. To do this, KMARF relies on a metareasoner that by using meta-reasoning expertise draws a conclusion about an appropriate problem solver or a method to perform reasoning. Once a particular problem solver has been selected, KMARF uses a combination of a declarative and procedural knowledge model and a transformation rules model to generate an input for the problem solver. Subsequently, the result of problem solving is used to progress towards completing the original problem.
In the implementation of KMARF we have so far progressed into the development of an ontology for the knowledge base using OWL Web Ontology Language, and we have used the framework to automatically generate PDDL les, feed them into a planner, and create plans. Since, KMARF has a much bigger vision than solving planning problems, in the future we plan on studying how our 3In its current form, the API does not support adding of new model transformation rules, which means that only PDDL language is supported. In the future however, we plan to expand the functionality by adding support for “pluggable” problem solving expertise les. knowledge model can be correlated to other formalisms e.g., Timed Automata.
As future work, we also plan to study how meta-reasoning can help KMARF to determine which prior knowledge and algorithms are relevant when a new, problem or unforeseen instance arrives. Such instance corresponds to the current state of the world, along with all current available sensory information. Initially, the system only knows how to solve problems it has seen before and had previously found reductions that could be solved separately using known procedures. If it can not nd such a reduction for a new instance, it must recur to space state exploration for generating a sequence of state transitions that either lead to the specied goal state or to a beer state in which either the system knows how to proceed with further reductions or declares the problem as intractable under its current knowledge.