Hierarchical knowledge-rich semantic maps for personalized path finding

Official URL: http://risc01.sabanciuniv.edu/record=b1649239 (Table of Contents)

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.