We tackle the problem of learning state-variable relationships in Partially Observable Markov Decision Processes to improve planning performance on mobile robots. The proposed approach extends Partially Observable Monte Carlo Planning (POMCP) and represents state-variable relationships with Markov Random Fields. A ROS-based implementation of the approach is proposed and evaluated in rocksample, a standard benchmark for probabilistic planning under uncertainty. Experiments have been performed in simulation with Gazebo. Results show that the proposed approach allows to efectively learn statevariable probabilistic constraints on ROS-based robotic platforms and to use them in subsequent episodes to outperform standard POMCP.
Planning under uncertainty is a crucial problem in sequential decision making and it widely
pervades artificial intelligence and robotics. In many real-world applications, agents act in
partially unknown environments and they know only the model of the dynamics of these
environments. However, in several applications there exist properties which can be used to
improve planning performance. For instance, in this work we focus on problems in which
the state is representable by a set of variables whose values are probabilistically related to
each other. An example is the rocksample domain [
Partially Observable Markov Decision Processes (POMDPs) [
The contribution of this work is twofold: a ROS-based architecture to learn state-variable relationships and the evaluation of this architecture in a Gazebo simulation of rocksample. A criterion based on the convergence of MRF potentials is also proposed to decide when the learning phase can be stopped and the MRF can be used by POMCP to obtain performance improvement. If the learning process is ended too early we could have a performance decrease due to a over specialized MRF on the relationships of few episodes. On the other hand, stopping the learning process too late, last episodes could be non informative for further improving the MRF. This case limits the possibility of exploiting the learnt MRF to obtain a significant performance improvement despite its higher accuracy using it only in few episodes. Results show that the learning phase can be performed on a ROS-based robotic platform and that the usage of the learnt MRF yields a statistically significant performance improvement compared to the standard POMCP.
We first present a method for learning the MRF during POMCP execution. It is based on the information present in the belief and, in particular, it uses information from the state having maximum probability. Then, we describe the ROS-based architecture designed to directly learn the MRF on mobile robots.
Learning the MRF is here meant as learning the potentials of pairwise MRF representing statevariable relationships. Our approach learns the MRF in episodes, where is determined by a stopping criterion described in the following. We initialize the MRF with uninformative priors and then update it at the end of each episode. In particular, given two state-variables and having possible values each, we need to learn the potential , (, ℎ) for each pair (, ℎ) with ∈ {1, . . . , } and ℎ ∈ {1, . . . , }, where variable equality occurs only when = ℎ. We assume that the true state-variable configuration, the hidden part of the state, changes only when a new episode starts. To keep track of state-variable values in diferent episodes we use three data structures. First, a vector () in which we store the state-variable values extracted from the belief in episode . Second, a four-dimensional array ℳ(, , , ℎ), used to count equalities and inequalities among pairs of state-variables in each episode . Third, a matrix (, ) in which we store the equality probabilities among state-variables until episode , namely, the percentage of times variables and had the same value in the first learning episodes.
At the end of each episode , we first populate () with the value of state-variable in the state having maximum likelihood in the belief. Then we update matrix ℳ (which is initialized to zero in the first episode) according to the following formula: ℳ+1(, , , ℎ) = {︃ℳ(, , , ℎ) + 1 ℳ(, , , ℎ) if () = ∧ () = ℎ otherwise Afterwards, we compute MRF potentials by normalizing the counts in ℳ as Finally, equality probabilities are computed from MRF potentials, for each (, ) ∈ , as , (, ℎ) = ∑︀
ℳ(, , , ℎ) ,=1,..., ℳ(, , , )
. (, ) =
∑︁ , (, ). =1,..., (1) (2) (3) Namely, we compute the sum of potentials corresponding to equal values of variables and .
The end of the learning process is determined by a stopping criterion based on the convergence of the MRF. The learning phase ends when each state-variable probability (, ) does not change of a value higher than a predefined threshold for at least 3 episodes. In that case, we consider the learnt MRF informative enough to be used.
We use three ROS nodes, namely environment, agent and planner. The environment discretizes the real world, exploiting a task-specific representation, e.g., a grid for the rocksample domain. The agent node holds information about odometry, and it interfaces the ROS-based robotic platform with the environment and with the planner. Finally, the planner runs the learning process and the POMCP algorithm to act optimally. If the agent performs a sensing action, it will interface with the environment or with sensors mounted on the robotic platform. If the action is moving, the agent node will send the desired goal to the ROS Navigation Stack [28], which will output velocity commands to the real mobile robot. After each action performed by the agent in the real environment, the belief is updated using the collected observation, and at the end of each episode the MRF is updated accordingly to the learning procedure. The implemented architecture is compatible with all mobile platforms that support the ROS Navigation Stack.
We perform our tests on the open-source multi-robot simulator Gazebo [29], in which a Turtlebot3 acts in rocksample on a grid with 5 rows and 5 columns with 8 rocks placed in fixed positions (see Figure 1.a). When the turtlebot performs a sensing action, the true value of the rocks is inferred from readings of a sensor. The reward obtained by moving and sensing is 0, while sampling a rock gives a reward of 10 if the rock is valuable, -10 if it is valueless. Finally, the discount factor used is = 0.95.
We have first defined the set of true relationships, with related probabilities, among rock values to be learnt (see Figure 1.b). We call them true MRF. This is the ground truth against which we then evaluate the performance of our approach. Then we start learning the MRF using at each episode a rock value configuration generated accordingly to the distribution defined by the true MRF. To evaluate our methodology we perform 10 runs, each composed of 100 episodes, and every episode is composed of 60 steps. In each episode a Turtlebot3 acts in the Gazebo simulator of rocksample described above. POMCP always performs 100000 simulations and initializes the particle filter with the same number of particles. The topology of the MRF is assumed to be know. Our method only learns the MRF potentials and the related equality probabilities. In Figure 1.d we show how equality probabilities between rock values change during a run of the learning process (in the x-axis the episode is displayed). The incremental diferences in probability values of all edges start to be lower than 0.01 (the threshold used in the stopping criterion) at episode 20. This condition is verified for the next three episodes, thus the stopping criterion ends the learning phase at the end of episode 23. To evaluate the performance of the proposed learning approach, we compute the MRF distance between the true MRF * (, ), assumed to be known, and the matrix (, ) obtained at the end of the learning phase. We call this measure and it is computed as the Euclidean distance normalized by the number of edges in the MRF ‖* − ‖ 2/|| between the two matrices. The average of this diference over all learning stages of diferent runs is called . The average MRF across the 10 runs is displayed in Figure 1.c. Its high accuracy it’s clearly visible and confirmed by the MRF distance of = 0.01. The proposed learning strategy used in tandem with the stopping criterion has a time complexity of ((|| + 2||) · ), where || is the number of states (needed to scan the belief), || is the number of edges (needed to update ℳ and to check if the learning process could be ended) and, finally, is the number of learning episodes.
The introduction of the learnt MRF in POMCP provides a statistically significant improvement with respect to the standard POMCP. We empirically show it by computing, at episode of the evaluation runs, the diference between the discounted return obtained using the learnt MRF and the discounted return obtained with standard POMCP, namely, ∆ = − . Then, we compute the average of these values across all (100) episodes and all (10) runs. We call this average ∆ and show it with the related distribution in Figure 1.e. Notice that the diference is computed episode by episode to reduce the randomness of the measure. The average diference in discounted return we achieved is 1.28 and to verify that it is statistically diferent from zero, we used the Student’s t-test obtaining a p-value lower than 0.05. The usage of the learnt MRF produces a statistically significant performance improvement (5.88%) without any additional overhead in terms of time complexity.
We have presented a methodology for learning state-variable relationships in POMDPs and a ROS-based architecture to perform the learning on robotic platforms. Moreover we introduce a converge based criterion to decide whether to stop the MRF learning process and to start using it without performance loss. The proposed approach has been tested on a Gazebo simulation of rocksample and results show that it allows to obtain a MRFs informative enough to achieve performance improvement. A limitation of the proposed approach is that the policy used during the MRF-learning phase is the standard POMCP policy, which aims to maximize the reward but it does not optimize the exploration-exploitation tradeof considering also the information acquired in the MRF. This could slow down the learning process. Future research directions aim to solve this problem. Furthermore, we are developing a method able to adapt the learnt MRF to the specific episode characteristics during the application phase. Moreover, we are investigating the possibility to test our approach on other domains. partially observable monte carlo planning, in: Proc. 28th International Joint Conference on Artificial Intelligence, IJCAI-19, ijcai.org, 2019, pp. 5540–5546. [13] A. Castellini, E. Marchesini, A. Farinelli, Partially observable monte carlo planning with state variable constraints for mobile robot navigation, Engineering Applications of Artificial Intelligence 104 (2021) 104382. [14] J. Lee, G. Kim, P. Poupart, K. Kim, Monte-carlo tree search for constrained POMDPs, in: Advances in Neural Information Processing Systems 31, NeurIPS-2018, Montréal, Canada, 2018, pp. 7934–7943. [15] C. Amato, F. A. Oliehoek, Scalable planning and learning for multiagent POMDPs, in:
Proceedings of the AAAI15, 2015, pp. 1995–2002. [16] J. D. Williams, S. Young, Partially observable markov decision processes for spoken dialog systems, Computer Speech and Language 21 (2007) 393–422. doi:10.1016/j.csl.2006. 06.008. [17] D. A. McAllester, S. Singh, Approximate planning for factored pomdps using belief state simplification, in: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, UAI’99, Morgan Kaufmann Publishers Inc., 1999, p. 409–416. [18] S. Ross, J. Pineau, B. Chaib-draa, P. Kreitmann, A bayesian approach for learning and planning in partially observable markov decision processes, Journal of Machine Learning Research 12 (2011) 1729–1770. [19] S. Katt, F. A. Oliehoek, C. Amato, Learning in POMDPs with Monte Carlo Tree Search, in: Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, JMLR.org, 2017, p. 1819–1827. [20] S. Katt, F. A. Oliehoek, C. Amato, Bayesian reinforcement learning in factored POMDPs, in: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2019, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2019, p. 7–15. [21] J. Fischer, O. S. Tas, Information particle filter tree: An online algorithm for POMDPs with belief-based rewards on continuous domains, in: Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, PMLR, 2020, pp. 3177–3187. [22] V. Thomas, G. Hutin, O. Bufet, Monte carlo information-oriented planning, in: ECAI 2020 - 24th European Conference on Artificial Intelligence, volume 325 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2020, pp. 2378–2385. doi:10.3233/FAIA200368. [23] D. Ognibene, L. Mirante, L. Marchegiani, Proactive intention recognition for joint humanrobot search and rescue missions through monte-carlo planning in pomdp environments, in: Social Robotics - 11th International Conference, ICSR 2019, Proceedings, Lecture Notes in Computer Science, Springer, 2019, pp. 332–343. doi:10.1007/978-3-030-35888-4_31. [24] T. S. Veiga, Information Gain and Value Function Approximation in Task Planning Using
POMDPs, Ph.D. thesis, Instituto Superior Técnico, Universidade de Lisboa, 2015. [25] M. Araya, O. Bufet, V. Thomas, F. Charpillet, A pomdp extension with belief-dependent rewards, in: Advances in Neural Information Processing Systems, volume 23, Curran Associates, Inc., 2010. [26] A. Atrash, J. Pineau, A bayesian method for learning pomdp observation parameters for robot interaction management systems, in: In The POMDP Practitioners Workshop, 2010. [27] C. Stachniss, G. Grisetti, W. Burgard, Information gain-based exploration using raoblackwellized particle filters, in: Proceedings of Robotics: Science and Systems (RSS), Cambridge, MA, USA, 2005. [28] E. Marder-Eppstein, E. Berger, T. Foote, B. Gerkey, K. Konolige, The ofice marathon: Robust navigation in an indoor ofice environment, in: 2010 IEEE International Conference on Robotics and Automation, 2010, pp. 300–307. [29] N. Koenig, A. Howard, Design and use paradigms for gazebo, an open-source multi-robot simulator, in: RSJ International Conference on Intelligent Robots and Systems (IROS), volume 3, 2004, pp. 2149–2154 vol.3.