Get the most recent info and news about heyristic on HackerNoon, where 10k+ technologists publish stories for 4M+ monthly readers.

Heyristic makes connecting with people easier than ever, edit your profile, add your social links and share your profile with your peers.

heyristic

This paper is available on Arxiv under CC 4.0 license.
Authors:
(1) Falke B. Ø. Carlsen, Department of Computer Science, Aalborg University, Denmark & falkeboc@cs.aau.dk;
(2) Lars Bo P. Frydenskov, Department of Computer Science, Aalborg University, Denmark & larsbopark@gmail.com;
(3) Nicolaj Ø. Jensen, Department of Computer Science, Aalborg University, Denmark & noje@cs.aau.dk;
(4) Jener Rasmussen, jener@jener.dk;
(5) Mathias M. Sørensen, mathiasmehlsoerensen@gmail.com;
(6) Asger G. Weirsøe, asger@weircon.dk;
(7) Mathias C. Jensen, Department of Computer Science, Aalborg University, Denmark & mcje@cs.aau.dk;
(8) Kim G. Larsen, Department of Computer Science, Aalborg University, Denmark & kgl@cs.aau.dk. Table of Links Introduction Definitions Model Checking Tool Overview Evaluation Conclusion and References We present CGAAL, our efficient on-the-fly model checker for alternating-time temporal logic (ATL) on concurrent game structures (CGS). We present how our tool encodes ATL as extended dependency graphs with negation edges and employs the distributed on-the-fly algorithm by Dalsgaard et al. Our tool offers multiple novel search strategies for the algorithm, including DHS which is inspired by PageRank and uses the in-degree of configurations as a heuristic, IHS which estimates instability of assignment values, and LPS which estimates the distance to a state satisfying the constituent property using linear programming. CGS are input using our modelling language LCGS, where composition and synchronisation are easily described. We prove the correctness of our encoding, and our experiments show that our tool CGAAL is often one to three orders of magnitude faster than the popular tool PRISM-games on case studies from PRISM’s documentation and among case studies we have developed. In our evaluation, we also compare and evaluate our search strategies, and find that our custom search strategies are often significantly faster than the usual breadth-first and depth-first search strategies. 1 Introduction Software plays a large role in our everyday lives, making decisions, enabling efficient communication, ensuring safety, and many more critical tasks. Furthermore, the complexity of the software and the decisions they have to make are ever-increasing due the to interconnectivity and reactive nature of modern systems. These software systems mutually depend on, communicate with, and guide each other based on their collective and internal states. Even a few interconnected systems that are not necessarily themselves too complex can give rise to an extremely complex system as a whole. Safety-critical software that operates in contexts where errors could lead to human casualties or significant capital losses requires methods to verify their correctness. Unfortunately, such methods are difficult to implement due to the sheer state-space explosion that arises from the inherent parallel composition of systems. In this paper, we consider systems that can be expressed as discrete multiplayer games in which the actors can perform actions concurrently. That is, in each configuration of the game, each player simultaneously chooses an action they wish to perform and the resulting decision vector then deterministically results in the next configuration of the game. Such concurrent games are extremely expressive and can be used to model a variety of complex systems and lends themselves inherently, by their concurrent nature, to describing multi-actor systems. The properties that we wish to verify on these systems are those that can be expressed by Alternating-time Temporal Logic (ATL) [1], a game theoretic extension of Computation Tree Logic (CTL) [2, 3], that like CTL can be used to describe safety and liveness properties. ATL extends CTL by replacing the existential and universal path quantifiers with so-called coalition quantifiers. These coalition quantifiers describe properties of the game in which a coalition of players can either enforce some desired outcome or cannot avoid an outcome. Of course, proof of satisfaction of such property is done by finding a strategy showing that the players can indeed enforce said property or by showing that no matter what strategy the players follow they cannot avoid said property. One existing tool that can model check concurrent (stochastic) games is PRISM-games [12], an extension of the probabilistic model checker PRISM [11]. PRISM excels at stochastic models such as discreteand continuous-time Markov chains, Markov decision processes, and (priced) probabilistic timed automata, for which it can verify various properties described in LTL , CSL, and probabilistic CTL*. There are multiple verification engines in PRISM, both symbolic and explicit state. The PRISM-games extension focuses on stochastic games in which game-theoretic approaches are needed. PRISM-games can among other things synthesise strategies and reason about equilibria-based properties, where players may have distinct, but not necessarily conflicting objectives. These properties are typically described with probabilistic ATL with rewards. In version 3.0 [12], PRISM-games added support for concurrent stochastic games. In [14], Liu and Smolka present a global and a local algorithm to compute fixed-point boolean vertex assignments in dependency graphs with directed hyper-edges representing dependencies between vertex values. The global algorithm has a better worst-case running time of the two, but the on-the-fly local algorithm only explores the graph as needed to compute the fixed-point assignment. Many problems have since been encoded as dependency graphs. Notably, model-checking problems for CTL can be encoded as dependency graphs and the algorithms by Liu and Smolka can be used to compute the satisfaction relation enabling model-checking using dependency graphs. J. F. Jensen et al. [9] show that weighted CTL can be encoded in dependency graphs as well and introduce symbolic edges to handle weights efficiently. In [10], M. C. Jensen et al. introduce symbolic dependency graphs, an encoding of probabilistic weighted CTL, and an implementation of a local and global algorithm. A. Dalsgaard et al. [4] present a distributed extension to the local algorithm to boost the performance and show how to model Petri Nets problems using CTL and dependency graphs. Furthermore, they extend dependency graphs by adding components and negation edges to solve formulae with negations. An abstract dependency graph framework is presented by S. Enevoldsen et al. in [6] where they generalise the various extensions of the dependency graphs with a general algorithm for any Noetherian partial order domain. In the closely related work of [5], S. Enevoldsen et at. uses abstract dependency graphs to model check probabilistic ATL for weighted stochastic games. In multiple works [4, 10] the local algorithm is found to be faster more often than the global algorithm in practice. In this paper, we introduce the tool CGAAL (Concurrent Games AALborg), a model checker implemented in Rust that allows for the verification of ATL properties on concurrent games. CGAAL works by encoding the model checking problem as an extended dependency graph and by implementing the on-the-fly local distributed algorithm by Dalsgaard et al. [4]. The concurrent games are described and inputted to the tool using LCGS, our PRISM-language inspired model language, and for specific ATL formulae, we can output a strategy describing how to ensure satisfaction given a positive result. Furthermore, CGAAL implements a variety of strategies for searching the problem state space: a heuristic inspired by PageRank [15] and two heuristic search strategies that exploit the state vector representation of our model, alongside the usual breadth-first and depth-first approach. We conduct experiments comparing our different search strategies with each other on several case studies and show that having more available compute threads often leads to speed-ups of 1-2 orders of magnitude. We also perform experiments comparing our tool on a selection of case studies to the state-of-the-art PRISM-games. Though while PRISM-games is a tool specialised for probabilistic games we find that our implementation often outperforms PRISM-games and especially whenever we are not required to compute the entire fixed point in which case we are often 1-3 orders of magnitude faster. Again, we emphasise that PRISM games is meant for probabilistic games and as such this is not a completely fair one-to-one comparison. Outline. This paper is structured as follows. Section 2 introduces the formal definitions of concurrent games and alternating-time temporal logic. In Section 3 we present how model checking of ATL properties in concurrent games can be encoded in extended dependency graphs. We also give a short explanation of the CERTAINZERO algorithm and our search strategies. In Section 4 we give a short example of how to use CGAAL and the LCGS language. An evaluation of our tool and a comparison with PRISM can be found in Section 5, and we conclude on our findings in Section 6. This paper is available on Arxiv under CC 4.0 license. This paper is available on Arxiv under CC 4.0 license. Authors: (1) Falke B. Ø. Carlsen, Department of Computer Science, Aalborg University, Denmark & falkeboc@cs.aau.dk; (2) Lars Bo P. Frydenskov, Department of Computer Science, Aalborg University, Denmark & larsbopark@gmail.com; (3) Nicolaj Ø. Jensen, Department of Computer Science, Aalborg University, Denmark & noje@cs.aau.dk; (4) Jener Rasmussen, jener@jener.dk; (5) Mathias M. Sørensen, mathiasmehlsoerensen@gmail.com; (6) Asger G. Weirsøe, asger@weircon.dk; (7) Mathias C. Jensen, Department of Computer Science, Aalborg University, Denmark & mcje@cs.aau.dk; (8) Kim G. Larsen, Department of Computer Science, Aalborg University, Denmark & kgl@cs.aau.dk. This paper is available on Arxiv under CC 4.0 license. Authors: Authors: (1) Falke B. Ø. Carlsen, Department of Computer Science, Aalborg University, Denmark & falkeboc@cs.aau.dk; (2) Lars Bo P. Frydenskov, Department of Computer Science, Aalborg University, Denmark & larsbopark@gmail.com; (3) Nicolaj Ø. Jensen, Department of Computer Science, Aalborg University, Denmark & noje@cs.aau.dk; (4) Jener Rasmussen, jener@jener.dk; (5) Mathias M. Sørensen, mathiasmehlsoerensen@gmail.com; (6) Asger G. Weirsøe, asger@weircon.dk; (7) Mathias C. Jensen, Department of Computer Science, Aalborg University, Denmark & mcje@cs.aau.dk; (8) Kim G. Larsen, Department of Computer Science, Aalborg University, Denmark & kgl@cs.aau.dk. Table of Links Introduction Introduction Definitions Definitions Model Checking Model Checking Tool Overview Tool Overview Evaluation Evaluation Conclusion and References Conclusion and References We present CGAAL, our efficient on-the-fly model checker for alternating-time temporal logic (ATL) on concurrent game structures (CGS). We present how our tool encodes ATL as extended dependency graphs with negation edges and employs the distributed on-the-fly algorithm by Dalsgaard et al. Our tool offers multiple novel search strategies for the algorithm, including DHS which is inspired by PageRank and uses the in-degree of configurations as a heuristic, IHS which estimates instability of assignment values, and LPS which estimates the distance to a state satisfying the constituent property using linear programming. CGS are input using our modelling language LCGS, where composition and synchronisation are easily described. We prove the correctness of our encoding, and our experiments show that our tool CGAAL is often one to three orders of magnitude faster than the popular tool PRISM-games on case studies from PRISM’s documentation and among case studies we have developed. In our evaluation, we also compare and evaluate our search strategies, and find that our custom search strategies are often significantly faster than the usual breadth-first and depth-first search strategies. 1 Introduction Software plays a large role in our everyday lives, making decisions, enabling efficient communication, ensuring safety, and many more critical tasks. Furthermore, the complexity of the software and the decisions they have to make are ever-increasing due the to interconnectivity and reactive nature of modern systems. These software systems mutually depend on, communicate with, and guide each other based on their collective and internal states. Even a few interconnected systems that are not necessarily themselves too complex can give rise to an extremely complex system as a whole. Safety-critical software that operates in contexts where errors could lead to human casualties or significant capital losses requires methods to verify their correctness. Unfortunately, such methods are difficult to implement due to the sheer state-space explosion that arises from the inherent parallel composition of systems. In this paper, we consider systems that can be expressed as discrete multiplayer games in which the actors can perform actions concurrently. That is, in each configuration of the game, each player simultaneously chooses an action they wish to perform and the resulting decision vector then deterministically results in the next configuration of the game. Such concurrent games are extremely expressive and can be used to model a variety of complex systems and lends themselves inherently, by their concurrent nature, to describing multi-actor systems. The properties that we wish to verify on these systems are those that can be expressed by Alternating-time Temporal Logic (ATL) [1], a game theoretic extension of Computation Tree Logic (CTL) [2, 3], that like CTL can be used to describe safety and liveness properties. ATL extends CTL by replacing the existential and universal path quantifiers with so-called coalition quantifiers. These coalition quantifiers describe properties of the game in which a coalition of players can either enforce some desired outcome or cannot avoid an outcome. Of course, proof of satisfaction of such property is done by finding a strategy showing that the players can indeed enforce said property or by showing that no matter what strategy the players follow they cannot avoid said property. One existing tool that can model check concurrent (stochastic) games is PRISM-games [12], an extension of the probabilistic model checker PRISM [11]. PRISM excels at stochastic models such as discreteand continuous-time Markov chains, Markov decision processes, and (priced) probabilistic timed automata, for which it can verify various properties described in LTL , CSL, and probabilistic CTL*. There are multiple verification engines in PRISM, both symbolic and explicit state. The PRISM-games extension focuses on stochastic games in which game-theoretic approaches are needed. PRISM-games can among other things synthesise strategies and reason about equilibria-based properties, where players may have distinct, but not necessarily conflicting objectives. These properties are typically described with probabilistic ATL with rewards. In version 3.0 [12], PRISM-games added support for concurrent stochastic games. In [14], Liu and Smolka present a global and a local algorithm to compute fixed-point boolean vertex assignments in dependency graphs with directed hyper-edges representing dependencies between vertex values. The global algorithm has a better worst-case running time of the two, but the on-the-fly local algorithm only explores the graph as needed to compute the fixed-point assignment. Many problems have since been encoded as dependency graphs. Notably, model-checking problems for CTL can be encoded as dependency graphs and the algorithms by Liu and Smolka can be used to compute the satisfaction relation enabling model-checking using dependency graphs. J. F. Jensen et al. [9] show that weighted CTL can be encoded in dependency graphs as well and introduce symbolic edges to handle weights efficiently. In [10], M. C. Jensen et al. introduce symbolic dependency graphs, an encoding of probabilistic weighted CTL, and an implementation of a local and global algorithm. A. Dalsgaard et al. [4] present a distributed extension to the local algorithm to boost the performance and show how to model Petri Nets problems using CTL and dependency graphs. Furthermore, they extend dependency graphs by adding components and negation edges to solve formulae with negations. An abstract dependency graph framework is presented by S. Enevoldsen et al. in [6] where they generalise the various extensions of the dependency graphs with a general algorithm for any Noetherian partial order domain. In the closely related work of [5], S. Enevoldsen et at. uses abstract dependency graphs to model check probabilistic ATL for weighted stochastic games. In multiple works [4, 10] the local algorithm is found to be faster more often than the global algorithm in practice. In this paper, we introduce the tool CGAAL (Concurrent Games AALborg), a model checker implemented in Rust that allows for the verification of ATL properties on concurrent games. CGAAL works by encoding the model checking problem as an extended dependency graph and by implementing the on-the-fly local distributed algorithm by Dalsgaard et al. [4]. The concurrent games are described and inputted to the tool using LCGS, our PRISM-language inspired model language, and for specific ATL formulae, we can output a strategy describing how to ensure satisfaction given a positive result. Furthermore, CGAAL implements a variety of strategies for searching the problem state space: a heuristic inspired by PageRank [15] and two heuristic search strategies that exploit the state vector representation of our model, alongside the usual breadth-first and depth-first approach. We conduct experiments comparing our different search strategies with each other on several case studies and show that having more available compute threads often leads to speed-ups of 1-2 orders of magnitude. We also perform experiments comparing our tool on a selection of case studies to the state-of-the-art PRISM-games. Though while PRISM-games is a tool specialised for probabilistic games we find that our implementation often outperforms PRISM-games and especially whenever we are not required to compute the entire fixed point in which case we are often 1-3 orders of magnitude faster. Again, we emphasise that PRISM games is meant for probabilistic games and as such this is not a completely fair one-to-one comparison. Outline . This paper is structured as follows. Section 2 introduces the formal definitions of concurrent games and alternating-time temporal logic. In Section 3 we present how model checking of ATL properties in concurrent games can be encoded in extended dependency graphs. We also give a short explanation of the CERTAINZERO algorithm and our search strategies. Outline In Section 4 we give a short example of how to use CGAAL and the LCGS language. An evaluation of our tool and a comparison with PRISM can be found in Section 5, and we conclude on our findings in Section 6. This paper is available on Arxiv under CC 4.0 license. This paper is available on Arxiv under CC 4.0 license. Arxiv

