Planning a Typical Working Day for Indoor Service Robots.

This paper describes a method of considering the problem of planning for indoor service robot. We introduce a novel graph theoretic formulation of the planning a typical working day problem. We prove that this problem is NP-complete. In proof we consider an explicit reduction of the planning a typical working day problem to the problem of finding a Hamiltonian path. Also we describe an approach to solve this problem. This approach is based on constructing a logical model for the planning a typical working day problem. Using our reduction from the planning a typical working day problem to the Hamiltonian path problem and reduction from the Hamiltonian path problem to the satisfiability problem one can try to solve the planning a typical working day problem by local search and intelligent algorithms which developed for the satisfiability problem. [ABSTRACT FROM AUTHOR]