Publications
2018 |
Baier, Hendrik; Cowling, Peter I Evolutionary MCTS with Flexible Search Horizon Inproceedings Proceedings of the AAAI Artificial Intelligence and Interactive Digital Entertainment Conference 2018 (AIIDE'18), Canada, AAAI, 2018. Abstract | BibTeX | Tags: agents, ai, decisions, games, heuristics, search | Links: @inproceedings{baier2018evolutionary, title = {Evolutionary MCTS with Flexible Search Horizon}, author = {Hendrik Baier and Peter I. Cowling}, url = {http://www.petercowling.com/wp-content/uploads/2018/09/Evolutionary-MCTS-with-Flexible-Search-Horizon.pdf}, year = {2018}, date = {2018-11-07}, booktitle = {Proceedings of the AAAI Artificial Intelligence and Interactive Digital Entertainment Conference 2018 (AIIDE'18), Canada}, journal = {In Proceedings of Artificial Intelligence and Interactive Digital Entertainment (AIIDE'18), Canada}, publisher = {AAAI}, abstract = {In turn-based multi-action adversarial games each player turn consists of several atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, which is currently best played by Evolutionary MCTS (EMCTS) – searching a tree with nodes representing action sequences as genomes, and edges representing mutations of those genomes. However, regular EMCTS is unable to search beyond the current player’s turn, leading to strategic short-sightedness. In this paper, we extend EMCTS to search to any given search depth beyond the current turn, using simple models of its own and the opponent’s behavior. Experiments on the game Hero Academy show that this Flexible-Horizon EMCTS (FH-EMCTS) convincingly out- performs several baselines including regular EMCTS, Online Evolutionary Planning (OEP), and vanilla MCTS, at all tested numbers of atomic actions per turn. Additionally, the separate contributions of the behavior models and the flexible search horizon are analyzed.}, keywords = {agents, ai, decisions, games, heuristics, search}, pubstate = {published}, tppubtype = {inproceedings} } In turn-based multi-action adversarial games each player turn consists of several atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, which is currently best played by Evolutionary MCTS (EMCTS) – searching a tree with nodes representing action sequences as genomes, and edges representing mutations of those genomes. However, regular EMCTS is unable to search beyond the current player’s turn, leading to strategic short-sightedness. In this paper, we extend EMCTS to search to any given search depth beyond the current turn, using simple models of its own and the opponent’s behavior. Experiments on the game Hero Academy show that this Flexible-Horizon EMCTS (FH-EMCTS) convincingly out- performs several baselines including regular EMCTS, Online Evolutionary Planning (OEP), and vanilla MCTS, at all tested numbers of atomic actions per turn. Additionally, the separate contributions of the behavior models and the flexible search horizon are analyzed. |
Baier, Hendrik; Cowling, Peter I Evolutionary MCTS for Multi-Action Adversarial Games Inproceedings Proceedings of the IEEE Conference on Computational Intelligence in Games, IEEE, 2018. Abstract | BibTeX | Tags: agents, decisions, heuristics, search | Links: @inproceedings{baier2018evolutionary_cig, title = {Evolutionary MCTS for Multi-Action Adversarial Games}, author = {Hendrik Baier and Peter I. Cowling}, url = {http://www.petercowling.com/wp-content/uploads/2019/02/baier2018evolutionary_cig.pdf}, year = {2018}, date = {2018-09-01}, booktitle = {Proceedings of the IEEE Conference on Computational Intelligence in Games}, publisher = {IEEE}, abstract = {Turn-based multi-action adversarial games are games in which each player turn consists of a sequence of atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, for which the current state of the art is Online Evolutionary Planning (OEP) – an evolutionary algorithm (EA) that treats atomic actions as genes, and complete action sequences as genomes. In this paper, we introduce Evolutionary Monte Carlo Tree Search (EMCTS) to tackle this challenge, combining the tree search of MCTS with the sequence-based optimization of EAs. Experiments on the game Hero Academy show that EMCTS convincingly outperforms several baselines including OEP and an improved variant of OEP introduced in this paper, at different time settings and numbers of atomic actions per turn. EMCTS also scales better than any existing algorithm with the complexity of the problem.}, keywords = {agents, decisions, heuristics, search}, pubstate = {published}, tppubtype = {inproceedings} } Turn-based multi-action adversarial games are games in which each player turn consists of a sequence of atomic actions, resulting in an extremely high branching factor. Many strategy board, card, and video games fall into this category, for which the current state of the art is Online Evolutionary Planning (OEP) – an evolutionary algorithm (EA) that treats atomic actions as genes, and complete action sequences as genomes. In this paper, we introduce Evolutionary Monte Carlo Tree Search (EMCTS) to tackle this challenge, combining the tree search of MCTS with the sequence-based optimization of EAs. Experiments on the game Hero Academy show that EMCTS convincingly outperforms several baselines including OEP and an improved variant of OEP introduced in this paper, at different time settings and numbers of atomic actions per turn. EMCTS also scales better than any existing algorithm with the complexity of the problem. |
2017 |
Chen, Yujie; Cowling, Peter; Polack, Fiona; Remde, Stephen; Mourdjis, Philip Dynamic optimisation of preventative and corrective maintenance schedules for a large scale urban drainage system Journal Article European journal of operational research, 257 (2), pp. 494–510, 2017. Abstract | BibTeX | Tags: ai, gaist, heuristics, hyperheuristics, optimisation, scheduling | Links: @article{chen2017dynamic, title = {Dynamic optimisation of preventative and corrective maintenance schedules for a large scale urban drainage system}, author = {Yujie Chen and Peter Cowling and Fiona Polack and Stephen Remde and Philip Mourdjis}, url = {http://www.petercowling.com/wp-content/uploads/2018/08/chen2017dynamic.pdf}, doi = {10.1016/j.ejor.2016.07.027}, year = {2017}, date = {2017-01-01}, journal = {European journal of operational research}, volume = {257}, number = {2}, pages = {494--510}, publisher = {North-Holland}, abstract = {Gully pots or storm drains are located at the side of roads to provide drainage for surface water. We consider gully pot maintenance as a risk-driven maintenance problem. We explore policies for preventative and corrective maintenance actions, and build optimised routes for maintenance vehicles. Our solutions take the risk impact of gully pot failure and its failure behaviour into account, in the presence of factors such as location, season and current status. The aim is to determine a maintenance policy that can automatically adjust its scheduling strategy in line with changes in the local environment, to minimise the surface flooding risk due to clogged gully pots. We introduce a rolling planning strategy, solved by a hyper-heuristic method. Results show the behaviour and strength of the automated adjustment in a range of real-world scenarios.}, keywords = {ai, gaist, heuristics, hyperheuristics, optimisation, scheduling}, pubstate = {published}, tppubtype = {article} } Gully pots or storm drains are located at the side of roads to provide drainage for surface water. We consider gully pot maintenance as a risk-driven maintenance problem. We explore policies for preventative and corrective maintenance actions, and build optimised routes for maintenance vehicles. Our solutions take the risk impact of gully pot failure and its failure behaviour into account, in the presence of factors such as location, season and current status. The aim is to determine a maintenance policy that can automatically adjust its scheduling strategy in line with changes in the local environment, to minimise the surface flooding risk due to clogged gully pots. We introduce a rolling planning strategy, solved by a hyper-heuristic method. Results show the behaviour and strength of the automated adjustment in a range of real-world scenarios. |