Introducing CGAAL: A Distributed On-The-Fly ATL Model Checker With Heuristics

Hybrid Meta-Heuristic for Efficient Course Timetabling

Meta-heuristics and Feasible Solutions in Course Timetabling

A Hybrid Meta-Heuristic for Feasible Large-Scale Course Timetables With Instance Decomposition

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

Authors:
(1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento;
(2) Marco Robol, Department of Information Engineering and Computer Science University of Trento;
(3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento;
(4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. 6 Conclusion This work aimed to evaluate the performance of several known heuristic search algorithms, such as D*, D* Lite, LPA*, LRTA*, RTAA*, and ARA* in terms of solving time, memory consumption, and path cost. The evaluation was made using different randomly generated grid environments with different characteristics alongside personalized grid environments with horizontal walls and different wall lengths as different hinders. Our experimental evaluation revealed that all the algorithms exhibit different performances with strengths and weaknesses under different grid characterizations. D* Lite consistently generated the shortest paths even in obstacle-dense grids, indicating its efficiency in dense environments. ARA* consistently provides faster solutions as the grid size increases, particularly larger than 100, while RTTA* generates faster solutions in smaller grid sizes, with the advantage of not being affected by dense environments. Our study provides valuable insights into selecting the appropriate heuristic search algorithm in the pathfinding domain. Using these insights, we propose a selection algorithm used to optimize the performance needed in a pathfinding domain, such as, solving time, path length, or memory consumption. However, our evaluation focused only on static environments, while dynamic environments may introduce additional challenges. Furthermore, we considered a limited set of experiments, not covering all possible combinations of the grid characteristics. This limitation means that the selection algorithm might not always recommend the most optimal solution, as seen in the example we introduced to evaluate our algorithm. In future work, we aim to address these limitations as follows: Firstly, we plan to extend our evaluation of the search algorithms to include dynamic environments. Secondly, we intend to explore various combinations of both domain characterization and priorities. Furthermore, we want to include additional scenario configuration, extending the random obstacles and the walls scenarios. With such additional understanding, we aim to refine our selection algorithm to automatically take decisions among the best search algorithms, based on the type of obstacles in the local search space. References [1] Nafiz Arica, Aysegul Mut, Alper Yörükçü & Kadir Alpaslan Demir (2017): An Empirical Comparison of Search Approaches for Moving Agents. Comput. Intell. 33(3), pp. 368–400, doi:10.1111/coin.12092. [2] Yngvi Björnsson, Vadim Bulitko & Nathan R. Sturtevant (2009): TBA*: Time-Bounded A*. In Craig Boutilier, editor: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pp. 431–436. Available at http://ijcai.org/ Proceedings/09/Papers/079.pdf. [3] David Bond, Niels A. Widger, Wheeler Ruml & Xiaoxun Sun (2010): Real-Time Search in Dynamic Worlds. In Ariel Felner & Nathan R. Sturtevant, editors: Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, July 8 10, 2010, AAAI Press, doi:10.1609/socs.v1i1.18174. Available at http://aaai.org/ocs/index.php/SOCS/SOCS10/paper/ view/2103. [4] Guillaume Brat, Ewen Denney, Dimitra Giannakopoulou, Jeremy Frank & Ari Jónsson (2006): Verification of autonomous systems for space applications. In: 2006 IEEE Aerospace Conference, IEEE, pp. 11–pp, doi:10.1109/AERO.2006.1656029. [5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein (2009): Introduction to Algorithms, 3rd Edition. MIT Press. Available at http://mitpress.mit.edu/books/ introduction-algorithms. [6] A. Elfes (1989): Using occupancy grids for mobile robot perception and navigation. Computer 22(6), pp. 46–57, doi:10.1109/2.30720. [7] Carlos Hernández & Jorge A. Baier (2011): Real-Time Heuristic Search with Depression Avoidance. In Toby Walsh, editor: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, IJCAI/AAAI, pp. 578–583, doi:10.5591/978-1-57735-516- 8/IJCAI11-104. [8] Mohd Javaid, Abid Haleem, Ravi Pratap Singh & Rajiv Suman (2021): Substantial capabilities of robotics in enhancing industry 4.0 implementation. Cognitive Robotics 1, pp. 58–75, doi:10.1016/j.cogr.2021.06.001. [9] Sven Koenig (2001): Agent-Centered Search. AI Mag. 22(4), pp. 109–132, doi:10.1609/aimag.v22i4.1596. [10] Sven Koenig (2004): A Comparison of Fast Search Methods for Real-Time Situated Agents, pp. 864–871. doi:10.1109/AAMAS.2004.10122. Available at https://doi.ieeecomputersociety.org/10.1109/ AAMAS.2004.10122. [11] Sven Koenig & Maxim Likhachev (2002): D*Lite, pp. 476–483. Available at http://www.aaai.org/ Library/AAAI/2002/aaai02-072.php. [12] Sven Koenig & Maxim Likhachev (2006): Real-time adaptive A*. In Hideyuki Nakashima, Michael P. Wellman, Gerhard Weiss & Peter Stone, editors: 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006), Hakodate, Japan, May 8-12, 2006, ACM, pp. 281–288, doi:10.1145/1160633.1160682. [13] Sven Koenig & Xiaoxun Sun (2009): Comparing real-time and incremental heuristic search for real-time situated agents. Auton. Agents Multi Agent Syst. 18(3), pp. 313–341, doi:10.1007/s10458 008-9061-x. [14] Richard E Korf (1990): Real-time heuristic search. Artificial intelligence 42(2-3), pp. 189–211, doi:10.1016/0004-3702(90)90054-4. [15] Maxim Likhachev, Geoffrey J. Gordon & Sebastian Thrun (2003): ARA*: Anytime A* with Provable Bounds on Sub-Optimality, pp. 767–774. Available at https://proceedings.neurips.cc/paper/2003/hash/ ee8fe9093fbbb687bef15a38facc44d2-Abstract.html. [16] Manuel Müller, Timo Müller, Behrang Ashtari Talkhestani, Philipp Marks, Nasser Jazdi & Michael Weyrich (2021): Industrial autonomous systems: a survey on definitions, characteristics and abilities. atAutomatisierungstechnik 69(1), pp. 3–13, doi:10.1515/auto-2020-0131. [17] Michal Pechoucek, Simon G Thompson & Holger Voos (2008): Defence Industry Applications of Autonomous Agents and Multi-Agent Systems. Springer, doi:10.1007/978-3-7643-8571-2. [18] Francisco J Perez-Grau, J Ramiro Martinez-de Dios, Julio L Paneque, J Joaquin Acevedo, Arturo Torres-González, Antidio Viguria, Juan R Astorga & Anibal Ollero (2021): Introducing autonomous aerial robots in industrial manufacturing. Journal of Manufacturing Systems 60, pp. 312–324, doi:10.1016/j.jmsy.2021.06.008. [19] José Ricardo Sánchez-Ibáñez, Carlos Jesús Pérez-del-Pulgar & Alfonso García-Cerezo (2021): Path Planning for Autonomous Mobile Robots: A Review. Sensors 21(23), p. 7898, doi:10.3390/s21237898. [20] Anthony Stentz (1995): The Focussed D* Algorithm for Real-Time Replanning. In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 95, Montréal Québec, Canada, August 20-25 1995, 2 Volumes, Morgan Kaufmann, pp. 1652–1659. Available at http://ijcai.org/ Proceedings/95-2/Papers/082.pdf. [21] Dmitry S. Yershov & Steven M. LaValle (2011): Simplicial Dijkstra and A* algorithms for optimal feedback planning. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2011, San Francisco, CA, USA, September 25-30, 2011, IEEE, pp. 3862–3867, doi:10.1109/IROS.2011.6095032. This paper is available on arxiv under CC 4.0 license. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. 6 Conclusion This work aimed to evaluate the performance of several known heuristic search algorithms, such as D*, D* Lite, LPA*, LRTA*, RTAA*, and ARA* in terms of solving time, memory consumption, and path cost. The evaluation was made using different randomly generated grid environments with different characteristics alongside personalized grid environments with horizontal walls and different wall lengths as different hinders. Our experimental evaluation revealed that all the algorithms exhibit different performances with strengths and weaknesses under different grid characterizations. D* Lite consistently generated the shortest paths even in obstacle-dense grids, indicating its efficiency in dense environments. ARA* consistently provides faster solutions as the grid size increases, particularly larger than 100, while RTTA* generates faster solutions in smaller grid sizes, with the advantage of not being affected by dense environments. Our study provides valuable insights into selecting the appropriate heuristic search algorithm in the pathfinding domain. Using these insights, we propose a selection algorithm used to optimize the performance needed in a pathfinding domain, such as, solving time, path length, or memory consumption. However, our evaluation focused only on static environments, while dynamic environments may introduce additional challenges. Furthermore, we considered a limited set of experiments, not covering all possible combinations of the grid characteristics. This limitation means that the selection algorithm might not always recommend the most optimal solution, as seen in the example we introduced to evaluate our algorithm. In future work, we aim to address these limitations as follows: Firstly, we plan to extend our evaluation of the search algorithms to include dynamic environments. Secondly, we intend to explore various combinations of both domain characterization and priorities. Furthermore, we want to include additional scenario configuration, extending the random obstacles and the walls scenarios. With such additional understanding, we aim to refine our selection algorithm to automatically take decisions among the best search algorithms, based on the type of obstacles in the local search space. References [1] Nafiz Arica, Aysegul Mut, Alper Yörükçü & Kadir Alpaslan Demir (2017): An Empirical Comparison of Search Approaches for Moving Agents. Comput. Intell. 33(3), pp. 368–400, doi:10.1111/coin.12092. [2] Yngvi Björnsson, Vadim Bulitko & Nathan R. Sturtevant (2009): TBA*: Time-Bounded A*. In Craig Boutilier, editor: IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pp. 431–436. Available at http://ijcai.org/ Proceedings/09/Papers/079.pdf. [3] David Bond, Niels A. Widger, Wheeler Ruml & Xiaoxun Sun (2010): Real-Time Search in Dynamic Worlds. In Ariel Felner & Nathan R. Sturtevant, editors: Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, July 8 10, 2010, AAAI Press, doi:10.1609/socs.v1i1.18174. Available at http://aaai.org/ocs/index.php/SOCS/SOCS10/paper/ view/2103. [4] Guillaume Brat, Ewen Denney, Dimitra Giannakopoulou, Jeremy Frank & Ari Jónsson (2006): Verification of autonomous systems for space applications. In: 2006 IEEE Aerospace Conference, IEEE, pp. 11–pp, doi:10.1109/AERO.2006.1656029. [5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein (2009): Introduction to Algorithms, 3rd Edition. MIT Press. Available at http://mitpress.mit.edu/books/ introduction-algorithms. [6] A. Elfes (1989): Using occupancy grids for mobile robot perception and navigation. Computer 22(6), pp. 46–57, doi:10.1109/2.30720. [7] Carlos Hernández & Jorge A. Baier (2011): Real-Time Heuristic Search with Depression Avoidance. In Toby Walsh, editor: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, IJCAI/AAAI, pp. 578–583, doi:10.5591/978-1-57735-516- 8/IJCAI11-104. [8] Mohd Javaid, Abid Haleem, Ravi Pratap Singh & Rajiv Suman (2021): Substantial capabilities of robotics in enhancing industry 4.0 implementation. Cognitive Robotics 1, pp. 58–75, doi:10.1016/j.cogr.2021.06.001. [9] Sven Koenig (2001): Agent-Centered Search. AI Mag. 22(4), pp. 109–132, doi:10.1609/aimag.v22i4.1596. [10] Sven Koenig (2004): A Comparison of Fast Search Methods for Real-Time Situated Agents, pp. 864–871. doi:10.1109/AAMAS.2004.10122. Available at https://doi.ieeecomputersociety.org/10.1109/ AAMAS.2004.10122. [11] Sven Koenig & Maxim Likhachev (2002): D*Lite, pp. 476–483. Available at http://www.aaai.org/ Library/AAAI/2002/aaai02-072.php. [12] Sven Koenig & Maxim Likhachev (2006): Real-time adaptive A*. In Hideyuki Nakashima, Michael P. Wellman, Gerhard Weiss & Peter Stone, editors: 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006), Hakodate, Japan, May 8-12, 2006, ACM, pp. 281–288, doi:10.1145/1160633.1160682. [13] Sven Koenig & Xiaoxun Sun (2009): Comparing real-time and incremental heuristic search for real-time situated agents. Auton. Agents Multi Agent Syst. 18(3), pp. 313–341, doi:10.1007/s10458 008-9061-x. [14] Richard E Korf (1990): Real-time heuristic search. Artificial intelligence 42(2-3), pp. 189–211, doi:10.1016/0004-3702(90)90054-4. [15] Maxim Likhachev, Geoffrey J. Gordon & Sebastian Thrun (2003): ARA*: Anytime A* with Provable Bounds on Sub-Optimality, pp. 767–774. Available at https://proceedings.neurips.cc/paper/2003/hash/ ee8fe9093fbbb687bef15a38facc44d2-Abstract.html. [16] Manuel Müller, Timo Müller, Behrang Ashtari Talkhestani, Philipp Marks, Nasser Jazdi & Michael Weyrich (2021): Industrial autonomous systems: a survey on definitions, characteristics and abilities. atAutomatisierungstechnik 69(1), pp. 3–13, doi:10.1515/auto-2020-0131. [17] Michal Pechoucek, Simon G Thompson & Holger Voos (2008): Defence Industry Applications of Autonomous Agents and Multi-Agent Systems. Springer, doi:10.1007/978-3-7643-8571-2. [18] Francisco J Perez-Grau, J Ramiro Martinez-de Dios, Julio L Paneque, J Joaquin Acevedo, Arturo Torres-González, Antidio Viguria, Juan R Astorga & Anibal Ollero (2021): Introducing autonomous aerial robots in industrial manufacturing. Journal of Manufacturing Systems 60, pp. 312–324, doi:10.1016/j.jmsy.2021.06.008. [19] José Ricardo Sánchez-Ibáñez, Carlos Jesús Pérez-del-Pulgar & Alfonso García-Cerezo (2021): Path Planning for Autonomous Mobile Robots: A Review. Sensors 21(23), p. 7898, doi:10.3390/s21237898. [20] Anthony Stentz (1995): The Focussed D* Algorithm for Real-Time Replanning. In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI 95, Montréal Québec, Canada, August 20-25 1995, 2 Volumes, Morgan Kaufmann, pp. 1652–1659. Available at http://ijcai.org/ Proceedings/95-2/Papers/082.pdf. [21] Dmitry S. Yershov & Steven M. LaValle (2011): Simplicial Dijkstra and A* algorithms for optimal feedback planning. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2011, San Francisco, CA, USA, September 25-30, 2011, IEEE, pp. 3862–3867, doi:10.1109/IROS.2011.6095032. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Future Directions in Heuristic Search

Authors:
(1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento;
(2) Marco Robol, Department of Information Engineering and Computer Science University of Trento;
(3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento;
(4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. 3 Experimental environment and performance metrices Heuristic search algorithms play an important role in fields such as robotic pathfinding, as they determine the optimal path given a starting position and a goal position. Grid-based environments are commonly used for representing real-world environment scenarios, where these algorithms can be implemented, such as in autonomous navigation and robotics [6]. In this study, we comprehensively analyze well known heuristic search algorithms, namely D*, D* Lite, LPA*, LRTA*, RTAA*, and ARA* in different grid environments. We use the Euclidean distance heuristic to guide the search of the algorithms and assess the impact of a few grid characteristics, such as the obstacle density and the grid size, on the performance of the algorithms. In our study, we use grid-based environments due to their simplicity, and control ease, in addition to being commonly used in path-planning tasks in the research community. The grids are composed of white cells, representing traversable states, whereas the black ones represent non-traversable obstacles. The agent in our simulation can move in eight directions, with a cost equal to 1 for horizontal and vertical moves, and √ 2 for diagonal movements. We used two types of grid environments: randomly generated grid environments and personalized grid environments. Randomly generated grid-based environments: The grids are characterized by three parameters: grid size (NxN), obstacle density, and the distance between the start and the goal states. To investigate the impact of each parameter on the performance of the search algorithms, we varied each parameter independently while keeping the other parameters constant. The variations included varying the grid size, varying start to goal distance, and varying the obstacle densities. For each grid in a variation, we generated ten random instances of the same grid parameters (e.g., a grid with 0.25 of obstacle density, size 300x300, and 140 of start to goal distance, have ten instances, which were generated randomly). Personalised grid environment: Designed for simulating more specific scenarios. These grids have fixed size (71x31 units) and a fixed position for both the start and goal states, and they were divided into two parts based on their obstacle configuration: • Horizontal wall configuration: For these experiments, we add horizontal walls of half grid width every 10 units of grid length. We added the walls in two orientations: once from left to right, and once from right to left in the newly generated grid. • Horizontal wall length configuration: Here, we add all possible walls that can be placed within the grid length, and each time we generate a new grid we increase all wall lengths by 2 units. We adopted these two distinct environments to provide a thorough analysis, seeking to reveal nuanced insights into the performance of the search algorithm in the presence of two different hindering scenarios. In the first one, obstacles are scattered randomly within the grid, whereas in the second one, the wall-like structures, appear as a mass of connected obstacles. To evaluate the performance of the different search algorithms used in the experiments, we have selected the following metrics: • Path cost: The metric measures the path length or the number of executed actions from the start to the goal state. It indicates the quality of the solution. • Memory consumption: It measures the required amount of memory for the algorithm to find a solution. It is relevant to check the scalability of the algorithm, and it is measured in (KB). • Solving Time: Represent the total time an algorithm takes to find a solution in (ms), measured in milliseconds (ms). We carried out our experiments on 3.30GHz 27 Intel i9 cores, equipped with 250Gb of RAM and running Ubuntu Linux 22.04. Using the following settings: All algorithms were using the Euclidean distance as the heuristic function. For LRTA* and RTAA*, we set the number of expended nodes to 250 for each iteration. The ARA* algorithm was run with a weight of 2.5 for the heuristic. We ran each algorithm 100 times on each grid to account for randomness and to ensure the reliability of the results. This paper is available on arxiv under CC 4.0 license. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. 3 Experimental environment and performance metrices Heuristic search algorithms play an important role in fields such as robotic pathfinding, as they determine the optimal path given a starting position and a goal position. Grid-based environments are commonly used for representing real-world environment scenarios, where these algorithms can be implemented, such as in autonomous navigation and robotics [6]. In this study, we comprehensively analyze well known heuristic search algorithms, namely D*, D* Lite, LPA*, LRTA*, RTAA*, and ARA* in different grid environments. We use the Euclidean distance heuristic to guide the search of the algorithms and assess the impact of a few grid characteristics, such as the obstacle density and the grid size, on the performance of the algorithms. In our study, we use grid-based environments due to their simplicity, and control ease, in addition to being commonly used in path-planning tasks in the research community. The grids are composed of white cells, representing traversable states, whereas the black ones represent non-traversable obstacles. The agent in our simulation can move in eight directions, with a cost equal to 1 for horizontal and vertical moves, and √ 2 for diagonal movements. We used two types of grid environments: randomly generated grid environments and personalized grid environments. Randomly generated grid-based environments: The grids are characterized by three parameters: Randomly generated grid-based environments: grid size (NxN), obstacle density, and the distance between the start and the goal states. To investigate the impact of each parameter on the performance of the search algorithms, we varied each parameter independently while keeping the other parameters constant. The variations included varying the grid size, varying start to goal distance, and varying the obstacle densities. For each grid in a variation, we generated ten random instances of the same grid parameters (e.g., a grid with 0.25 of obstacle density, size 300x300, and 140 of start to goal distance, have ten instances, which were generated randomly). Personalised grid environment: Designed for simulating more specific scenarios. These grids have fixed size (71x31 units) and a fixed position for both the start and goal states, and they were divided into two parts based on their obstacle configuration: Personalised grid environment: • Horizontal wall configuration: For these experiments, we add horizontal walls of half grid width every 10 units of grid length. We added the walls in two orientations: once from left to right, and once from right to left in the newly generated grid. Horizontal wall configuration: • Horizontal wall length configuration: Here, we add all possible walls that can be placed within Horizontal wall length configuration: the grid length, and each time we generate a new grid we increase all wall lengths by 2 units. We adopted these two distinct environments to provide a thorough analysis, seeking to reveal nuanced insights into the performance of the search algorithm in the presence of two different hindering scenarios. In the first one, obstacles are scattered randomly within the grid, whereas in the second one, the wall-like structures, appear as a mass of connected obstacles. To evaluate the performance of the different search algorithms used in the experiments, we have selected the following metrics: • Path cost: The metric measures the path length or the number of executed actions from the start to the goal state. It indicates the quality of the solution. Path cost: • Memory consumption: It measures the required amount of memory for the algorithm to find a solution. It is relevant to check the scalability of the algorithm, and it is measured in (KB). Memory consumption: • Solving Time: Represent the total time an algorithm takes to find a solution in (ms), measured in milliseconds (ms). Solving Time: We carried out our experiments on 3.30GHz 27 Intel i9 cores, equipped with 250Gb of RAM and running Ubuntu Linux 22.04. Using the following settings: All algorithms were using the Euclidean distance as the heuristic function. For LRTA* and RTAA*, we set the number of expended nodes to 250 for each iteration. The ARA* algorithm was run with a weight of 2.5 for the heuristic. We ran each algorithm 100 times on each grid to account for randomness and to ensure the reliability of the results. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Performance Metrics of Heuristic Search Algorithms in Grid Environments

গ্রিড এনভায়রনমেন্টে হিউরিস্টিক সার্চ অ্যালগরিদমের পারফরম্যান্স মেট্রিক্স

Leistungsmetriken heuristischer Suchalgorithmen in Grid-Umgebungen

Métricas de rendimiento de algoritmos de búsqueda heurística en entornos de red

Mesures de performance des algorithmes de recherche heuristiques dans les environnements de grille

ग्रिड वातावरण में ह्यूरिस्टिक खोज एल्गोरिदम के प्रदर्शन मेट्रिक्स

グリッド環境におけるヒューリスティック探索アルゴリズムのパフォーマンス指標

그리드 환경에서 휴리스틱 검색 알고리즘의 성능 지표

Métricas de desempenho de algoritmos de pesquisa heurística em ambientes de grade

Метрики производительности алгоритмов эвристического поиска в грид-средах

Izgara Ortamlarında Sezgisel Arama Algoritmalarının Performans Ölçümleri

Số liệu hiệu suất của thuật toán tìm kiếm heuristic trong môi trường lưới

网格环境中启发式搜索算法的性能指标

Authors:
(1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento;
(2) Marco Robol, Department of Information Engineering and Computer Science University of Trento;
(3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento;
(4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. The paper presents a comprehensive performance evaluation of some heuristic search algorithms in the context of autonomous systems and robotics. The objective of the study is to evaluate and compare the performance of different search algorithms in different problem settings on the pathfinding domain. Experiments give us insight into the behavior of the evaluated heuristic search algorithms, over the variation of different parameters: domain size, obstacle density, and distance between the start and the goal states. Results are then used to design a selection algorithm that, on the basis of problem characteristics, suggests the best search algorithm to use. 1 Introduction Autonomous agents and robotics have increasingly been used in various domains, such as, industrial applications [16, 18, 8], surveillance [17], and exploration [4]. These systems are designed to autonomously make decisions and execute actions based on their dynamic and unpredictable environments. Under such conditions, systems are required to be as reactive as possible to changes in the environment. Therefore, ensuring good performance is a significant challenge. In the case of planning, selecting the most effective search algorithm becomes crucial to enhance the overall performance of the system. Real-time heuristic search (RTS) (e.g.,[14, 9]) is a state-of-the-art approach for planning while executing, that helps minimize agent reaction time. These algorithms enable agents to make decisions by interleaving planning with execution while considering the evolving environment, which is an essential property in applications such as robotics, and video game agents. Despite the numerous methods proposed in this field [14, 13, 12, 3, 2], a comprehensive understanding of these algorithms remains elusive. Existing studies [1, 13, 10] have primarily focused on testing the performance of the algorithm based on a single parameter (e.g., look-ahead, sensor range). However, the influence of the problem domain characteristics on algorithm performance remains an understudied aspect. Our objective is to investigate the characteristics of the problem that may impact algorithm performances. To achieve this, we first review existing state of art of search algorithms and their applications. Then we design our experiments to evaluate some of the algorithm performances, also defining relevant metrics to use in the evaluation. Later on, experiment results are analyzed to provide a comprehensive understanding of how problem characteristics influence the performance of the different search algorithms. Finally, from the insight gained from our study, we introduce a selection algorithm that helps us to select the appropriate search algorithm. This paper is structured as follows. We begin by reviewing state-of-the-art search algorithms and previous performance evaluation studies. Next, we describe the approach we adopted to evaluate the search algorithms that are subject to our study, define the problem domain and its characteristics, and the performance metrics. In section four, we present our experimental results. Section five introduces our proposed selection algorithm with an execution example. Finally, we derive our conclusion, the limitations of our study, and possible directions for future work. This paper is available on arxiv under CC 4.0 license. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini, Department of Information Engineering and Computer Science University of Trento. The paper presents a comprehensive performance evaluation of some heuristic search algorithms in the context of autonomous systems and robotics. The objective of the study is to evaluate and compare the performance of different search algorithms in different problem settings on the pathfinding domain. Experiments give us insight into the behavior of the evaluated heuristic search algorithms, over the variation of different parameters: domain size, obstacle density, and distance between the start and the goal states. Results are then used to design a selection algorithm that, on the basis of problem characteristics, suggests the best search algorithm to use. 1 Introduction Autonomous agents and robotics have increasingly been used in various domains, such as, industrial applications [16, 18, 8], surveillance [17], and exploration [4]. These systems are designed to autonomously make decisions and execute actions based on their dynamic and unpredictable environments. Under such conditions, systems are required to be as reactive as possible to changes in the environment. Therefore, ensuring good performance is a significant challenge. In the case of planning, selecting the most effective search algorithm becomes crucial to enhance the overall performance of the system. Real-time heuristic search (RTS) (e.g.,[14, 9]) is a state-of-the-art approach for planning while executing, that helps minimize agent reaction time. These algorithms enable agents to make decisions by interleaving planning with execution while considering the evolving environment, which is an essential property in applications such as robotics, and video game agents. Despite the numerous methods proposed in this field [14, 13, 12, 3, 2], a comprehensive understanding of these algorithms remains elusive. Existing studies [1, 13, 10] have primarily focused on testing the performance of the algorithm based on a single parameter (e.g., look-ahead, sensor range). However, the influence of the problem domain characteristics on algorithm performance remains an understudied aspect. Our objective is to investigate the characteristics of the problem that may impact algorithm performances. To achieve this, we first review existing state of art of search algorithms and their applications. Then we design our experiments to evaluate some of the algorithm performances, also defining relevant metrics to use in the evaluation. Later on, experiment results are analyzed to provide a comprehensive understanding of how problem characteristics influence the performance of the different search algorithms. Finally, from the insight gained from our study, we introduce a selection algorithm that helps us to select the appropriate search algorithm. This paper is structured as follows. We begin by reviewing state-of-the-art search algorithms and previous performance evaluation studies. Next, we describe the approach we adopted to evaluate the search algorithms that are subject to our study, define the problem domain and its characteristics, and the performance metrics. In section four, we present our experimental results. Section five introduces our proposed selection algorithm with an execution example. Finally, we derive our conclusion, the limitations of our study, and possible directions for future work. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Evaluating Heuristic Search Algorithms in Pathfinding: A Comprehensive Study on Performance Metrics 

This is paper is available on arxiv under CC 4.0 DEED license.
Authors:
(1) Dhruv Shah, UC Berkeley and he contributed equally;
(2)  Michael Equi, UC Berkeley and he contributed equally;
(3) Blazej Osinski, University of Warsaw;
(4) Fei Xia, Google DeepMind;
(5) Brian Ichter, Google DeepMind;
(6) Sergey Levine, UC Berkeley and Google DeepMind. Table of Links Abstract & Introduction
Related Work
Problem Formulation and Overview
LFG: Scoring Subgoals by Polling LLMs
LLM Heuristics for Goal-Directed Exploration
System Evaluation
Discussion and References
A. Implementation Details
B. Prompts B Prompts B.1 Positive Prompt B.2 Negative Prompt This is paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Dhruv Shah, UC Berkeley and he contributed equally; (2)  Michael Equi, UC Berkeley and he contributed equally; (3) Blazej Osinski, University of Warsaw; (4) Fei Xia, Google DeepMind; (5) Brian Ichter, Google DeepMind; (6) Sergey Levine, UC Berkeley and Google DeepMind. This is paper is available on arxiv under CC 4.0 DEED license. Authors: Authors: (1) Dhruv Shah, UC Berkeley and he contributed equally; (2)  Michael Equi, UC Berkeley and he contributed equally; (3) Blazej Osinski, University of Warsaw; (4) Fei Xia, Google DeepMind; (5) Brian Ichter, Google DeepMind; (6) Sergey Levine, UC Berkeley and Google DeepMind. Table of Links Abstract & Introduction Related Work Problem Formulation and Overview LFG: Scoring Subgoals by Polling LLMs LLM Heuristics for Goal-Directed Exploration System Evaluation Discussion and References A. Implementation Details B. Prompts Abstract & Introduction Abstract & Introduction Related Work Related Work Problem Formulation and Overview Problem Formulation and Overview LFG: Scoring Subgoals by Polling LLMs LFG: Scoring Subgoals by Polling LLMs LLM Heuristics for Goal-Directed Exploration LLM Heuristics for Goal-Directed Exploration System Evaluation System Evaluation Discussion and References Discussion and References A. Implementation Details A. Implementation Details B. Prompts B. Prompts B Prompts B.1 Positive Prompt B.2 Negative Prompt

Navigation with Large Language Models: Semantic Guesswork as a Heuristic for Planning: Prompts

This is paper is available on arxiv under CC 4.0 DEED license.
Authors:
(1) Dhruv Shah, UC Berkeley and he contributed equally;
(2)  Michael Equi, UC Berkeley and he contributed equally;
(3) Blazej Osinski, University of Warsaw;
(4) Fei Xia, Google DeepMind;
(5) Brian Ichter, Google DeepMind;
(6) Sergey Levine, UC Berkeley and Google DeepMind. Table of Links Abstract & Introduction
Related Work
Problem Formulation and Overview
LFG: Scoring Subgoals by Polling LLMs
LLM Heuristics for Goal-Directed Exploration
System Evaluation
Discussion and References
A. Implementation Details
B. Prompts 5 LLM Heuristics for Goal-Directed Exploration Given the LLM scoring pipeline outlined in the previous section, our key insight is that we can incorporate these scores in a search-based planning pipeline to heuristically guide the search process. We instantiate LFG using frontier-based exploration (FBE) and LLM scores generated via polling. FBE: This method maintains a “map” of the seen parts of the environment, which may be geometric [33] or topological [34], and a frontier separating it from the unexplored parts. By navigating to the nearest point of the frontier, the robot explores new areas of the environment until it finds the goal object or completes exploration without finding it. A standard FBE implementation is presented in Algorithm 2 inblack text. The robot maintains either a 2D metric map of its surroundings, or a topological map whose nodes are comprised of the robot’s visual observations and edges represent paths taken in the environment. Additionally, we also store semantic labels corresponding to objects detected in the robot’s observations, which are used to ground the observations in text. At a fixed re-planning rate, the high-level planner computes its frontier fi (Line 10), and picks the frontier point that is closest to the current location, i.e., maximizing the distance score (Line 16), and then navigates to this frontier (Line 21). At any point in this process, if the agent’s semantic detector detects an object of the same category as the query q, it navigates directly to this object and the trajectory ends. Incorporating LLM scores: Our method, LFG, extends FBE by using an additional search heuristic obtained by polling LLMs for semantic “scores”. The modifications to FBE are marked in purple in Algorithm 2. After enumerating the frontiers, LFG uses the semantic labels from a VLM [35] to ground subgoal images at each frontier fi (Line 11). These images are converted into textual strings, and form the subgoal candidates si that can be scored using Algorithm 1. We associate each frontier point fi with the nearest object cluster ci (Line 17), and compute LLM scores for each point as follows: where p is the current position of the agent, and wp, wn are hyperparameters (see Appendix A.1). We then choose the frontier with the highest score to be the next subgoal (Line 21), navigate to it using a local controller, and repeat the planning process. Algorithm 2 outlines the general recipe for integrating LLM scores as a planning heuristic. Please see Appendix A for specific instantiations of this system with geometric and topological maps, and more details about the referenced subroutines. This is paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Dhruv Shah, UC Berkeley and he contributed equally; (2)  Michael Equi, UC Berkeley and he contributed equally; (3) Blazej Osinski, University of Warsaw; (4) Fei Xia, Google DeepMind; (5) Brian Ichter, Google DeepMind; (6) Sergey Levine, UC Berkeley and Google DeepMind. This is paper is available on arxiv under CC 4.0 DEED license. Authors: Authors: (1) Dhruv Shah, UC Berkeley and he contributed equally; (2)  Michael Equi, UC Berkeley and he contributed equally; (3) Blazej Osinski, University of Warsaw; (4) Fei Xia, Google DeepMind; (5) Brian Ichter, Google DeepMind; (6) Sergey Levine, UC Berkeley and Google DeepMind. Table of Links Abstract & Introduction Related Work Problem Formulation and Overview LFG: Scoring Subgoals by Polling LLMs LLM Heuristics for Goal-Directed Exploration System Evaluation Discussion and References A. Implementation Details B. Prompts Abstract & Introduction Abstract & Introduction Related Work Related Work Problem Formulation and Overview Problem Formulation and Overview LFG: Scoring Subgoals by Polling LLMs LFG: Scoring Subgoals by Polling LLMs LLM Heuristics for Goal-Directed Exploration LLM Heuristics for Goal-Directed Exploration System Evaluation System Evaluation Discussion and References Discussion and References A. Implementation Details A. Implementation Details B. Prompts B. Prompts 5 LLM Heuristics for Goal-Directed Exploration Given the LLM scoring pipeline outlined in the previous section, our key insight is that we can incorporate these scores in a search-based planning pipeline to heuristically guide the search process. We instantiate LFG using frontier-based exploration (FBE) and LLM scores generated via polling. FBE: This method maintains a “map” of the seen parts of the environment, which may be geometric [33] or topological [34], and a frontier separating it from the unexplored parts. By navigating to the nearest point of the frontier, the robot explores new areas of the environment until it finds the goal object or completes exploration without finding it. A standard FBE implementation is presented in Algorithm 2 inblack text. The robot maintains either a 2D metric map of its surroundings, or a topological map whose nodes are comprised of the robot’s visual observations and edges represent paths taken in the environment. Additionally, we also store semantic labels corresponding to objects detected in the robot’s observations, which are used to ground the observations in text. FBE: At a fixed re-planning rate, the high-level planner computes its frontier f i (Line 10), and picks the frontier point that is closest to the current location, i.e., maximizing the distance score (Line 16), and then navigates to this frontier (Line 21). At any point in this process, if the agent’s semantic detector detects an object of the same category as the query q, it navigates directly to this object and the trajectory ends. i Incorporating LLM scores: Our method, LFG, extends FBE by using an additional search heuristic obtained by polling LLMs for semantic “scores”. The modifications to FBE are marked in purple in Algorithm 2. After enumerating the frontiers, LFG uses the semantic labels from a VLM [35] to ground subgoal images at each frontier f i (Line 11). These images are converted into textual strings, and form the subgoal candidates s i that can be scored using Algorithm 1. We associate each frontier point f i with the nearest object cluster ci (Line 17), and compute LLM scores for each point as follows: i i i where p is the current position of the agent, and w p , w n are hyperparameters (see Appendix A.1). We then choose the frontier with the highest score to be the next subgoal (Line 21), navigate to it using a local controller, and repeat the planning process. Algorithm 2 outlines the general recipe for integrating LLM scores as a planning heuristic. Please see Appendix A for specific instantiations of this system with geometric and topological maps, and more details about the referenced subroutines. p p n

Navigation with Large Language Models: LLM Heuristics for Goal-Directed Exploration

This is paper is available on arxiv under CC 4.0 DEED license.
Authors:
(1) Dhruv Shah, UC Berkeley and he contributed equally;
(2)  Michael Equi, UC Berkeley and he contributed equally;
(3) Blazej Osinski, University of Warsaw;
(4) Fei Xia, Google DeepMind;
(5) Brian Ichter, Google DeepMind;
(6) Sergey Levine, UC Berkeley and Google DeepMind. Table of Links Abstract & Introduction
Related Work
Problem Formulation and Overview
LFG: Scoring Subgoals by Polling LLMs
LLM Heuristics for Goal-Directed Exploration
System Evaluation
Discussion and References
A. Implementation Details
B. Prompts 2 Related Work Vision-based navigation: Navigation is conventionally approached as a largely geometric problem, where the aim is to map an environment and use that map to find a path to a goal location [1]. Learning-based approaches can exploit patterns in the training environments, particularly by learning vision-based navigation strategies through reinforcement or imitation [2–7]. Our work is also related to PONI [7], which uses a learned potential function to prioritize frontier points to explore; instead, we use a language model to rank these points. Notably, these methods do not benefit from prior semantic knowledge (e.g., from the web), and must rely entirely on patterns discovered from offline or online navigational data. Our aim is specifically to bring semantic knowledge into navigation, to enable robots to more effectively search for a goal in a new environment. Semantic knowledge-guided navigation: Prior knowledge about the semantics of indoor environments can provide significantly richer guidance. With the advent of effective open vocabulary vision models [8, 9], some works have recently explored incorporating their semantic knowledge into models for navigation and other robotic tasks with the express aim of improving performance at instruction following [10–14]. In general within robotics, such methods have either utilized pretrained vision-language representations [15–17], or used language models directly to make decisions [18–23]. Our aim is somewhat different: while we also focus on language-specified goals, we are primarily concerned with utilizing the semantics in pre-trained language models to help a robot figure out how to actually reach the goal, rather than utilizing the language models to more effectively interpret a language instruction. While language models can output reasonable substeps for temporally extended tasks in some settings [24, 25], there is contradictory evidence about their ability to actually plan [26], and because they are unaware of the observations and layout in a particular environment, their “plans” depend entirely on the context that is provided to them. In contrast to prior work, our approach does not rely on the language model producing a good plan, but merely a heuristic that can bias a dedicated planner to reach a goal more effectively. In this way, we use the language models more to produce suggestions rather than actual plans. LLM-guided navigation: Some works have sought to combine predictions from language models with either planning or probabilistic inference [14, 27], so as to not rely entirely on forward prediction from the language model to take actions. However, these methods are more aimed at filtering out infeasible decisions, for example by disallowing actions that a robot is incapable of performing, and still focus largely on being able to interpret and process instructions, rather than using the language model as a source of semantic hints. In contrast, by incorporating language model suggestions as heuristics into a heuristic planner, our approach can completely override the language model predictions if they are incorrect, while still making use of them if they point the way to the goal. Another branch of recent research [28–30] has taken a different approach to ground language models, by making it possible for them to read in image observations directly. While this represents a promising alternative approach to make language models more useful for embodied decision making, we believe it is largely orthogonal and complementary to our work: although vision-language models can produce more grounded inferences about the actions a robot should take, they are still limited only to guessing when placed in unfamiliar environments. Therefore, although we use ungrounded language-only models in our evaluation, we expect that our method could be combined with vision-language models easily, and would provide complementary benefits. This is paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Dhruv Shah, UC Berkeley and he contributed equally; (2)  Michael Equi, UC Berkeley and he contributed equally; (3) Blazej Osinski, University of Warsaw; (4) Fei Xia, Google DeepMind; (5) Brian Ichter, Google DeepMind; (6) Sergey Levine, UC Berkeley and Google DeepMind. This is paper is available on arxiv under CC 4.0 DEED license. Authors: Authors: (1) Dhruv Shah, UC Berkeley and he contributed equally; (2)  Michael Equi, UC Berkeley and he contributed equally; (3) Blazej Osinski, University of Warsaw; (4) Fei Xia, Google DeepMind; (5) Brian Ichter, Google DeepMind; (6) Sergey Levine, UC Berkeley and Google DeepMind. Table of Links Abstract & Introduction Related Work Problem Formulation and Overview LFG: Scoring Subgoals by Polling LLMs LLM Heuristics for Goal-Directed Exploration System Evaluation Discussion and References A. Implementation Details B. Prompts Abstract & Introduction Abstract & Introduction Related Work Related Work Problem Formulation and Overview Problem Formulation and Overview LFG: Scoring Subgoals by Polling LLMs LFG: Scoring Subgoals by Polling LLMs LLM Heuristics for Goal-Directed Exploration LLM Heuristics for Goal-Directed Exploration System Evaluation System Evaluation Discussion and References Discussion and References A. Implementation Details A. Implementation Details B. Prompts B. Prompts 2 Related Work Vision-based navigation: Navigation is conventionally approached as a largely geometric problem, where the aim is to map an environment and use that map to find a path to a goal location [1]. Learning-based approaches can exploit patterns in the training environments, particularly by learning vision-based navigation strategies through reinforcement or imitation [2–7]. Our work is also related to PONI [7], which uses a learned potential function to prioritize frontier points to explore; instead, we use a language model to rank these points. Notably, these methods do not benefit from prior semantic knowledge (e.g., from the web), and must rely entirely on patterns discovered from offline or online navigational data. Our aim is specifically to bring semantic knowledge into navigation, to enable robots to more effectively search for a goal in a new environment. Vision-based navigation: Semantic knowledge-guided navigation: Prior knowledge about the semantics of indoor environments can provide significantly richer guidance. With the advent of effective open vocabulary vision models [8, 9], some works have recently explored incorporating their semantic knowledge into models for navigation and other robotic tasks with the express aim of improving performance at instruction following [10–14]. In general within robotics, such methods have either utilized pretrained vision-language representations [15–17], or used language models directly to make decisions [18–23]. Our aim is somewhat different: while we also focus on language-specified goals, we are primarily concerned with utilizing the semantics in pre-trained language models to help a robot figure out how to actually reach the goal, rather than utilizing the language models to more effectively interpret a language instruction. While language models can output reasonable substeps for temporally extended tasks in some settings [24, 25], there is contradictory evidence about their ability to actually plan [26], and because they are unaware of the observations and layout in a particular environment, their “plans” depend entirely on the context that is provided to them. In contrast to prior work, our approach does not rely on the language model producing a good plan, but merely a heuristic that can bias a dedicated planner to reach a goal more effectively. In this way, we use the language models more to produce suggestions rather than actual plans. Semantic knowledge-guided navigation: LLM-guided navigation: Some works have sought to combine predictions from language models with either planning or probabilistic inference [14, 27], so as to not rely entirely on forward prediction from the language model to take actions. However, these methods are more aimed at filtering out infeasible decisions, for example by disallowing actions that a robot is incapable of performing, and still focus largely on being able to interpret and process instructions, rather than using the language model as a source of semantic hints. In contrast, by incorporating language model suggestions as heuristics into a heuristic planner, our approach can completely override the language model predictions if they are incorrect, while still making use of them if they point the way to the goal. LLM-guided navigation: Another branch of recent research [28–30] has taken a different approach to ground language models, by making it possible for them to read in image observations directly. While this represents a promising alternative approach to make language models more useful for embodied decision making, we believe it is largely orthogonal and complementary to our work: although vision-language models can produce more grounded inferences about the actions a robot should take, they are still limited only to guessing when placed in unfamiliar environments. Therefore, although we use ungrounded language-only models in our evaluation, we expect that our method could be combined with vision-language models easily, and would provide complementary benefits.

Navigation with Large Language Models: Semantic Guesswork as a Heuristic for Planning: Related Work

Authors:
(1) Renan F. F. da Silva, Institute of Computing, University of Campinas;
(2) Yulle G. F. Borges, Institute of Computing, University of Campinas;
(3) Rafael C. S. Schouery, Institute of Computing, University of Campinas. 9 Conclusion Our approaches were quite effective, enabling us to find solutions very close to the optimal solution, even in instances with many items. These results are partly due to the excellent quality of the solutions given by Two-by-Two, which efficiently handles color constraints. Another positive factors are our neighborhoods, which are efficient in quality and time complexity. Lastly, Gilmore and Gomory Formulation has a strong relaxation for the BPP, and this property may extend to CBPP. For a strong relaxation, the values for the optimal fractional and integer solutions are very close, so the patterns used by relaxation probably belong to integer solutions of high quality. Therefore, this is an excellent method to find a good set of patterns for the initial build of GRASP. Acknowledgements This project was supported by the S˜ao Paulo Research Foundation (FAPESP) grants #2015/11937-9 and #2020/06511-0; and the Brazilian National Council For Scientific and Technological Development (CNPq) grants #144257/2019-0, #311039/2020-0 and #425340/2016 3. Declarations Conflict of interest All authors declare that they have no conflicts of interest. References [1] Alsarhan H, Chia D, Christman A, et al (2016) A two-pass algorithm for unordered colored bin packing. Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School pp 1–10 [2] Balogh J, B´ek´esi J, Dosa G, et al (2013) Black and white bin packing. In: Erlebach T, Persiano G (eds) Approximation and Online Algorithms. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 131–144, https://doi.org/10.1007/978-3-642-38016-7_12 [3] Balogh J, B´ek´esi J, D´osa G, et al (2015) Offline black and white bin packing. Theoretical Computer Science 596:92–101. https://doi.org/10.1016/j.tcs.2015.06.045 [4] Belov G, Scheithauer G (2006) A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Operational Research 171(1):85–106. https://doi.org/10.1016/j.ejor.2004.08.036 [5] B¨ohm M, Sgall J, Vesel´y P (2015) Online colored bin packing. In: Bampis E, Svensson O (eds) Approximation and Online Algorithms. Springer International Publishing, Cham, pp 35–46, https://doi.org/10.1007/978-3-319-18263-6_4 [6] B¨ohm M, D´osa G, Epstein L, et al (2018) Colored bin packing: Online algorithms and lower bounds. Algorithmica 80(1):155–184. https://doi.org/10.1007/s00453-016-0248-2 [7] Borges Y, Schouery R (2020) Modelos pseudo polinomiais para o problema do empacotamento colorido. In: Anais do V Encontro de Teoria da Computa¸c˜ao, pp 37–40, https://doi.org/ 10.5753/etc.2020.11084, (In Portuguese) [8] Borges YGF, Schouery RCS, Miyazawa FK (2023) Mathematical models and exact algorithms for the colored bin packing problem. 2305.15291 [9] Brand˜ao F, Pedroso JP (2016) Bin packing and related problems: General arc-flow formulation with graph compression. Computers & Operations Research 69:56–67. https://doi.org/10. 1016/j.cor.2015.11.009 [10] Buljubaˇsi´c M, Vasquez M (2016) Consistent neighborhood search for one-dimensional bin packing and two-dimensional vector packing. Computers & Operations Research 76:12–21. https://doi.org/10.1016/j.cor.2016.06.009 [11] Carvalho JMVd (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research 86(0):629–659. https://doi.org/10. 1023/A:1018952112615 [12] Castelli M, Vanneschi L (2014) A hybrid harmony search algorithm with variable neighbourhood search for the bin-packing problem. 2014 Sixth World Congress on Nature and Biologically Inspired Computing (NaBIC 2014) pp 1–6. https://doi.org/10.1109/NaBIC.2014. 6921849 [13] Chen J, Han X, Bein W, et al (2015) Black and white bin packing revisited. In: Lu Z, Kim D, Wu W, et al (eds) Combinatorial Optimization and Applications. Springer International Publishing, Cham, pp 45–59, https://doi.org/10.1007/978-3-319-26626-8_4 [14] Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS Journal on Computing 32(1):101–119. https://doi.org/ 10.1287/ijoc.2018.0880 [15] Delorme M, Iori M, Martello S (2018) Bpplib: a library for bin packing and cutting stock problems. Optimization Letters 12(2):235–250. https://doi.org/10.1007/s11590-017-1192-z [16] Demˇsar J (2006) Statistical comparisons of classifiers over multiple data sets. The Journal of Machine learning research 7:1–30 [17] D´osa G, Epstein L (2014) Colorful bin packing. In: Ravi R, Gørtz IL (eds) Algorithm Theory – SWAT 2014. Springer International Publishing, Cham, pp 170–181, https://doi.org/10. 1007/978-3-319-08404-6_15 [18] Feo TA, Resende MG (1989) A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters 8(2):67–71. https://doi.org/https://doi.org/ 10.1016/0167-6377(89)90002-3 [19] Fleszar K, Hindi KS (2002) New heuristics for one-dimensional bin-packing. Computers & Operations Research 29(7):821–839. https://doi.org/10.1016/S0305-0548(00)00082-4 [20] Friedman M (1937) The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association 32(200):675–701. https: //doi.org/10.1080/01621459.1937.10503522 [21] Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Operations Research 9(6):849–859. https://doi.org/10.1287/opre.29.6.1092 [22] Gonz´alez-San-Mart´ın J, Cruz-Reyes L, G´omez-Santill´an C, et al (2023) Comparative Study of Heuristics for the One-Dimensional Bin Packing Problem, Springer Nature Switzerland, Cham, pp 293–305. https://doi.org/10.1007/978-3-031-28999-6_19 [23] Gupta JND, Ho JC (1999) A new heuristic algorithm for the one-dimensional binpacking problem. Production Planning & Control 10(6):598–603. https://doi.org/10.1080/ 095372899232894 [24] Iman RL, Davenport JM (1980) Approximations of the critical region of the fbietkan statistic. Communications in Statistics - Theory and Methods 9(6):571–595. https://doi.org/10. 1080/03610928008827904 [25] Karp RM (1972) Reducibility among Combinatorial Problems, Springer US, Boston, MA, pp 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9 [26] de Lima VL, Iori M, Miyazawa FK (2022) Exact solution of network flow models with strong relaxations. Mathematical Programming pp 1–34. https://doi.org/10.1007/ s10107-022-01785-9 [27] Loh KH, Golden B, Wasil E (2008) Solving the one-dimensional bin packing problem with a weight annealing heuristic. Computers & Operations Research 35(7):2283–2291. https:// doi.org/10.1016/j.cor.2006.10.021 [28] Mladenovi´c N, Hansen P (1997) Variable neighborhood search. Computers & Operations Research 24(11):1097–1100. https://doi.org/10.1016/S0305-0548(97)00031-2 [29] Nemenyi PB (1963) Distribution-free multiple comparisons. PhD thesis, Princeton University [30] Pessoa A, Sadykov R, Uchoa E, et al (2020) A generic exact solver for vehicle routing and related problems. Mathematical Programming 183(1):483–523. https://doi.org/10.1007/ s10107-020-01523-z [31] Vance PH (1998) Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optimization and Applications 9(3):211–228. https://doi.org/10.1023/A: 1018346107246 [32] Wei L, Luo Z, Baldacci R, et al (2020) A new branch-and-price-and-cut algorithm for onedimensional bin-packing problems. INFORMS Journal on Computing 32(2):428–443. https://doi.org/10.1287/ijoc.2018.0867 This paper is available on arxiv under CC 4.0 license. Authors: (1) Renan F. F. da Silva, Institute of Computing, University of Campinas; (2) Yulle G. F. Borges, Institute of Computing, University of Campinas; (3) Rafael C. S. Schouery, Institute of Computing, University of Campinas. Authors: (1) Renan F. F. da Silva, Institute of Computing, University of Campinas; (2) Yulle G. F. Borges, Institute of Computing, University of Campinas; (3) Rafael C. S. Schouery, Institute of Computing, University of Campinas. 9 Conclusion Our approaches were quite effective, enabling us to find solutions very close to the optimal solution, even in instances with many items. These results are partly due to the excellent quality of the solutions given by Two-by-Two, which efficiently handles color constraints. Another positive factors are our neighborhoods, which are efficient in quality and time complexity. Lastly, Gilmore and Gomory Formulation has a strong relaxation for the BPP, and this property may extend to CBPP. For a strong relaxation, the values for the optimal fractional and integer solutions are very close, so the patterns used by relaxation probably belong to integer solutions of high quality. Therefore, this is an excellent method to find a good set of patterns for the initial build of GRASP. Acknowledgements This project was supported by the S˜ao Paulo Research Foundation (FAPESP) grants #2015/11937-9 and #2020/06511-0; and the Brazilian National Council For Scientific and Technological Development (CNPq) grants #144257/2019-0, #311039/2020-0 and #425340/2016 3. Acknowledgements Declarations Conflict of interest All authors declare that they have no conflicts of interest. Conflict of interest References [1] Alsarhan H, Chia D, Christman A, et al (2016) A two-pass algorithm for unordered colored bin packing. Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School pp 1–10 [2] Balogh J, B´ek´esi J, Dosa G, et al (2013) Black and white bin packing. In: Erlebach T, Persiano G (eds) Approximation and Online Algorithms. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 131–144, https://doi.org/10.1007/978-3-642-38016-7_12 [3] Balogh J, B´ek´esi J, D´osa G, et al (2015) Offline black and white bin packing. Theoretical Computer Science 596:92–101. https://doi.org/10.1016/j.tcs.2015.06.045 [4] Belov G, Scheithauer G (2006) A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Operational Research 171(1):85–106. https://doi.org/10.1016/j.ejor.2004.08.036 [5] B¨ohm M, Sgall J, Vesel´y P (2015) Online colored bin packing. In: Bampis E, Svensson O (eds) Approximation and Online Algorithms. Springer International Publishing, Cham, pp 35–46, https://doi.org/10.1007/978-3-319-18263-6_4 [6] B¨ohm M, D´osa G, Epstein L, et al (2018) Colored bin packing: Online algorithms and lower bounds. Algorithmica 80(1):155–184. https://doi.org/10.1007/s00453-016-0248-2 [7] Borges Y, Schouery R (2020) Modelos pseudo polinomiais para o problema do empacotamento colorido. In: Anais do V Encontro de Teoria da Computa¸c˜ao, pp 37–40, https://doi.org/ 10.5753/etc.2020.11084, (In Portuguese) [8] Borges YGF, Schouery RCS, Miyazawa FK (2023) Mathematical models and exact algorithms for the colored bin packing problem. 2305.15291 [9] Brand˜ao F, Pedroso JP (2016) Bin packing and related problems: General arc-flow formulation with graph compression. Computers & Operations Research 69:56–67. https://doi.org/10. 1016/j.cor.2015.11.009 [10] Buljubaˇsi´c M, Vasquez M (2016) Consistent neighborhood search for one-dimensional bin packing and two-dimensional vector packing. Computers & Operations Research 76:12–21. https://doi.org/10.1016/j.cor.2016.06.009 [11] Carvalho JMVd (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research 86(0):629–659. https://doi.org/10. 1023/A:1018952112615 [12] Castelli M, Vanneschi L (2014) A hybrid harmony search algorithm with variable neighbourhood search for the bin-packing problem. 2014 Sixth World Congress on Nature and Biologically Inspired Computing (NaBIC 2014) pp 1–6. https://doi.org/10.1109/NaBIC.2014. 6921849 [13] Chen J, Han X, Bein W, et al (2015) Black and white bin packing revisited. In: Lu Z, Kim D, Wu W, et al (eds) Combinatorial Optimization and Applications. Springer International Publishing, Cham, pp 45–59, https://doi.org/10.1007/978-3-319-26626-8_4 [14] Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS Journal on Computing 32(1):101–119. https://doi.org/ 10.1287/ijoc.2018.0880 [15] Delorme M, Iori M, Martello S (2018) Bpplib: a library for bin packing and cutting stock problems. Optimization Letters 12(2):235–250. https://doi.org/10.1007/s11590-017-1192-z [16] Demˇsar J (2006) Statistical comparisons of classifiers over multiple data sets. The Journal of Machine learning research 7:1–30 [17] D´osa G, Epstein L (2014) Colorful bin packing. In: Ravi R, Gørtz IL (eds) Algorithm Theory – SWAT 2014. Springer International Publishing, Cham, pp 170–181, https://doi.org/10. 1007/978-3-319-08404-6_15 [18] Feo TA, Resende MG (1989) A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters 8(2):67–71. https://doi.org/https://doi.org/ 10.1016/0167-6377(89)90002-3 [19] Fleszar K, Hindi KS (2002) New heuristics for one-dimensional bin-packing. Computers & Operations Research 29(7):821–839. https://doi.org/10.1016/S0305-0548(00)00082-4 [20] Friedman M (1937) The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association 32(200):675–701. https: //doi.org/10.1080/01621459.1937.10503522 [21] Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Operations Research 9(6):849–859. https://doi.org/10.1287/opre.29.6.1092 [22] Gonz´alez-San-Mart´ın J, Cruz-Reyes L, G´omez-Santill´an C, et al (2023) Comparative Study of Heuristics for the One-Dimensional Bin Packing Problem, Springer Nature Switzerland, Cham, pp 293–305. https://doi.org/10.1007/978-3-031-28999-6_19 [23] Gupta JND, Ho JC (1999) A new heuristic algorithm for the one-dimensional binpacking problem. Production Planning & Control 10(6):598–603. https://doi.org/10.1080/ 095372899232894 [24] Iman RL, Davenport JM (1980) Approximations of the critical region of the fbietkan statistic. Communications in Statistics - Theory and Methods 9(6):571–595. https://doi.org/10. 1080/03610928008827904 [25] Karp RM (1972) Reducibility among Combinatorial Problems, Springer US, Boston, MA, pp 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9 [26] de Lima VL, Iori M, Miyazawa FK (2022) Exact solution of network flow models with strong relaxations. Mathematical Programming pp 1–34. https://doi.org/10.1007/ s10107-022-01785-9 [27] Loh KH, Golden B, Wasil E (2008) Solving the one-dimensional bin packing problem with a weight annealing heuristic. Computers & Operations Research 35(7):2283–2291. https:// doi.org/10.1016/j.cor.2006.10.021 [28] Mladenovi´c N, Hansen P (1997) Variable neighborhood search. Computers & Operations Research 24(11):1097–1100. https://doi.org/10.1016/S0305-0548(97)00031-2 [29] Nemenyi PB (1963) Distribution-free multiple comparisons. PhD thesis, Princeton University [30] Pessoa A, Sadykov R, Uchoa E, et al (2020) A generic exact solver for vehicle routing and related problems. Mathematical Programming 183(1):483–523. https://doi.org/10.1007/ s10107-020-01523-z [31] Vance PH (1998) Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optimization and Applications 9(3):211–228. https://doi.org/10.1023/A: 1018346107246 [32] Wei L, Luo Z, Baldacci R, et al (2020) A new branch-and-price-and-cut algorithm for onedimensional bin-packing problems. INFORMS Journal on Computing 32(2):428–443. https://doi.org/10.1287/ijoc.2018.0867 This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Stories, News & Mentions about HEYRISTIC

Heyristic’s Stories on HackerNoon