Human-Assisted Rule Satisfaction in Partially Observable Environments

Many lightweight installations of smart environment systems do not have complex and expensive sensing and actuating capabilities, leaving parts of the environment unobservable to the system. This limits reasoning and decision making complexity of such systems. A decision support system that can collaborate with human users alleviates this problem by asking users to provide missing pieces of information or to perform actuations of which the system itself is incapable. In this paper we present a smart system that uses declarative rules to describe the expected behavior of the environment. In any situation the system aims to satisfy the rules by finding the actions to transform the environment state to conform to existing restrictions. The system asks users to provide missing information that is relevant to the final decision or to perform required actions. A decision tree is constructed, which defines the actions depending on user's answers. The system constructs it in such a way to minimize the expected efforts of users. We present two ways of constructing such a decision tree. One uses backtracking for optimal results, and the other uses a heuristic approach for faster decision tree creation. We show that the relatively small drop in efficiency allows most smart environments to use the fast heuristic algorithm for decision tree construction.