Planning, monitoring and replanning techniques for handling abnormity in HTN-based planning and execution

doi:10.23919/JSEE.2024.000090

Journal of Systems Engineering and Electronics ›› 2024, Vol. 35 ›› Issue (5): 1264-1275.doi: 10.23919/JSEE.2024.000090

收稿日期:2022-04-01 出版日期:2024-10-18 发布日期:2024-11-06

Planning, monitoring and replanning techniques for handling abnormity in HTN-based planning and execution

Kai KANG¹(), Kai CHENG¹(), Tianhao SHAO¹^,*(), Hongjun ZHANG¹(), Ke ZHANG²()

¹ Command and Control Engineering College, Army Engineering University of PLA, Nanjing 210000, China
² The 63rd Research Institute of National University of Defense Technology, Nanjing 210000, China

Received:2022-04-01 Online:2024-10-18 Published:2024-11-06
Contact: Tianhao SHAO E-mail:13913835075@139.com;chengkai911@126.com;296749641@qq.com;jsnjzhj_lgdx@163.com;2387303531@qq.com
About author:
KANG Kai was born in 1986. He received his M.S. degree from the PLA University of Science and Technology. He is pursuing his Ph.D. drgree at the Army Engineering University of PLA. His main research interests include data mining, task planning and intelligent decision making.E-mail: 13913835075@139.com

CHENG Kai was born in 1983. He received his Ph.D. degree from the PLA University of Science and Technology. He is currently an associate professor at the Army Engineering University of PLA. His main research interests include data mining, task planning and intelligent decision making.E-mail: chengkai911@126.com

SHAO Tianhao was born in 1996. He received his M.S. degree from the Army Engineering University of PLA. He is pursuing his Ph.D. drgree at the Army Engineering University of PLA. His main research interests include data mining, task planning and intelligent decision making.E-mail: 296749641@qq.com

ZHANG Hongjun was born in 1963. He received his Ph. D. degree from the Nanjing University of Science and Technology. He is currently a professor at the Army Engineering University of PLA. His main research fields are data engineering, effectiveness evaluation and intelligent decision making.E-mail: jsnjzhj_lgdx@163.com

ZHANG Ke was born in 1996. She received her Ph.D. degree from the Army Engineering University of PLA. She is currently an assistant researcher at the 63rd Research Institute of National University of Defense Technology. Her main research interests include data mining, task planning and intelligent decision making. E-mail: 2387303531@qq.com
First author contact:
Co-first author
Supported by:
This work was supported by the National Natural Science Foundation of China (61806221).

摘要/Abstract

Abstract:

A framework that integrates planning, monitoring and replanning techniques is proposed. It can devise the best solution based on the current state according to specific objectives and properly deal with the influence of abnormity on the plan execution. The framework consists of three parts: the hierarchical task network (HTN) planner based on Monte Carlo tree search (MCTS), hybrid plan monitoring based on forward and backward and norm-based replanning method selection. The HTN planner based on MCTS selects the optimal method for HTN compound task through pre-exploration. Based on specific objectives, it can identify the best solution to the current problem. The hybrid plan monitoring has the capability to detect the influence of abnormity on the effect of an executed action and the premise of an unexecuted action, thus trigger the replanning. The norm-based replanning selection method can measure the difference between the expected state and the actual state, and then select the best replanning algorithm. The experimental results reveal that our method can effectively deal with the influence of abnormity on the implementation of the plan and achieve the target task in an optimal way.

Key words: hierarchical task network, Monte carlo tree search (MCTS), planning, execution, abnormity

. [J]. Journal of Systems Engineering and Electronics, 2024, 35(5): 1264-1275.

Kai KANG, Kai CHENG, Tianhao SHAO, Hongjun ZHANG, Ke ZHANG. Planning, monitoring and replanning techniques for handling abnormity in HTN-based planning and execution[J]. Journal of Systems Engineering and Electronics, 2024, 35(5): 1264-1275.

图/表 9

参考文献 38

