Weighted Randomized Anytime Planning in Pyhop. Ferrer, G. In Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024), pages 54–58, 2024. ![Weighted Randomized Anytime Planning in Pyhop [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper abstract bibtex 5 downloads Since they produce plans whose quality increases with time, anytime planners are very useful for domains such as robotics and video games. Planners using the SHOP algorithm can op- erate as anytime planners by retaining the result of the first depth-first search path that reaches the goal, then returning the results of subsequent searches if they improve upon it. However, backtracking to the most recent alternative may not be the best approach for quickly finding a low-cost plan. In this paper, we replace backtracking depth-first search with a randomized algorithm in the Pyhop implementation of SHOP. Whenever there are multiple options, the planner se- lects a random operator or method. For every selected option, it records the cost of every plan that includes that option. It uses these cost statistics to make the selection of options that lead to lower-cost plans more probable. We evaluated the resulting HTN planner on three domains - the Traveling Salesperson Problem, the Pickup and Delivery Problem, and the Satellite Problem. Our experiments show that the weighted-selection approach outperforms both depth-first search and unweighted randomized selection.
@InProceedings{Ferrer2024AnytimePlanning,
author = {Gabriel Ferrer},
booktitle = {Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)},
title = {Weighted Randomized Anytime Planning in Pyhop},
year = {2024},
abstract = {Since they produce plans whose quality increases with time, anytime planners are very useful for domains such as robotics and video games. Planners using the SHOP algorithm can op- erate as anytime planners by retaining the result of the first depth-first search path that reaches the goal, then returning the results of subsequent searches if they improve upon it. However, backtracking to the most recent alternative may not be the best approach for quickly finding a low-cost plan. In this paper, we replace backtracking depth-first search with a randomized algorithm in the Pyhop implementation of SHOP. Whenever there are multiple options, the planner se- lects a random operator or method. For every selected option, it records the cost of every plan that includes that option. It uses these cost statistics to make the selection of options that lead to lower-cost plans more probable. We evaluated the resulting HTN planner on three domains - the Traveling Salesperson Problem, the Pickup and Delivery Problem, and the Satellite Problem. Our experiments show that the weighted-selection approach outperforms both depth-first search and unweighted randomized selection.},
url_paper = {https://icaps24.icaps-conference.org/program/workshops/hplan/HPlan2024_paper_5.pdf},
pages = {54--58}
}
% submission 6
Downloads: 5
{"_id":"pRbE9WeDJ78Pfp483","bibbaseid":"ferrer-weightedrandomizedanytimeplanninginpyhop-2024","author_short":["Ferrer, G."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Gabriel"],"propositions":[],"lastnames":["Ferrer"],"suffixes":[]}],"booktitle":"Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)","title":"Weighted Randomized Anytime Planning in Pyhop","year":"2024","abstract":"Since they produce plans whose quality increases with time, anytime planners are very useful for domains such as robotics and video games. Planners using the SHOP algorithm can op- erate as anytime planners by retaining the result of the first depth-first search path that reaches the goal, then returning the results of subsequent searches if they improve upon it. However, backtracking to the most recent alternative may not be the best approach for quickly finding a low-cost plan. In this paper, we replace backtracking depth-first search with a randomized algorithm in the Pyhop implementation of SHOP. Whenever there are multiple options, the planner se- lects a random operator or method. For every selected option, it records the cost of every plan that includes that option. It uses these cost statistics to make the selection of options that lead to lower-cost plans more probable. We evaluated the resulting HTN planner on three domains - the Traveling Salesperson Problem, the Pickup and Delivery Problem, and the Satellite Problem. Our experiments show that the weighted-selection approach outperforms both depth-first search and unweighted randomized selection.","url_paper":"https://icaps24.icaps-conference.org/program/workshops/hplan/HPlan2024_paper_5.pdf","pages":"54–58","bibtex":"@InProceedings{Ferrer2024AnytimePlanning,\n author = {Gabriel Ferrer},\n booktitle = {Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)},\n title = {Weighted Randomized Anytime Planning in Pyhop},\n year = {2024},\n abstract = {Since they produce plans whose quality increases with time, anytime planners are very useful for domains such as robotics and video games. Planners using the SHOP algorithm can op- erate as anytime planners by retaining the result of the first depth-first search path that reaches the goal, then returning the results of subsequent searches if they improve upon it. However, backtracking to the most recent alternative may not be the best approach for quickly finding a low-cost plan. In this paper, we replace backtracking depth-first search with a randomized algorithm in the Pyhop implementation of SHOP. Whenever there are multiple options, the planner se- lects a random operator or method. For every selected option, it records the cost of every plan that includes that option. It uses these cost statistics to make the selection of options that lead to lower-cost plans more probable. We evaluated the resulting HTN planner on three domains - the Traveling Salesperson Problem, the Pickup and Delivery Problem, and the Satellite Problem. Our experiments show that the weighted-selection approach outperforms both depth-first search and unweighted randomized selection.},\n url_paper = {https://icaps24.icaps-conference.org/program/workshops/hplan/HPlan2024_paper_5.pdf},\n pages = {54--58}\n}\n\n% submission 6\n","author_short":["Ferrer, G."],"key":"Ferrer2024AnytimePlanning","id":"Ferrer2024AnytimePlanning","bibbaseid":"ferrer-weightedrandomizedanytimeplanninginpyhop-2024","role":"author","urls":{" paper":"https://icaps24.icaps-conference.org/program/workshops/hplan/HPlan2024_paper_5.pdf"},"metadata":{"authorlinks":{}},"downloads":5},"bibtype":"inproceedings","biburl":"https://icaps24.icaps-conference.org/program/workshops/hplan/hplan.bib","dataSources":["obo5j8TzJxMFi59JG"],"keywords":[],"search_terms":["weighted","randomized","anytime","planning","pyhop","ferrer"],"title":"Weighted Randomized Anytime Planning in Pyhop","year":2024,"downloads":5}