Hierarchical knowledge-rich semantic maps for personalized path finding

Demirel, Ezgi (2017) Hierarchical knowledge-rich semantic maps for personalized path finding. [Thesis]

[thumbnail of Restricted to Repository staff only until 06.02.2020] PDF (Restricted to Repository staff only until 06.02.2020)
Restricted to Repository staff only

Download (40MB) | Request a copy


In large dynamic environments (e.g., shopping malls) where robots help/guide humans to their destinations, computing personalized routes becomes challenging. From the computational complexity perspective, due to the users’ constraints that ensure visiting some locations before their destination, the path finding problem becomes intractable. Moreover, for computing personalized paths, relevant knowledge (e.g., commonsense knowledge, temporary knowledge, map of the environment) should be represented, extracted and integrated within path finding. From the social perspective, considering human-robot interactions, expressing queries/answers regarding path finding problems require an understandable dialogue interface and methods to summarize very long itineraries. In this thesis, we address both sorts of challenges to solve personalized path finding problems. In particular, we formally define the constrained path finding (CPF) problem and prove its intractability. We introduce a knowledge-based method to compute personalized solutions to CPF problems, using answer set programming (ASP) and relevant knowledge bases. We introduce controlled natural languages, H2R-CNL and R2H-CNL, to represent human-robot dialogues for personalized path finding, and methods to extract relevant knowledge and transform queries/answers to/from formal languages using Semantic Web technologies. To solve CPF problems more efficiently and to present solutions to users more intuitively, we introduce a novel mathematical model, called Hierarchical Knowledge- Rich Semantic Maps (HSMs), that hierarchically represents an environment at different levels of abstraction. We also introduce methods for computing and presenting personalized paths over HSMs. We experimentally evaluate our CPF methods over a real-world shopping mall environment and some randomly generated instances, to show their scalability and the usefulness of HSMs.
Item Type: Thesis
Additional Information: Yükseköğretim Kurulu Tez Merkezi Tez No: 461041.
Uncontrolled Keywords: Semantic maps. -- Knowledge representation and reasoning. -- Path finding. -- Constrained satisfaction. -- Shortest path. -- Answer set programming. -- Controlled natural language. -- Anlambilim Haritalar. -- Bilgi gösterimi ve akıl yürütme. -- Yol bulma. -- Kısıtlama tatmini. -- En kısa yol. -- Çözüm seti programlama. -- Kontrollü doğal dil.
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 10 May 2018 11:28
Last Modified: 26 Apr 2022 10:22
URI: https://research.sabanciuniv.edu/id/eprint/34767

Actions (login required)

View Item
View Item