A General Formal Framework for Personalized Path Finding based on Hierarchical Knowledge-Based Environmental Modelling

Posted on July 1st, 2017

We study the problem of computing personalized paths in an environment, taking into account the user’s constraints and preferences, and a variety of knowledge about the environment and the user. From the modeling perspective; we introduce a novel mathematical model, called Hierarchical Knowledge-Rich Semantic Map (HSM), for representing the environment compactly, and propose different sorts of knowledge bases for representing relevant commonsense knowledge and temporary knowledge about the environment and its users. From the computational perspective; first, we consider the problem of personalized path finding at each level of an HSM: We prove that personalized path finding is intractable, introduce a formal method to solve it, prove the correctness of this method, and extend it to make interoperable with heterogenous knowledge. After that, we introduce a recursive algorithm to incrementally solve personalized path finding at an HSM, evaluate its performance empirically, and discuss its usefulness with some robotic scenarios.



Comments are closed.