1	WANG H W, QI C. Hierarchical task network planning based emergency response decision making theory and method. Beijing: Science Press, 2015.
2	GENG S T, CAO X W, LI X N, et al Joint operations electronic countermeasures task decomposition method based on extended hierarchical task network. Journal of Academy of Armored Force Engineering, 2018, 32 (5): 8- 13.
3	NIE J F. Operational task decomposition method based on extended HTN planning. Proc. of the 8th International Conference on Dependable Systems and Their Applications, 2021: 626−630.
4	MILOT A, CHAUVEAU E, LACROIX S, et al. Market-based multi-robot coordination with HTN planning. Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2021: 2606−2612.
5	LIN T X, HOU M X, EDWARDS C R, et al. Bounded cost HTN planning for marine autonomy. Proc. of the Global Oceans, 2020.
6	WANG Z, WANG S C, LI M L, et al Research on application of HTN planning in emergency logistics program formulation. Safety and Environmental Engineering, 2017, 24 (5): 15- 20.
7	SUN L, ZHU A S, LI B, et al. HTN guided adversarial planning for RTS games. Proc. of the IEEE International Conference on Mechatronics and Automation, 2020: 1326−1331.
8	SAANCHEZ-GARZON I, FDEZ-OLIVARES J, CASTILLO L. A repair-replanning strategy for HTN-based therapy planning systems. https://decsai.ugr.es/~faro/LinkedDocuments/FinalSubmission_DC_AIME11.pdf. 2011.
9	NAU D, AU T C, ILGHAMI O, et al Applications of SHOP and SHOP2. IEEE Intelligent Systems, 2005, 20 (2): 34- 41. doi: 10.1109/MIS.2005.20
10	WAISBROT N, KUTER U, KONIK T. Combining heuristic search with hierarchical task-network planning: a preliminary report. Proc. of the International Florida Artificial Intelligence Research Society Conference, 2008: 557−578.
11	CHENG K, WU L, YU X H, et al Improving hierarchical task network planning performance by the use of domain-independent heuristic search. Knowledge-Based Systems, 2018, 142, 117- 126. doi: 10.1016/j.knosys.2017.11.031
12	LI M L, WANG H W, QI C A novel HTN planning approach for handling disruption during plan execution. Applied Intelligence, 2016, 46 (4): 1- 10.
13	HOLLER D, BERCHER P, BEHNKE G, et al. On guiding search in HTN planning with classical planning heuristics. Proc. of the International Joint Conference on Artificial Intelligence, 2019: 6171−6175.
14	BEHNKE G, HOLLER D, BIUNDO S. Finding optimal solutions in HTN planning−a SAT-based approach. Proc. of the 28th International Joint Conference on Artificial Intelligence, 2019: 5500−5508.
15	PATRA S, GHALLAB M, NAU D, et al APE: an acting and planning engine. Cognitive Systems, 2019, 7, 175- 194.
16	PATRA S, MASON J, KUMAR A, et al. Integrating acting, planning, and learning in hierarchical operational models. Proc. of the International Conference on Automated Planning and Scheduling, 2020: 478−487.
17	WICHLACZ J, HOLLER D, TORRALBA A, et al. Applying Monte-Carlo tree search in HTN planning. Proc. of the 13th International Symposium on Combinatorial Search, 2020: 82−90.
18	GOLDMAN R P. Solving POMDPs online through HTN planning and Monte Carlo tree search. Proc. of the 4th ICAPS Workshop on Hierarchical Planning, 2021: 57−61.
19	MYERS K L CPEF: a continuous planning and execution framework. AI Magazine, 1999, 20 (4): 63- 69.
20	KROGT R V D, WEERDT M D. Plan repair as an extension of planning. Proc. of the International Conference on Automated Planning and Scheduling, 2005: 161−170.
21	OUALI L O, RICH C, SABOURET N. Plan recovery in reactive HTNs using symbolic planning. Proc. of the International Conference on Artificial General Intelligence, 2015: 320−330.
22	AYAN N F, KUTER U, YAMAN F, et al. HOTRiDE: hierarchical ordered task replanning in dynamic environments. Proc. of the International Conference on Automated Planning and Scheduling, 2007: 31−36.
23	WARFIELD I, HOGG C, LEE-URBAN S, et al. Adaptation of hierarchical task network plans. Proc. of the International Florida Artificial Intelligence Research Society Conference, 2007: 429−434.
24	BECHON P, BARBIER M, LESIRE C, et al. Using hybrid planning for plan reparation. Proc. of the European Conference on Mobile Robots, 2015: 1−6.
25	HOLLER D, BERCHER P, BEHNKE G, et al. HTN plan repair using unmodified planning systems. Proc. of the International Conference on Automated Planning and Scheduling, 2018: 26−30.
26	SHIVASHANKAR V. Hierarchical goal networks: formalisms and algorithms for planning and acting. Maryland: University of Maryland, College Park, 2015.
27	REIFSNYDER N, MUNOZ-AVILA H. Computing numeric expectations for cognitive agents. Proc. of the Conference on Advances in Cognitive Systems, 2020.
28	REIFSNYDER N, MUNOZ-AVILA H. Policy regression for monitoring execution in goal reasoning systems. Proc. of the Conference on Advances in Cognitive Systems, 2020.
29	YANG Z Z, ONTANON S. Guiding Monte Carlo tree search by scripts in real-time strategy games. Proc. of the 15th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2019: 100−106.
30	SILVER D, HUANG A, MADDISON C J, et al Mastering the game of go with deep neural networks and tree search. Nature, 2016, 529 (7587): 484- 489. doi: 10.1038/nature16961
31	TANG Z T, ZHU Y H, ZHAO D B. Enhanced rolling horizon evolution algorithm with opponent model learning. IEEE Trans. on Games, 2020. DOI: 10.1109/tg.2020.3022698.
32	SWIECHOWSKI M, SAWICKI B, MANDZIUK J. Monte Carlo tree search: a review on recent modifications and applications. Artifical Intelligence Review, 2023, 56: 2497−2562.
33	BROWNE C B, POWLEY E, WHITEHOUSE D A survey of Monte Carlo tree search methods. IEEE Trans. on Computational Intelligence and AI in Games, 2012, 4 (1): 1- 43. doi: 10.1109/TCIAIG.2012.2186810
34	SHAO T H, ZHANG H J, CHENG K, et al The hierarchical task network planning method based on Monte Carlo tree search. Knowledge-Based Systems, 2021, 225 (4): 107067.
35	GOLUB G H, LOAN C F V. Matrix computations. Maryland: The Johns Hopkins University Press, 2013.
36	SHAO T H, ZHANG H J, CHENG K, et al Review of replanning in hierarchical task network. Systems Engineering and Electronics, 2020, 42 (12): 2833- 2846.
37	VIAZOVSKYI M, CERTICKY M. StarAlgo: a squad movement planning library for StarCraft using Monte Carlo tree search and Negamax. https://doi.org/10.48550/arXiv.1812.11371.
38	KARTAL B, HERNANDEZ-LEAL P, TAYLOR M E. Action guidance with MCTS for deep reinforcement learning. Proc. of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2019: 153−159.

