MSc. Thesis Defense: Ezgi Demirel
  • FENS
  • MSc. Thesis Defense: Ezgi Demirel

You are here

HIERARCHICAL KNOWLEDGE-RICH SEMANTIC MAPS

FOR PERSONALIZED PATH FINDING

 

Ezgi Demirel
Computer Science and Engineering, MSc. Thesis, 2017

 

Thesis Jury

Assoc. Prof. Dr. Esra Erdem (Thesis Advisor),

Assoc. Prof. Dr. Volkan Patoğlu,

 Assist. Prof. Dr. Reyyan Yeniterzi

 

 

Date & Time: 5th,  Jan 2017 –  10:40 AM

Place: FENS G035

Keywords : Path Finding, Commonsense Knowledge, Ontologies, Environment Modeling, Knowledge Integration, Answer Set Programming, Semantic Web, Controlled Natural Languages, Human-Robot Interaction

 

Abstract

 

 

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.