Multi-goal Pathfinding in Cyber-Physical-Social Environments: Multi-layer Search over a Semantic Knowledge Graph

Multi-goal pathfinding (MGPF) is a problem of searching for a path between a start and a destination that allows a set of goals to be satisfied along the path. In this paper, we address MGPF in the context of ubiquitous environments such as airports, commercial centers and smart campuses that accommodate cyber, physical and social entities from smart objects, to sensors and to humans. The availability of data and services in such environments presents new opportunities for addressing MGPF. More precisely, given a MGPF problem in a pervasive environment, our approach exploits data from various resources, for instance, information acquired from cyber-physical entities located in the environment and from external resources such as the Web in order to solve the problem. In this approach, we propose a knowledge model for describing spatial structures of an environment, cyber-physical-social entities it contains, and relationships among them as a graph, called cyber-spatial graph (CSG). Depending on the set of goals to be satisfied, we dynamically build a graph of goal-location pairs (each goal paired with locations at which it can be satisfied), on top of a CSG creating a multi-layer graph. We adapt A* algorithm into a multi-layer A* that is able to search on both layers. We propose heuristics that exploit the structure and knowledge of CSG to improve the search. Our experiments show significant time efficiency and node expansion reduction in various graph structures when employing the heuristics.