Initial	Target	$ S\_h $	$ S\_m $	$ P\_h $/%	$ P\_m $/%
1,0	2,6	8.78	8.05	72.83	98.94
3,3	2,1	3.93	3.46	87.63	97.98
4,5	5,5	1.67	1.44	96.97	98.99
5,0	3,2	4.51	4.36	86.49	100.00
6,0	1,5	11.28	10.23	60.49	96.84
1,2	2,6	7.02	5.47	69.32	100.00
2,5	6,0	10.32	9.28	68.49	97.87
5,1	0,4	9.81	8.45	63.86	98.97
0,1	6,1	7.69	7.58	90.91	100.00
4,0	3,3	5.24	4.53	87.78	97.98

Initial	Target	$ S\_h $	$ S\_m $	$ S\_mt $
1,0	2,6	8.25	7.59	7.16
3,3	2,1	3.81	3.42	3.05
4,5	5,5	1.56	1.44	1.13
5,0	3,2	4.48	4.32	4.16
6,0	1,5	10.98	10.52	10.06
1,2	2,6	6.54	5.57	5.13
2,5	6,0	9.83	9.65	9.17
5,1	0,4	9.23	8.78	8.16
0,1	6,1	7.28	6.96	6.52
4,0	3,3	4.88	4.54	4.12
Average value		6.69	6.28	5.86

Planning, monitoring and replanning techniques for handling abnormity in HTN-based planning and execution

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 38

相关文章 0

编辑推荐

Metrics

本文评价