Autonomous robots that operate in indoor, uncertain environments move around from one location to the next to fulfill a set of ordered task. To do so, they need a floor plan of the building to plan their route. In case the building is unfamiliar to a robot it can employ online mapping techniques, though these techniques are resource intensive and time consuming. In addition, processing such geometric maps in an automated planner to determine a feasible route is resource demanding as well. The solution proposed in this article is an ontology that combines knowledge of floor plans and actual information of a building with concepts in automated planning, so that robots become more efficient in route planning. Moreover, the ontology is implemented as a hypergraph to benefit from its advances in creating elegant inference-rules, e.g., to infer route-alternatives while preparing the operation.
Autonomous, robotic systems are expected to operate in uncertain environments for
executing various tasks at various locations. In case there is sufficient freedom in task order
they need to plan their route and their next task simultaneously. An example is a search
and rescue operation in a building, where the robot needs to move between rooms to
search and assist victims. Such operations are typically conducted in environments that
are new to the robot. This does not necessarily mean that the robot is completely
ignorant and has to conduct resource-demanding techniques as Simultaneous Localization
and Mapping (SLAM [
This article discusses such an ontology, represented as a hypergraph, that combines
concepts that typically exist in a floor plan with some main concepts used in automated
planning. Given this ontology, the robot can deduce via symbolic reasoning how to go
from one place on the map to another before the operation starts, without the need for
data-driven approaches as SLAM to first create a map that is then used by HRL or
MonteCarlo Tree Search [
The next Section 2 provides some background on important concepts found in floor plans and automated planning, followed by Section 3 introducing GRAQL as an approach to represent an ontology in a knowledge-hypergraph. Section 4 presents the proposed ontology for route-planning in an indoor environment and how to apply inference to automatically determine route-alternatives in its knowledge-hypergraph, followed by some initial conclusion and future work in Section 5.
The ontology developed will not always be as thorough as some of the existing work, as it is intended to explore the benefits of a hypergraph rather than being 100% complete.
Inspired by the work of [
The research domain of automated planning has produced various modelling solutions,
such as the Planning Domain Definition Language (PDDL [
Here, the above-mentioned concepts are applied to a robot that plans its route in a building from its current location, called actual location, to a goal or destination, in this case its final location. The state that is used by the planner is the actual location. It is assumed that the robot has one or more operators, which is a designated set of system components via which the system is able to execute a primitive task independently. An operator that the robot can execute is exit via door, which has a matching primitive task of goto adjacent room that is conditioned on the fact that there exists a door connecting the room the robot is currently in with the adjacent room. Hence, the planner requires particular contextual conditions, or in this case building conditions, which are the room connections in the building. Then, a composite task would be to go from one room in the building to another room via a series of intermediate rooms, i.e., goto room, which is conditioned on the fact that there is a series of connected rooms from the robot’s actual location to its final location. A hierarchical illustration of these planning elements is depicted in Figure 2, where it should be noted that final location and actual location are not a sub of goal and state, but they are (for now undefined) concepts merely used by the planner as either goal or state. In a same way room connection is used as a condition.
The background presented in this chapter introduced some important entities that are used in a floor plan and in automated planning, but, apart from the sub-relations, it did not discussed the relations between them. These relations are introduced with the proposed ontology in Section 4, after some background on GRAQL has been given.
GRAQL is a query language to create, use and maintain an ontological knowledge
representation within the GRAKN hypergraph database [
In a plain knowledge-graph, each entity and attribute is a node in the graph and each relation is an edge between two nodes. In the knowledge-hypergraph a relation itself is a node linked to multiple other nodes, as entities, attributes and relations, via edges each specified by a role. The benefit of a hypergraph is that a relation is another type of a concept where multiple (> 2) other concepts can play a role in. In addition, hypergraphs allow to define a hierarchy in relations and in their roles. For example, one could specify a spatial-connection-relation, having the roles place and connector, that relates two or more spaces (in the role place) via a structural element (in the role connector). In case of a floor plan, one could then specify a sub of this relation as a room-connection-relation having the roles place, door-connector and stairs-connector, where the latter two are a sub of the role connector, for example to connect two rooms (in the role of a place) via a door (in the role of a door-connector) or via a stairs (in the role of a stairs-connector). The resulting benefit is that it makes knowledge more clear and less cumbersome to query than classical knowledge-graphs. This benefit is used in the ontology proposed next, when creating inference-rules on room connections.
The hierarchical relation of the entities for mapping in Figure 1 and for automated planning in Figure 2 are now used to introduce the main part of the proposed ontology depicted in Figure 3. To distinguish between the three different concepts, i.e., entity, relation and attribute, each of them is illustrated with a particular symbol: a rectangle for entity, a diamond for relation and an ellipse for an attribute. Roles are indicated alongside each edge. A brief description of some typical hypergraph-relations is presented next, as entities were already introduced. Please contact the authors for the complete ontology. • task requirement is a relationship with 3 roles to specify that any task requires particular building conditions and a particular value of the planner’s state; • divisioning is a relationship with 2 roles to specify that a compound task can be partitioned into a number of (more detailed) compound and/or primitive tasks; • room connection is a relationship with 3 roles to specify that one door, or a series of doors, connects two rooms in the building, which could be a necessary condition to plan one of the tasks of the robot;
Let us complete this introduction of the ontology with the example depicted in Figure 4, while a more elaborated example can be received upon request. The instances in Figure 4 are related to the hierarchy in Figure 1 as follows: LivingWall, HallWall and KitchenWall which are instances of a wall, LivingDoor and KitchenDoor which are instances of a door, while Living, Hall and Kitchen are instances of a room. Further, the figure depicts one prior relation, i.e., room-connection, and one new relation of the ontology: a constructing relationship indicating how a room that has the role of a construction is made out of the different structural elements having the role of a part.
The room connection relation shown in Figure 4 is obtained via the following rule, which benefits from the ability of GRAQL to use n-ary relations: room-connection sub rule, when f $x isa room; $y isa room; $x != $y; $z isa door; (construction: $x, part: $z) isa constructing; (construction: $y, part: $z) isa constructing; g, then f(place:$x, place:$y, door-connector: $z) isa room-connectiong; If the robot wants to go from one place to the next, it can query the room connection between these places as that will produce the door-connectors. For example, a query on the room connections of the Living will show that the Hall is reached via the LivingDoor. By making the room connection rule transitive, it can connect all places with all connectors.
An ontology for route planning through a building was presented by combining knowledge of a floor plan with knowledge on automated planning. The ontology was further extended with automated inference to prune the possible route-alternative and thereby, prevent that an automated planner explores infeasible routes. As such, our approach makes a separation between resource intensive, data driven methods and inference on symbolic knowledge. Another benefit, as our ontology is implemented as a knowledge-hypergraph, is that inference-rules are much easier and faster to implement compared to more traditional approaches on knowledge databases, mainly due to the fact that a relation is a hierarchical concept of multiple roleplayers. With little effort a human operator can thus enter symbolic knowledge making the use of, e.g., SLAM, unnecessary. Future work is to further integrate this knowledge-hypergraph with a route- planner on an actual robot.