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

• SYSTEMS ENGINEERING • Previous Articles Next Articles

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

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.

Figures/Tables 9

Fig 1

Fig 2

Fig 3

Table 1

Fig 4

Table 2

Fig 5

Fig 7

Fig 6

References 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

[1]	Faxing LU, Qiuyang DAI, Guang YANG, Zhengrong JIA. Online task planning method of anti-ship missile based on rolling optimization [J]. Journal of Systems Engineering and Electronics, 2024, 35(3): 720-731.
[2]	Jiandong ZHANG, Yukun GUO, Lihui ZHENG, Qiming YANG, Guoqing SHI, Yong WU. Real-time UAV path planning based on LSTM network [J]. Journal of Systems Engineering and Electronics, 2024, 35(2): 374-385.
[3]	Jia ZHANG, Xin DU, Qichen DONG, Bin XIN. Distributed collaborative complete coverage path planning based on hybrid strategy [J]. Journal of Systems Engineering and Electronics, 2024, 35(2): 463-472.
[4]	Jinming LIU, Yingguo CHEN, Rui WANG, Yingwu CHEN. Complex task planning method of space-aeronautics cooperative observation based on multi-layer interaction [J]. Journal of Systems Engineering and Electronics, 2023, 34(6): 1550-1564.
[5]	Feng WU, Xiuluo LIU, Jia WANG, Chao LI, Ying LIU, Jianbin SU, Ailiang ZHANG, Min WANG. Research on agile space emergency launching mission planning simulation and verification method [J]. Journal of Systems Engineering and Electronics, 2023, 34(5): 1267-1284.
[6]	Dongdong YAO, Xiaofang WANG, Hai LIN, Zhuping WANG. Leader trajectory planning method considering constraints of formation controller [J]. Journal of Systems Engineering and Electronics, 2023, 34(5): 1294-1308.
[7]	Yunxiu ZENG, Kai XU. Recognition and interfere deceptive behavior based on inverse reinforcement learning and game theory [J]. Journal of Systems Engineering and Electronics, 2023, 34(2): 270-288.
[8]	Lu DONG, Zichen HE, Chunwei SONG, Changyin SUN. A review of mobile robot motion planning methods: from classical motion planning workflows to reinforcement learning-based architectures [J]. Journal of Systems Engineering and Electronics, 2023, 34(2): 439-459.
[9]	Jianmai SHI, Jiaming ZHANG, Hongtao LEI, Zhong LIU, Rui WANG. Joint mission and route planning of unmanned air vehicles via a learning-based heuristic [J]. Journal of Systems Engineering and Electronics, 2023, 34(1): 81-98.
[10]	Jing LUO, Qianchao LIANG, Hao LI. UAV penetration mission path planning based on improved holonic particle swarm optimization [J]. Journal of Systems Engineering and Electronics, 2023, 34(1): 197-213.
[11]	Peng LIU, Boyuan XIA, Zhiwei YANG, Jichao LI, Yuejin TAN. A deep reinforcement learning method for multi-stage equipment development planning in uncertain environments [J]. Journal of Systems Engineering and Electronics, 2022, 33(6): 1159-1175.
[12]	Lei HU, Boqi XI, Guoxing YI, Hui ZHAO, Jiapeng ZHONG. A multiple heterogeneous UAVs reconnaissance mission planning and re-planning algorithm [J]. Journal of Systems Engineering and Electronics, 2022, 33(6): 1190-1207.
[13]	Honghong ZHANG, Xusheng GAN, Shuangfeng LI, Zhiyuan CHEN. UAV safe route planning based on PSO-BAS algorithm [J]. Journal of Systems Engineering and Electronics, 2022, 33(5): 1151-1160.
[14]	Lanyong ZHANG, Ruixuan ZHANG. Research on UAV cloud control system based on ant colony algorithm [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 805-811.
[15]	Gang LIU, Zhibiao AN, Songyang LAO, Wu LI. Firepower distribution method of anti-ship missile based on coupled path planning [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 1010-1024.

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

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 9

References 38

Related Articles 15

Recommended Articles

Metrics

Comments