Solving decision making problems is the essence of any intelligent autonomous agent. The objective of this problem is finding the most beneficial course of action, in relation to some revenue measure. In the aspect, robots which are set in the real world are often required to account for its uncertainty when making decisions, in order to provide reliable and robust results. There are multiple possible sources for this uncertainty, e.g. a dynamic environment in which unpredictable events might occur; noisy or limited observations, such as a limited camera range and an inaccurate GPS signal; and inaccurate delivery of actions. Relevant problems include: simultaneous localization and mapping (SLAM), path planning, sensor deployment, robotic arm manipulation, and in recent years even more profound problems such as natural language processing (NLP).
Yet, making a decision (in a naive way) requires calculation of the revenue for every candidate action, in a possibly very large group of actions. Also, uncertainty measures, such as entropy, are expensive to calculate. Overall the total computational cost of the problem can turn exceptionally expensive, thus making it challenging for online systems, or when having a limited processing power (e.g. in drones). Recently several approaches have been introduced in order to improve this high computational cost, considering only specific problems. Moreover, while some of these approaches demonstrate good performance, the induced error from using them is not modeled nor bounded, and therefore the results can not be guaranteed.
In this work, we look for computationally efficient algorithms to solve the decision making and planning problems. Until now we have introduced a new method for analysis of states in this context, which is then used to generate sparse and efficient approximations. Thanks to the pre-analysis, we can also bound the approximation error and guarantee the quality of solution. In several demonstrations, using our algorithms showed a significant improvement in run time.