ROLZO is a unique mobility service which gives its members access to an exceptional fleet of luxury and high performance cars on demand

ROLZO

This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel;
(2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction
Background
Related Work
POMCP for Stochastic Contingent Planning
Domain Independent Heuristics for POMCP
Empirical Evaluation
Conclusion and References 5 Domain Independent Heuristics for POMCP We now describe the main contribution of this paper — two domain independent rollout heuristics that leverage methods developed in the automated planning community, using the structure specified in the stochastic contingent planning problem. 5.1 Delete Relaxation Heuristics Delete relaxation heuristics are built upon the notion that if actions have only positive effects, then the number of actions that can be executed before the state becomes fixed is finite, and in many cases, small. Also, as actions cannot destroy the precondition of other actions, one can execute actions in parallel. Algorithm 2 portrays a delete relaxation heuristic. Delete relaxation heuristics create a layered graph, interleaving action and fact layers. The first layer, which is a fact layer, contains all the facts that hold in the state for which the heuristic is computed (line 2). The second layer, which is an action layer, contains all the actions whose preconditions hold given the facts in the first layer (line 5). The next layer, which is again a fact layer, contains all the positive effects of the actions in the previous layer, as well as all facts from the previous layer (line 6), and so forth. We stop developing the graph once no new facts can be obtained (line 8). 5.2 Heuristics in Belief Space A major disadvantage of the above heuristics is that they focus on a single state. When the agent is aware of the true state of the system, observations have no value. Hence, the above heuristics, as well as any heuristic that is based on a single state, do not provide an estimate for the value of information, which is a key advantage of POMDPs. We hence suggest now a heuristic that is computed over a set B of possible states (Algorithm 3). We compute again the delete relaxation graph, with a few modifications. We compute for each state in B a separate fact layer. An action can be applied only if its preconditions are satisfied in the fact layers of all agents (line 7). This is equivalent to the requirement in contingent planning where an action is applicable only if it is applicable in all states in the current belief, where B is served as an approximation of the true belief state. Second, our method leverages the deterministic observations, that allow us to filter out states that are inconsistent with the received observation (lines 8-14). When a sensing action can be applied, all states that do not agree with the value of s on the observation are discarded from B (lines 10-14). That is, we remove the fact layers corresponding to these states, and no longer consider them when computing which actions can be applied. We stop when both no states were discarded, and no new facts were obtained (line 17). This process must take into account sensing actions to remove states that are incompatible with s, which would allow, at the next iteration, that action preconditions would be satisfied for less states, and hence additional actions can be executed. This paper is available on arxiv under CC 4.0 license. Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. This paper is available on arxiv under CC 4.0 license. Authors: Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction Background Related Work POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Empirical Evaluation Conclusion and References Introduction Introduction Background Background Related Work Related Work POMCP for Stochastic Contingent Planning POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Domain Independent Heuristics for POMCP Empirical Evaluation Empirical Evaluation Conclusion and References Conclusion and References 5 Domain Independent Heuristics for POMCP We now describe the main contribution of this paper — two domain independent rollout heuristics that leverage methods developed in the automated planning community, using the structure specified in the stochastic contingent planning problem. 5.1 Delete Relaxation Heuristics Delete relaxation heuristics are built upon the notion that if actions have only positive effects, then the number of actions that can be executed before the state becomes fixed is finite, and in many cases, small. Also, as actions cannot destroy the precondition of other actions, one can execute actions in parallel. Algorithm 2 portrays a delete relaxation heuristic. Delete relaxation heuristics create a layered graph, interleaving action and fact layers. The first layer, which is a fact layer, contains all the facts that hold in the state for which the heuristic is computed (line 2). The second layer, which is an action layer, contains all the actions whose preconditions hold given the facts in the first layer (line 5). The next layer, which is again a fact layer, contains all the positive effects of the actions in the previous layer, as well as all facts from the previous layer (line 6), and so forth. We stop developing the graph once no new facts can be obtained (line 8). 5.2 Heuristics in Belief Space A major disadvantage of the above heuristics is that they focus on a single state. When the agent is aware of the true state of the system, observations have no value. Hence, the above heuristics, as well as any heuristic that is based on a single state, do not provide an estimate for the value of information, which is a key advantage of POMDPs. We hence suggest now a heuristic that is computed over a set B of possible states (Algorithm 3). B We compute again the delete relaxation graph, with a few modifications. We compute for each state in B a separate fact layer. An action can be applied only if its preconditions are satisfied in the fact layers of all agents (line 7). This is equivalent to the requirement in contingent planning where an action is applicable only if it is applicable in all states in the current belief, where B is served as an approximation of the true belief state. B B Second, our method leverages the deterministic observations, that allow us to filter out states that are inconsistent with the received observation (lines 8-14). When a sensing action can be applied, all states that do not agree with the value of s on the observation are discarded from B (lines 10-14). That is, we remove the fact layers corresponding to these states, and no longer consider them when computing which actions can be applied. B We stop when both no states were discarded, and no new facts were obtained (line 17). This process must take into account sensing actions to remove states that are incompatible with s , which would allow, at the next iteration, that action preconditions would be satisfied for less states, and hence additional actions can be executed. s

Rollout Heuristics: Domain Independent Heuristics for POMCP

This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel;
(2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction
Background
Related Work
POMCP for Stochastic Contingent Planning
Domain Independent Heuristics for POMCP
Empirical Evaluation
Conclusion and References 7 Conclusion In this paper we suggested to model goal POMDPs as stochastic contingent planning models, which allows us to use domain independent heuristics developed in the automated planning community to estimate the utility of belief states. We implemented our domain independent heuristics into the rollout mechanism of POMCP — a well known online POMDP planner that constructs a search tree to evaluate which action to take next. We provide an empirical evaluation showing how heuristics provide much leverage, especially in complex domains that require a long planning horizon, compared to the standard uniform rollout policy that is often used in POMCP. For future research we intend to integrate our methods into other solvers, such as RTDP-BEL, or into point-based planners as a method to gather good belief points. We can also experiment with additional heuristics, other than the hadd heuristic used in this paper. References [1] Alexandre Albore, Héctor Palacios & Hector Geffner (2009): A Translation-Based Approach to Contingent Planning. In: IJCAI, 9, pp. 1623–1628, doi:10.5555/1661445.1661706. Available at https://dl.acm. org/doi/10.5555/1661445.1661706. [2] Blai Bonet & Héctor Geffner (2001): Planning as heuristic search. Artificial Intelligence 129(1-2), pp. 5–33, doi:10.1016/S0004-3702(01)00108-4. [3] Blai Bonet & Hector Geffner (2009): Solving POMDPs: RTDP-Bel vs. Point-based Algorithms. In Craig Boutilier, editor: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pp. 1641–1646, doi:10.5555/1661445.1661709. Available at https://dl.acm.org/doi/10.5555/1661445.1661709. [4] Blai Bonet & Hector Geffner (2011): Planning under Partial Observability by Classical Replanning: Theory and Experiments. In: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pp. 1936–1941, doi:10.5591/978-1-57735-516-8/IJCAI11-324. [5] Ronen I Brafman & Guy Shani (2016): Online belief tracking using regression for contingent planning. Artificial Intelligence 241, pp. 131–152, doi:10.1016/j.artint.2016.08.005. [6] Hector Geffner & Blai Bonet (2022): A concise introduction to models and methods for automated planning. Springer Nature. [7] Malte Helmert & Carmel Domshlak (2009): Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway? In Lubos Brim, Stefan Edelkamp, Eric A. Hansen & Peter Sanders, editors: Graph Search Engineering, 29.11. - 04.12.2009, Dagstuhl Seminar Proceedings 09491, Schloss Dagstuhl -LeibnizZentrum für Informatik, Germany, doi:10.1609/icaps.v19i1.13370. Available at http://drops.dagstuhl. de/opus/volltexte/2010/2432/. [8] Malte Helmert, Patrik Haslum, Jörg Hoffmann & Raz Nissim (2014): Merge-and-shrink abstraction: A method for generating lower bounds in factored state spaces. Journal of the ACM (JACM) 61(3), pp. 1–63, doi:10.1145/2559951. [25] Guy Shani, Joelle Pineau & Robert Kaplow (2013): A survey of point-based POMDP solvers. Autonomous Agents and Multi-Agent Systems 27, pp. 1–51, doi:10.1007/s10458-012-9200-2. [26] William Shen, Felipe Trevizan, Sam Toyer, Sylvie Thiébaux & Lexing Xie (2019): Guiding search with generalized policies for probabilistic planning. In: Proceedings of the International Symposium on Combinatorial Search, 10, pp. 97–105, doi:10.1609/socs.v10i1.18507. [27] David Silver & Joel Veness (2010): Monte-Carlo planning in large POMDPs. Advances in neural information processing systems 23, doi:10.5555/2997046.2997137. [28] Richard D Smallwood & Edward J Sondik (1973): The optimal control of partially observable Markov processes over a finite horizon. Operations research 21(5), pp. 1071–1088, doi:10.1287/opre.21.5.1071. [29] Adhiraj Somani, Nan Ye, David Hsu & Wee Sun Lee (2013): DESPOT: Online POMDP planning with regularization. Advances in neural information processing systems 26, doi:10.1613/jair.5328. [30] Zachary Sunberg & Mykel Kochenderfer (2018): Online algorithms for POMDPs with continuous state, action, and observation spaces. In: Proceedings of the International Conference on Automated Planning and Scheduling, 28, pp. 259–263, doi:10.48550/arXiv.1709.06196. [31] Yuchen Xiao, Sammie Katt, Andreas ten Pas, Shengjian Chen & Christopher Amato (2019): Online planning for target object search in clutter under partial observability. In: 2019 International Conference on Robotics and Automation (ICRA), IEEE, pp. 8241–8247, doi:10.1109/ICRA.2019.8793494. [32] Nan Ye, Adhiraj Somani, David Hsu & Wee Sun Lee (2017): DESPOT: Online POMDP planning with regularization. Journal of Artificial Intelligence Research 58, pp. 231–266, doi:10.1613/jair.5328. This paper is available on arxiv under CC 4.0 license. Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. This paper is available on arxiv under CC 4.0 license. Authors: Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction Background Related Work POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Empirical Evaluation Conclusion and References Introduction Introduction Background Background Related Work Related Work POMCP for Stochastic Contingent Planning POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Domain Independent Heuristics for POMCP Empirical Evaluation Empirical Evaluation Conclusion and References Conclusion and References 7 Conclusion In this paper we suggested to model goal POMDPs as stochastic contingent planning models, which allows us to use domain independent heuristics developed in the automated planning community to estimate the utility of belief states. We implemented our domain independent heuristics into the rollout mechanism of POMCP — a well known online POMDP planner that constructs a search tree to evaluate which action to take next. We provide an empirical evaluation showing how heuristics provide much leverage, especially in complex domains that require a long planning horizon, compared to the standard uniform rollout policy that is often used in POMCP. For future research we intend to integrate our methods into other solvers, such as RTDP-BEL, or into point-based planners as a method to gather good belief points. We can also experiment with additional heuristics, other than the h add heuristic used in this paper. add References [1] Alexandre Albore, Héctor Palacios & Hector Geffner (2009): A Translation-Based Approach to Contingent Planning. In: IJCAI, 9, pp. 1623–1628, doi:10.5555/1661445.1661706. Available at https://dl.acm. org/doi/10.5555/1661445.1661706. [2] Blai Bonet & Héctor Geffner (2001): Planning as heuristic search. Artificial Intelligence 129(1-2), pp. 5–33, doi:10.1016/S0004-3702(01)00108-4. [3] Blai Bonet & Hector Geffner (2009): Solving POMDPs: RTDP-Bel vs. Point-based Algorithms. In Craig Boutilier, editor: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pp. 1641–1646, doi:10.5555/1661445.1661709. Available at https://dl.acm.org/doi/10.5555/1661445.1661709. [4] Blai Bonet & Hector Geffner (2011): Planning under Partial Observability by Classical Replanning: Theory and Experiments. In: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pp. 1936–1941, doi:10.5591/978-1-57735-516-8/IJCAI11-324. [5] Ronen I Brafman & Guy Shani (2016): Online belief tracking using regression for contingent planning. Artificial Intelligence 241, pp. 131–152, doi:10.1016/j.artint.2016.08.005. [6] Hector Geffner & Blai Bonet (2022): A concise introduction to models and methods for automated planning. Springer Nature. [7] Malte Helmert & Carmel Domshlak (2009): Landmarks, Critical Paths and Abstractions: What’s the Difference Anyway? In Lubos Brim, Stefan Edelkamp, Eric A. Hansen & Peter Sanders, editors: Graph Search Engineering, 29.11. - 04.12.2009, Dagstuhl Seminar Proceedings 09491, Schloss Dagstuhl -LeibnizZentrum für Informatik, Germany, doi:10.1609/icaps.v19i1.13370. Available at http://drops.dagstuhl. de/opus/volltexte/2010/2432/. [8] Malte Helmert, Patrik Haslum, Jörg Hoffmann & Raz Nissim (2014): Merge-and-shrink abstraction: A method for generating lower bounds in factored state spaces. Journal of the ACM (JACM) 61(3), pp. 1–63, doi:10.1145/2559951. [25] Guy Shani, Joelle Pineau & Robert Kaplow (2013): A survey of point-based POMDP solvers. Autonomous Agents and Multi-Agent Systems 27, pp. 1–51, doi:10.1007/s10458-012-9200-2. [26] William Shen, Felipe Trevizan, Sam Toyer, Sylvie Thiébaux & Lexing Xie (2019): Guiding search with generalized policies for probabilistic planning. In: Proceedings of the International Symposium on Combinatorial Search, 10, pp. 97–105, doi:10.1609/socs.v10i1.18507. [27] David Silver & Joel Veness (2010): Monte-Carlo planning in large POMDPs. Advances in neural information processing systems 23, doi:10.5555/2997046.2997137. [28] Richard D Smallwood & Edward J Sondik (1973): The optimal control of partially observable Markov processes over a finite horizon. Operations research 21(5), pp. 1071–1088, doi:10.1287/opre.21.5.1071. [29] Adhiraj Somani, Nan Ye, David Hsu & Wee Sun Lee (2013): DESPOT: Online POMDP planning with regularization. Advances in neural information processing systems 26, doi:10.1613/jair.5328. [30] Zachary Sunberg & Mykel Kochenderfer (2018): Online algorithms for POMDPs with continuous state, action, and observation spaces. In: Proceedings of the International Conference on Automated Planning and Scheduling, 28, pp. 259–263, doi:10.48550/arXiv.1709.06196. [31] Yuchen Xiao, Sammie Katt, Andreas ten Pas, Shengjian Chen & Christopher Amato (2019): Online planning for target object search in clutter under partial observability. In: 2019 International Conference on Robotics and Automation (ICRA), IEEE, pp. 8241–8247, doi:10.1109/ICRA.2019.8793494. [32] Nan Ye, Adhiraj Somani, David Hsu & Wee Sun Lee (2017): DESPOT: Online POMDP planning with regularization. Journal of Artificial Intelligence Research 58, pp. 231–266, doi:10.1613/jair.5328.

Rollout Heuristics for Online Stochastic Contingent Planning: Conclusion and References

This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel;
(2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction
Background
Related Work
POMCP for Stochastic Contingent Planning
Domain Independent Heuristics for POMCP
Empirical Evaluation
Conclusion and References 2 Background We now provide the required background on POMDPs, contingent planning, domain-independent heuristics, and the POMCP algorithm. 2.1 POMDPs Because the state of a POMDP is partially observable, the agent typically does not know what the true underlying state of the world is. Hence, it can maintain a belief state b, which is a distribution over S, i.e., b(s) is the likelihood that s is the current state. When a goal belief is reached, that is sums∈Gb(s) = 1, then the agent is sure that it is at a goal state, and the execution terminates. A solution to a POMDP, called a policy, is a function that assigns an action to every belief state. The optimal policy minimizes the expected cost, i.e., the expected number of steps before a goal belief has been reached. 2.2 POMCP The Partially Observable Monte-Carlo Planning (POMCP) online re-planning approach uses a Monte Carlo tree search (MCTS) approach to select the next action to execute [27]. At each re-planning episode POMCP constructs a tree, where the root node is the current belief state. Then, POMCP runs forward simulations, where a state is sampled from the current belief, and actions are chosen using an exploration strategy that initially selects actions that were not executed a sufficient amount of times, but gradually moves to select the seemingly best action. Observations in the simulations are selected based on the current state-action observation distribution. When reaching a leaf node, POMCP begins a so-called rollout. This rollout is designed to provide a value estimate for the leaf, based on some predefined rollout policy. The value of the leaf is updated using the outcome of the rollout, and then the values of the nodes along the branch that were visited during the simulation are updated given their descendants. Obviously, the values of all nodes in the tree are hence highly dependent on the values obtained by the rollout policy. POMCP is an anytime algorithm, that is, it continues to run simulations until a timeout, and then returns the action that seems best at the root of the search tree. POMCP was designed for large problems. Hence, POMCP does not maintain and update a belief state explicitly. Instead, POMCP uses a particle filter approach, where a set of states is sampled at the initial belief, and this set is progressed through the tree. 2.3 Contingent Planning under Partial Observability Preconditions allow us to restrict our attention only to applicable actions. An action is applicable in a belief b is all possible states in b satisfy the preconditions of the action. Obviously, one can avoid specifying preconditions for actions, allowing for actions that can always be executed, as is typically the case in flat POMDP representations. However, in domains with many actions, preconditions are a useful tool for drastically limiting the amount of actions that should be considered. 2.4 Regression-based Belief Maintenance Updating a belief can be costly. Alternatively, one can avoid the computation of new formulas representing the updated belief, by maintaining only the initial belief formula, and the history —the sequence of executed actions and sensed observations [5]. When the agent needs to query whether the preconditions of an action or the goal hold at the current node, the formula is regressed [20] through the action observation sequence back towards the initial belief. Then, one can apply SAT queries to check whether the query formula holds. We now briefly review the regression process for deterministic actions. This approach can be highly useful for larger POMDPs, complementing the particle filter approach used in POMCP. Regression maintains the equivalence of the formula [20, 5]. For any two formulas φ1 and φ2 we have: Hence, we can produce a regression over formulas, and compare the regressed formulas, making conclusions about the original formulas. The regression can be recursively applied to a sequence of actions and observations (history) h as follows: where ε is the empty sequence. This allows us to perform a regression of a formula through an entire plan, and analyze the required conditions for a plan to apply. In addition, the regression mechanism of [5] maintains a cached list of fluents F(n) that are known to hold at node n, given the action effects or observations. Following an actuation action a, F(a(n)) contains all fluents in F(n) that were not modified by a, as well as effects of a that are not conditioned on hidden fluents. For a sensing action revealing the value l, F(a(n,l)) = F(n) ∪ {l}. During future regression queries, when a value at a particular node becomes known, e.g. when regressing a later observation, it is added to F(n). All fluents p such that p ∈/ F(n)∧ ¬p ∈/ F(n) are said to be hidden at n. The cached list is useful for simplifying future regressed formulas. This paper is available on arxiv under CC 4.0 license. Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. This paper is available on arxiv under CC 4.0 license. Authors: Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction Background Related Work POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Empirical Evaluation Conclusion and References Introduction Introduction Background Background Related Work Related Work POMCP for Stochastic Contingent Planning POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Domain Independent Heuristics for POMCP Empirical Evaluation Empirical Evaluation Conclusion and References Conclusion and References 2 Background We now provide the required background on POMDPs, contingent planning, domain-independent heuristics, and the POMCP algorithm. 2.1 POMDPs Because the state of a POMDP is partially observable, the agent typically does not know what the true underlying state of the world is. Hence, it can maintain a belief state b, which is a distribution over S, i.e., b(s) is the likelihood that s is the current state. When a goal belief is reached, that is sums∈Gb(s) = 1, then the agent is sure that it is at a goal state, and the execution terminates. A solution to a POMDP, called a policy, is a function that assigns an action to every belief state. The optimal policy minimizes the expected cost, i.e., the expected number of steps before a goal belief has been reached. 2.2 POMCP The Partially Observable Monte-Carlo Planning (POMCP) online re-planning approach uses a Monte Carlo tree search (MCTS) approach to select the next action to execute [27]. At each re-planning episode POMCP constructs a tree, where the root node is the current belief state. Then, POMCP runs forward simulations, where a state is sampled from the current belief, and actions are chosen using an exploration strategy that initially selects actions that were not executed a sufficient amount of times, but gradually moves to select the seemingly best action. Observations in the simulations are selected based on the current state-action observation distribution. When reaching a leaf node, POMCP begins a so-called rollout. This rollout is designed to provide a value estimate for the leaf, based on some predefined rollout policy. The value of the leaf is updated using the outcome of the rollout, and then the values of the nodes along the branch that were visited during the simulation are updated given their descendants. Obviously, the values of all nodes in the tree are hence highly dependent on the values obtained by the rollout policy. POMCP is an anytime algorithm, that is, it continues to run simulations until a timeout, and then returns the action that seems best at the root of the search tree. POMCP was designed for large problems. Hence, POMCP does not maintain and update a belief state explicitly. Instead, POMCP uses a particle filter approach, where a set of states is sampled at the initial belief, and this set is progressed through the tree. 2.3 Contingent Planning under Partial Observability Preconditions allow us to restrict our attention only to applicable actions. An action is applicable in a belief b is all possible states in b satisfy the preconditions of the action. Obviously, one can avoid specifying preconditions for actions, allowing for actions that can always be executed, as is typically the case in flat POMDP representations. However, in domains with many actions, preconditions are a useful tool for drastically limiting the amount of actions that should be considered. 2.4 Regression-based Belief Maintenance Updating a belief can be costly. Alternatively, one can avoid the computation of new formulas representing the updated belief, by maintaining only the initial belief formula, and the history —the sequence of executed actions and sensed observations [5]. When the agent needs to query whether the preconditions of an action or the goal hold at the current node, the formula is regressed [20] through the action observation sequence back towards the initial belief. Then, one can apply SAT queries to check whether the query formula holds. We now briefly review the regression process for deterministic actions. This approach can be highly useful for larger POMDPs, complementing the particle filter approach used in POMCP. Regression maintains the equivalence of the formula [20, 5]. For any two formulas φ1 and φ2 we have: Hence, we can produce a regression over formulas, and compare the regressed formulas, making conclusions about the original formulas. The regression can be recursively applied to a sequence of actions and observations (history) h as follows: where ε is the empty sequence. This allows us to perform a regression of a formula through an entire plan, and analyze the required conditions for a plan to apply. In addition, the regression mechanism of [5] maintains a cached list of fluents F(n) that are known to hold at node n, given the action effects or observations. Following an actuation action a, F(a(n)) contains all fluents in F(n) that were not modified by a, as well as effects of a that are not conditioned on hidden fluents. For a sensing action revealing the value l, F(a(n,l)) = F(n) ∪ {l}. During future regression queries, when a value at a particular node becomes known, e.g. when regressing a later observation, it is added to F(n). All fluents p such that p ∈/ F(n)∧ ¬p ∈/ F(n) are said to be hidden at n. The cached list is useful for simplifying future regressed formulas.

Rollout Heuristics for Online Stochastic Contingent Planning: Background

This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel;
(2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction
Background
Related Work
POMCP for Stochastic Contingent Planning
Domain Independent Heuristics for POMCP
Empirical Evaluation
Conclusion and References 6 Empirical Evaluation We conduct an empirical study to evaluate our methods. Our methods are implemented in C#. 6.1 Benchmark Domains We extended the following contingent planning benchmarks to stochastic settings: Doors: In the door domain the agent must move in a grid to reach a target position. Odd levels in the grid are all open, while in even levels there are doors, and only one door is open. The agent can sense whether a door is open when it is at adjacent cells. The agent must identify the open doors and get to the target position. In the stochastic version the agent can open a closed door with some probability of success. The agent can hence either search for the already open door, or attempt to open a closed door. Blocks World: In the contingent blocks world problem, the agent does not know the structure of the initial block configuration, but it can sense whether one block is on top of another one, and whether a block is clear. In the stochastic version moving a block from one block to another has a 0.3 probability of success, while moving blocks to and from the table succeeds deterministicly. Hence, it is often preferable to use the table as an intermediate position. Unix: In this domain the agent must search for a file in a file system, and copy it to a destination folder. In the stochastic version there is a non-uniform distribution over the possible locations of the file. MedPks: The agent here needs to identify which illness a patient has and treat it. To do so, the agent tests for each illness independently, until the proper illness is found. The stochastic version here has non-uniform distribution over the possible illnesses as well. Localize: In this domain the agent must reach a goal position in a grid. The agent does not know where it initially is, and can only sense adjacent walls. In the stochastic version there several places in the grid where the agent may slip and stay in place. This makes the localization in the grid more difficult. Wumpus: In this challenging problem the agent must reach a target position in a grid infested by monsters called Wumpuses. Cells may be unsafe to travel as they may contain either a Wumpus or a pit. Wumpuses emit a stench, and pits emit a breeze, both of which can be sensed in adjacent cells. The agent must sense in multiple positions to identify the safe cells. The stochastic version here also has non-uniform distribution over the safe cells. 6.2 Results For each domain above we run 20 online episodes, and compute the success rate, the average run time for computing the next action, and the average cost to the goal. We did not use a timeout, but runs longer than 100 steps were considered to be stuck in a loop, and terminated. We begin by looking at the quality of the policy — the average cost to the goal. As can be seen, the random rollout policy is best only in the MedPks domain, and close to best in unix. This is not too surprising, because in these two domains the best strategy is very simple, and random strategies easily stumble upon the goal. In blocks all methods achieved similar performance, because the optimal strategy is very short, and rollouts are less important. This domain has many possible actions, and hence a huge branching factor, making it difficult to scale up using POMCP. On doors and localize, which require lengthier trajectories to reach the goal, but do not need long information-gathering efforts, the single state hadd strategy operates very well. However, on Wumpus, where long sequences of actions are needed for information gathering, the multiple-state heuristic works best. We expected the results to be that way, although we expected more significant difference between the "smart" heuristics and the random rollout. With respect to the required time to run the simulations for a single decision, the results are mixed. While obviously the random strategy requires no time to compute the next action during a rollout, it often results in lengthy rollouts, which reduce this effect. The single state heuristic is almost always faster than the multi-state heuristic, but not by much. This paper is available on arxiv under CC 4.0 license. Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. This paper is available on arxiv under CC 4.0 license. Authors: Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction Background Related Work POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Empirical Evaluation Conclusion and References Introduction Introduction Background Background Related Work Related Work POMCP for Stochastic Contingent Planning POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Domain Independent Heuristics for POMCP Empirical Evaluation Empirical Evaluation Conclusion and References Conclusion and References 6 Empirical Evaluation We conduct an empirical study to evaluate our methods. Our methods are implemented in C#. 6.1 Benchmark Domains We extended the following contingent planning benchmarks to stochastic settings: Doors : In the door domain the agent must move in a grid to reach a target position. Odd levels in the grid are all open, while in even levels there are doors, and only one door is open. The agent can sense whether a door is open when it is at adjacent cells. The agent must identify the open doors and get to the target position. In the stochastic version the agent can open a closed door with some probability of success. The agent can hence either search for the already open door, or attempt to open a closed door. Doors Blocks World: In the contingent blocks world problem, the agent does not know the structure of the initial block configuration, but it can sense whether one block is on top of another one, and whether a block is clear. In the stochastic version moving a block from one block to another has a 0.3 probability of success, while moving blocks to and from the table succeeds deterministicly. Hence, it is often preferable to use the table as an intermediate position. Unix: In this domain the agent must search for a file in a file system, and copy it to a destination folder. In the stochastic version there is a non-uniform distribution over the possible locations of the file. MedPks : The agent here needs to identify which illness a patient has and treat it. To do so, the agent tests for each illness independently, until the proper illness is found. The stochastic version here has non-uniform distribution over the possible illnesses as well. MedPks Localize : In this domain the agent must reach a goal position in a grid. The agent does not know where it initially is, and can only sense adjacent walls. In the stochastic version there several places in the grid where the agent may slip and stay in place. This makes the localization in the grid more difficult. Localize Wumpus : In this challenging problem the agent must reach a target position in a grid infested by monsters called Wumpuses. Cells may be unsafe to travel as they may contain either a Wumpus or a pit. Wumpuses emit a stench, and pits emit a breeze, both of which can be sensed in adjacent cells. The agent must sense in multiple positions to identify the safe cells. The stochastic version here also has non-uniform distribution over the safe cells. Wumpus 6.2 Results For each domain above we run 20 online episodes, and compute the success rate, the average run time for computing the next action, and the average cost to the goal. We did not use a timeout, but runs longer than 100 steps were considered to be stuck in a loop, and terminated. We begin by looking at the quality of the policy — the average cost to the goal. As can be seen, the random rollout policy is best only in the MedPks domain, and close to best in unix. This is not too surprising, because in these two domains the best strategy is very simple, and random strategies easily stumble upon the goal. In blocks all methods achieved similar performance, because the optimal strategy is very short, and rollouts are less important. This domain has many possible actions, and hence a huge branching factor, making it difficult to scale up using POMCP. On doors and localize, which require lengthier trajectories to reach the goal, but do not need long information-gathering efforts, the single state h add strategy operates very well. However, on Wumpus, where long sequences of actions are needed for information gathering, the multiple-state heuristic works best. We expected the results to be that way, although we expected more significant difference between the "smart" heuristics and the random rollout. add With respect to the required time to run the simulations for a single decision, the results are mixed. While obviously the random strategy requires no time to compute the next action during a rollout, it often results in lengthy rollouts, which reduce this effect. The single state heuristic is almost always faster than the multi-state heuristic, but not by much.

Rollout Heuristics for Online Stochastic Contingent Planning: Empirical Evaluation

This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel;
(2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction
Background
Related Work
POMCP for Stochastic Contingent Planning
Domain Independent Heuristics for POMCP
Empirical Evaluation
Conclusion and References 4 POMCP for Stochastic Contingent Planning We focus here on goal-oriented POMDP domains specified as stochastic contingent planning problems. We now define this concept formally. This definition does not support noisy observations, however, this is not truly a limitation. One can compile a noisy observation into a deterministic observation over an artificial fact whose value changes stochastically. Consider, for example, a sensor that nosily detects whether there is a wall in front of a robot. Instead of noisily observing whether there is a wall, we can deterministically detect a green light that is lit when the sensor (stochastically) detects a wall. That is, we can observe the green light without noise, but the green light is only noisily correlated with the existence of a wall. Algorithm 1 describes the POMCP implementation for stochastic contingent planning problems. When the agent needs to act, it calls Search. Search repeatedly samples a state (line 3-4) and simulates forward execution given this state is the true underlying system state. The Simulate procedure is recursive. We first check whether the current tree node is a goal belief. This is done be regressing the negation of the goal formula ¬G through the history of the current node. For goal beliefs, the value is 0, and we can stop. Our implementation of POMCP also stops deepening the tree after a predefined threshold Max TreeDepth. If that threshold is reached (line 12), we run a Rollout to compute an estimation for the cost of reaching the goal from this node (line 13). In line 15 we check whether this node has already been expanded, and if not, we compute its children. We do so only for applicable actions whose preconditions are satisfied in the current belief (line 17). Again, this is computed using regression over the history. We now select an action a using the UCT exploration-exploitation criterion (line 21), and sample a next state and an observation (lines 22-27). We call Simulate recursively in line 28. Lines 29-32 update the value of the current node. Lines 28,29 update the counters for the executed action and received observation. Line 31 computes the value for the action as a weighted average over all observations. Line 32 computes the value of the node as the minimal cost among all actions. Our value update, which we empirically found to be more useful, is different than the original POMCP, which uses incremental updates, and more similar to the value update in DESPOT [18]. The Rollout procedure receives as input the current simulated state s, as well as a set B of states (particles) in the node from which the rollout begins. B is used by some of our rollout heuristics, as we explain below. The rollout executes actions given the heuristic rollout policy until the goal has been reached, or a maximal number of steps has been reached. This paper is available on arxiv under CC 4.0 license. Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. This paper is available on arxiv under CC 4.0 license. Authors: Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction Background Related Work POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Empirical Evaluation Conclusion and References Introduction Introduction Background Background Related Work Related Work POMCP for Stochastic Contingent Planning POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Domain Independent Heuristics for POMCP Empirical Evaluation Empirical Evaluation Conclusion and References Conclusion and References 4 POMCP for Stochastic Contingent Planning We focus here on goal-oriented POMDP domains specified as stochastic contingent planning problems. We now define this concept formally. This definition does not support noisy observations, however, this is not truly a limitation. One can compile a noisy observation into a deterministic observation over an artificial fact whose value changes stochastically. Consider, for example, a sensor that nosily detects whether there is a wall in front of a robot. Instead of noisily observing whether there is a wall, we can deterministically detect a green light that is lit when the sensor (stochastically) detects a wall. That is, we can observe the green light without noise, but the green light is only noisily correlated with the existence of a wall. Algorithm 1 describes the POMCP implementation for stochastic contingent planning problems. When the agent needs to act, it calls Search. Search repeatedly samples a state (line 3-4) and simulates forward execution given this state is the true underlying system state. The Simulate procedure is recursive. We first check whether the current tree node is a goal belief. This is done be regressing the negation of the goal formula ¬G through the history of the current node. For goal beliefs, the value is 0, and we can stop. Our implementation of POMCP also stops deepening the tree after a predefined threshold Max TreeDepth. If that threshold is reached (line 12), we run a Rollout to compute an estimation for the cost of reaching the goal from this node (line 13). In line 15 we check whether this node has already been expanded, and if not, we compute its children. We do so only for applicable actions whose preconditions are satisfied in the current belief (line 17). Again, this is computed using regression over the history. We now select an action a using the UCT exploration-exploitation criterion (line 21), and sample a next state and an observation (lines 22-27). We call Simulate recursively in line 28. Lines 29-32 update the value of the current node. Lines 28,29 update the counters for the executed action and received observation. Line 31 computes the value for the action as a weighted average over all observations. Line 32 computes the value of the node as the minimal cost among all actions. Our value update, which we empirically found to be more useful, is different than the original POMCP, which uses incremental updates, and more similar to the value update in DESPOT [18]. The Rollout procedure receives as input the current simulated state s, as well as a set B of states (particles) in the node from which the rollout begins. B is used by some of our rollout heuristics, as we explain below. The rollout executes actions given the heuristic rollout policy until the goal has been reached, or a maximal number of steps has been reached.

Rollout Heuristics: POMCP for Stochastic Contingent Planning

This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel;
(2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction
Background
Related Work
POMCP for Stochastic Contingent Planning
Domain Independent Heuristics for POMCP
Empirical Evaluation
Conclusion and References 3 Related Work Augmenting MCTS methods with heuristics in the context of fully observable MDPs was previously suggested. [14] describe an MCTS tree based approach that uses planning based heuristics. The PROST planner [13] uses a heuristic for estimating the value of states. The DP-UCT approach [26] use a planning heuristic based on deep learning for the rollout phase. We are not aware of previous attempts to adapt these approaches to POMDPs. There were several extensions suggested for POMCP [16]. For example [17] considers dynamic environments, and [11] consider non-linear dynamics. All these methods rely on rollouts, and can hence leverage the rollout strategies that we suggest here. POMCPOW [30] extends POMCP to the challenge of solving POMDPs with continuous state, action, and observation spaces. It constructs the search tree incrementally to explore additional regions of the observation and action spaces. It also requires a rollout policy to evaluate the utility of leaf nodes. Our rollout strategies relay on classical planning approaches which are discrete, and it is hence unlikely that our methods can be extended to continuous domains. DESPOT [29, 32, 18] is an online POMDP solver based on tree search, similar to POMCP. DESPOT uses a different strategy than the UCB rule for constructing the tree, designed to avoid the overly greedy nature of POMCP exploration strategy. DESPOT also requires a so-called default policy to evaluate the utility of a leaf in the tree, and the authors stress the importance of a strong default policy to improve the convergence. Thus, our methods can be directly applied to DESPOT as well. We chose here to focus on POMCP rather than DESPOT, because POMCP is a simpler method, which allows us to better focus on the importance of the heuristic function, independent of the effect of the various augmentations that DESPOT adds on top of POMCP. [22] suggest a method called PSG to evaluate the proximity of states to the goal. They suggest using PSG in several places within POMCP including rollouts. PSG assumes that states are defined in a factored manner using state features, and computes a function from features to the goal using subgoals. In essence, their approach can be considered as a type of heuristic, which is highly related to the concept of landmarks in classical planning [19]. Representing the POMDP as a stochastic contingent planning problem, as we do, allows us to use any heuristic developed in the planning community, and can hence be considered to be an extension of PSG. Similarly, [31] also find it difficult to provide good rollout strategies to compute the value of POMCP leaves. Focusing on a robotics motion planning domain, they suggest SVE, state value estimator, that attempts to evaluate the utility of a state directly. [15] also focus on the need to use heuristics for guiding search in POMDPs. They focus on RTDPBEL [4], an algorithm that runs forward trajectories in belief space to produce a policy. They show that using a heuristic can significantly improve RTDP-BEL. They use domain specific heuristics, and as such, our domain independent approach can also be applied to their methods. This paper is available on arxiv under CC 4.0 license. Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. This paper is available on arxiv under CC 4.0 license. Authors: Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction Background Related Work POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Empirical Evaluation Conclusion and References Introduction Introduction Background Background Related Work Related Work POMCP for Stochastic Contingent Planning POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Domain Independent Heuristics for POMCP Empirical Evaluation Empirical Evaluation Conclusion and References Conclusion and References 3 Related Work Augmenting MCTS methods with heuristics in the context of fully observable MDPs was previously suggested. [14] describe an MCTS tree based approach that uses planning based heuristics. The PROST planner [13] uses a heuristic for estimating the value of states. The DP-UCT approach [26] use a planning heuristic based on deep learning for the rollout phase. We are not aware of previous attempts to adapt these approaches to POMDPs. There were several extensions suggested for POMCP [16]. For example [17] considers dynamic environments, and [11] consider non-linear dynamics. All these methods rely on rollouts, and can hence leverage the rollout strategies that we suggest here. POMCPOW [30] extends POMCP to the challenge of solving POMDPs with continuous state, action, and observation spaces. It constructs the search tree incrementally to explore additional regions of the observation and action spaces. It also requires a rollout policy to evaluate the utility of leaf nodes. Our rollout strategies relay on classical planning approaches which are discrete, and it is hence unlikely that our methods can be extended to continuous domains. DESPOT [29, 32, 18] is an online POMDP solver based on tree search, similar to POMCP. DESPOT uses a different strategy than the UCB rule for constructing the tree, designed to avoid the overly greedy nature of POMCP exploration strategy. DESPOT also requires a so-called default policy to evaluate the utility of a leaf in the tree, and the authors stress the importance of a strong default policy to improve the convergence. Thus, our methods can be directly applied to DESPOT as well. We chose here to focus on POMCP rather than DESPOT, because POMCP is a simpler method, which allows us to better focus on the importance of the heuristic function, independent of the effect of the various augmentations that DESPOT adds on top of POMCP. [22] suggest a method called PSG to evaluate the proximity of states to the goal. They suggest using PSG in several places within POMCP including rollouts. PSG assumes that states are defined in a factored manner using state features, and computes a function from features to the goal using subgoals. In essence, their approach can be considered as a type of heuristic, which is highly related to the concept of landmarks in classical planning [19]. Representing the POMDP as a stochastic contingent planning problem, as we do, allows us to use any heuristic developed in the planning community, and can hence be considered to be an extension of PSG. Similarly, [31] also find it difficult to provide good rollout strategies to compute the value of POMCP leaves. Focusing on a robotics motion planning domain, they suggest SVE, state value estimator, that attempts to evaluate the utility of a state directly. [15] also focus on the need to use heuristics for guiding search in POMDPs. They focus on RTDPBEL [4], an algorithm that runs forward trajectories in belief space to produce a policy. They show that using a heuristic can significantly improve RTDP-BEL. They use domain specific heuristics, and as such, our domain independent approach can also be applied to their methods.

Rollout Heuristics for Online Stochastic Contingent Planning: Related Work

This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel;
(2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction
Background
Related Work
POMCP for Stochastic Contingent Planning
Domain Independent Heuristics for POMCP
Empirical Evaluation
Conclusion and References Partially observable Markov decision processes (POMDP) are a useful model for decision-making under partial observability and stochastic actions. Partially Observable Monte-Carlo Planning is an online algorithm for deciding on the next action to perform, using a Monte-Carlo tree search approach, based on the UCT (UCB applied to trees) algorithm for fully observable Markov-decision processes. POMCP develops an action-observation tree, and at the leaves, uses a rollout policy to provide a value estimate for the leaf. As such, POMCP is highly dependent on the rollout policy to compute good estimates, and hence identify good actions. Thus, many practitioners who use POMCP are required to create strong, domain-specific heuristics. In this paper, we model POMDPs as stochastic contingent planning problems. This allows us to leverage domain-independent heuristics that were developed in the planning community. We suggest two heuristics, the first is based on the well-known hadd heuristic from classical planning, and the second is computed in belief space, taking the value of information into account. 1 Introduction Many autonomous agents operate in environments where actions have stochastic effects, and important information that is required for obtaining the goal is hidden from the agent. Agents in such environments typically execute actions and sense some observations that result from these actions. Based on the accumulated observations the agents can better estimate their current state and decide on the next action to execute. Such environments are often modeled as partially observable Markov decision processes (POMDPs) [28]. POMPD models allow us to reason about the hidden state of the system, typically using a belief state – a distribution over the possible environment states. The belief state can be updated given the executed action and the received observation. One can compute a policy, a mapping from beliefs to actions, that dictates which action should be executed given the current belief. Many algorithms were suggested for computing such policies [25]. However, in larger environments, it often becomes difficult to maintain a belief state, let alone compute a policy for all possible belief states. In such cases, one can use an online re-planning approach, where after every action is executed, the agent computes which action to execute next. Such online approaches replace the lengthy single policy computation which is done offline, before the agent begins to act, with a sequence of shorter computations, which are executed online, during execution, after each action [21]. POMCP [27] is such an online replanning approach, extending the UCT algorithm for fully observable Markov decision processes (MDPs) to POMDPs. POMCP operates by constructing online a search tree, interleaving decision and observation nodes. The root of the tree is a decision node. Each decision node has an outgoing edge for every possible action, ending at an observation node. Then, the outgoing edges from an observation node denote the possible observations that result from the incoming action. The agent computes a value for each node in the tree, and then, the agent can choose, from the root node, the action associated with the edge leading to the highest value child node. To evaluate the value of leaf nodes, POMCP executes a random walk in belief space, known as a rollout, where the agent selects actions from some rollout policy to construct a trajectory in belief space and obtain an estimation of the quality of the leaf node. Clearly, this evaluation is highly dependant on the ability of the rollout policy to reach the agent goals. In complex problems, obtaining the goal may require a lengthy sequence of actions [16], and until the goal is reached, no meaningful rewards are obtained. Indeed, practitioners that use POMCP often implement complex domain-specific heuristics for the rollout policy. In this paper we focus on suggesting domain-independent heuristics for rollout policies. We leverage work in automated planning, using heuristics defined for classical and contingent planning problems [7, 8, 6]. We thus represent POMDP problems in a structured manner, using boolean facts to capture the state of the environments. This allows both for a compact representation of large problems, compared with standard flat representations that do not scale, as well as the ability to use classical planning heuristics. We begin by suggesting using the well-known hadd heuristic for choosing rollout actions [2]. This heuristic searches forward in a delete relaxation setting, until the goal has been reached. Then, the value of an action is determined by the number of steps in the delete relaxation space following the action, required for obtaining the goal. Next, we observe that any state-based rollout policy is inherently limited in its ability to evaluate the missing information required for reaching the goal, and hence, provide some estimate as to the value of information [12] of an action. We hence suggest a multi-state rollout policy, where actions are executed on a set of states jointly, and observations are used to eliminate states that are incompatible with the observed value. We show that this heuristic is much more informed in domains that require complex information-gathering strategies. For an empirical evaluation, we extend domains from the contingent planning community with stochastic effects. We evaluate our heuristics, comparing them to random rollouts, showing that they allow us to provide significantly better behavior. This paper is available on arxiv under CC 4.0 license. Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. This paper is available on arxiv under CC 4.0 license. Authors: Authors: (1) Oded Blumenthal, Software and Information Systems Engineering, Ben Gurion University, Israel; (2) Guy Shani, Software and Information Systems Engineering, Ben Gurion University, Israel. Table of Links Introduction Background Related Work POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Empirical Evaluation Conclusion and References Introduction Introduction Background Background Related Work Related Work POMCP for Stochastic Contingent Planning POMCP for Stochastic Contingent Planning Domain Independent Heuristics for POMCP Domain Independent Heuristics for POMCP Empirical Evaluation Empirical Evaluation Conclusion and References Conclusion and References Partially observable Markov decision processes (POMDP) are a useful model for decision-making under partial observability and stochastic actions. Partially Observable Monte-Carlo Planning is an online algorithm for deciding on the next action to perform, using a Monte-Carlo tree search approach, based on the UCT (UCB applied to trees) algorithm for fully observable Markov-decision processes. POMCP develops an action-observation tree, and at the leaves, uses a rollout policy to provide a value estimate for the leaf. As such, POMCP is highly dependent on the rollout policy to compute good estimates, and hence identify good actions. Thus, many practitioners who use POMCP are required to create strong, domain-specific heuristics. In this paper, we model POMDPs as stochastic contingent planning problems. This allows us to leverage domain-independent heuristics that were developed in the planning community. We suggest two heuristics, the first is based on the well-known h add heuristic from classical planning, and the second is computed in belief space, taking the value of information into account. add 1 Introduction Many autonomous agents operate in environments where actions have stochastic effects, and important information that is required for obtaining the goal is hidden from the agent. Agents in such environments typically execute actions and sense some observations that result from these actions. Based on the accumulated observations the agents can better estimate their current state and decide on the next action to execute. Such environments are often modeled as partially observable Markov decision processes (POMDPs) [28]. POMPD models allow us to reason about the hidden state of the system, typically using a belief state – a distribution over the possible environment states. The belief state can be updated given the executed action and the received observation. One can compute a policy, a mapping from beliefs to actions, that dictates which action should be executed given the current belief. Many algorithms were suggested for computing such policies [25]. However, in larger environments, it often becomes difficult to maintain a belief state, let alone compute a policy for all possible belief states. In such cases, one can use an online re-planning approach, where after every action is executed, the agent computes which action to execute next. Such online approaches replace the lengthy single policy computation which is done offline, before the agent begins to act, with a sequence of shorter computations, which are executed online, during execution, after each action [21]. POMCP [27] is such an online replanning approach, extending the UCT algorithm for fully observable Markov decision processes (MDPs) to POMDPs. POMCP operates by constructing online a search tree, interleaving decision and observation nodes. The root of the tree is a decision node. Each decision node has an outgoing edge for every possible action, ending at an observation node. Then, the outgoing edges from an observation node denote the possible observations that result from the incoming action. The agent computes a value for each node in the tree, and then, the agent can choose, from the root node, the action associated with the edge leading to the highest value child node. To evaluate the value of leaf nodes, POMCP executes a random walk in belief space, known as a rollout, where the agent selects actions from some rollout policy to construct a trajectory in belief space and obtain an estimation of the quality of the leaf node. Clearly, this evaluation is highly dependant on the ability of the rollout policy to reach the agent goals. In complex problems, obtaining the goal may require a lengthy sequence of actions [16], and until the goal is reached, no meaningful rewards are obtained. Indeed, practitioners that use POMCP often implement complex domain-specific heuristics for the rollout policy. In this paper we focus on suggesting domain-independent heuristics for rollout policies. We leverage work in automated planning, using heuristics defined for classical and contingent planning problems [7, 8, 6]. We thus represent POMDP problems in a structured manner, using boolean facts to capture the state of the environments. This allows both for a compact representation of large problems, compared with standard flat representations that do not scale, as well as the ability to use classical planning heuristics. We begin by suggesting using the well-known h add heuristic for choosing rollout actions [2]. This heuristic searches forward in a delete relaxation setting, until the goal has been reached. Then, the value of an action is determined by the number of steps in the delete relaxation space following the action, required for obtaining the goal. add Next, we observe that any state-based rollout policy is inherently limited in its ability to evaluate the missing information required for reaching the goal, and hence, provide some estimate as to the value of information [12] of an action. We hence suggest a multi-state rollout policy, where actions are executed on a set of states jointly, and observations are used to eliminate states that are incompatible with the observed value. We show that this heuristic is much more informed in domains that require complex information-gathering strategies. For an empirical evaluation, we extend domains from the contingent planning community with stochastic effects. We evaluate our heuristics, comparing them to random rollouts, showing that they allow us to provide significantly better behavior.

Rollout Heuristics for Online Stochastic Contingent Planning: Introduction

Venom Foundation, a leader in blockchain technology adoption in regulated markets, is thrilled to announce the signing of a momentous Memorandum of Understanding (MOU) with the UAE Government to develop and implement the National Carbon Credit System. This landmark partnership represents a significant step towards leveraging blockchain technology to address environmental challenges and promote sustainability on a national scale. This revolutionary collaboration underscores the UAE's unwavering commitment to bolstering transparency, reliability, and efficiency in carbon emission management, while using the next-generation blockchain technology of Venom and in doing so, propelling the nation towards its ambitious climate targets of a 40% reduction in carbon emissions by 2030. The Venom blockchain itself is carbon neutral. The Memorandum of Understanding (MoU) signed between the Ministry of Climate Change and Environment (MCCE), the Industrial Innovation Group, and Venom Foundation outlines four strategic objectives: reducing emissions, promoting sustainable agriculture, enhancing environmental health, and conserving biodiversity. As part of this partnership, Venom will actively participate in realizing a greener future. Taryam Matar Taryam, CEO of Industrial Innovation Group, affirmed their dedication to sustainable development, "For Industrial Innovation Group, it is a great honor to contribute to the creation of the United Arab Emirates” first National Carbon Credit Registry System together with Venom. The Industrial Innovation Group steadfastly adheres to sustainable development goals and endeavors to reduce environmental impact, including through decarbonization, as global climate change is closely linked to the increasing concentration of CO2 in the atmosphere. With over 30 years of experience, Industrial Innovation Group has a long history of creating large-scale national registries related to identification processes and excels in developing sustainable pathways for various business sectors, conceptualizing carbon removal initiatives, generating project documentation for different carbon credit registries, and effectively managing, monitoring, and reporting on carbon utilization projects." Peter Knez, Chair of the Foundation Council at Venom Foundation, commented, "We are honored and excited to join hands with the UAE Government to build the National Carbon Credit System. At Venom, we believe that blockchain technology has the potential to drive real-world impact, and this initiative perfectly embodies that vision. Together, we are committed to creating a sustainable future and pioneering solutions that positively influence the global climate." Venom’s success is driven by its groundbreaking technology, strict regulatory compliance, and a scalable and secure platform that serves a wide range of use cases. As the MOU between Venom and the UAE Government comes into effect, both entities eagerly anticipate the successful launch and implementation of the National Carbon Credit System. This historic partnership exemplifies the potential of blockchain technology in advancing environmental initiatives and reinforces the commitment to building a more sustainable and eco-friendly future. About Venom Foundation: Venom Foundation, operating as a decentralized network licensed by the Abu Dhabi Global Market (ADGM), is at the forefront of driving the advancement of global Web3 projects. As the world's first compliant blockchain, Venom provides a secure environment for investors and financial services firms, offering the freedom to build, innovate, and expand. Under the jurisdiction of the ADGM, Venom serves as a trusted platform for authorities and enterprises, ensuring compliance with regulatory requirements. To enhance its capabilities, Venom has developed a range of in-house decentralized applications (dApps) and protocols on its blockchain. With features such as dynamic sharding, low fees, high-speed transactions, and scalability, Venom has the potential to serve as the foundational infrastructure for a thriving global ecosystem of Web3 applications. Its exceptional transaction speeds and limitless scalability enable it to meet the evolving needs of a rapidly growing user base. Disclaimer: This is not a financial promotion. Contact: Jonathan, pr@venomtech.io This story was distributed as a release by Chainwire under HackerNoon’s Brand As An Author Program. Learn more about the program here: https://business.hackernoon.com/brand-as-author

ROLZO

rolzo.com

-- employees

Since n.d.

COMPANY RANKING

ROLZO

EVERGREEN INDEX #9582

Representing this company? Click here to claim and customize this page!

ROLZO WIKI

Apply to get your Tech Company News Page live on HackerNoon.com today!

ROLZO

rolzo.com

-- employees

Since n.d.

COMPANY RANKING

ROLZO

EVERGREEN INDEX #9582

RELATED COMPANIESRANK

STORIES ABOUT ROLZO

Representing this company? Click here to claim and customize this page!

ROLZO WIKI

Apply to get your Tech Company News Page live on HackerNoon.com today!