کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4960653 1446503 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Procedia Computer Science - Volume 112, 2017, Pages 741-750
نویسندگان
, , , ,