一种带局部搜索空间的动态目标搜索算法

摘要

动态目标路径规划问题是游戏人工智能中极具挑战性的研究内容之一,其研究成果可广泛应用于机器人导航、军事仿真等众多领域,具有较大的研究价值和实用价值。
　　 本文在人工智能搜索技术之上,深入研究了实时游戏中移动目标搜索算法MTS,并针对该算法更新启发值慢、搜索效率低、追捕成功率不高等问题,提出了一种带局部搜索空间的动态目标搜索算法LSS-MTS。该算法将LSS-LRTA*算法的局部搜索空间确定方法及启发值更新策略,应用到移动目标搜索算法中,解决了MTS搜索效率低的问题。与MTS相比,LSS-MTS算法学习效率更高,启发值更新策略更有效,因此,LSS-MTS能够更好地满足大型游戏场景以及现实中对路径搜索严格的实时性要求。
　　 实验结果表明,随着障碍物分布比例及智能体与目标间速度比例的增加,LSS-MTS算法在追捕成功率、平均搜索时间上较MTS算法有明显的优势,同时该算法可以根据搜索时间等条件限制,预先设定前探值的大小,从而减少搜索时间,很好的满足实时性要求。

目录

文摘

英文文摘

1 绪论

1.1 研究背景

1.2 研究现状

1.3 本文工作概述

2 相关知识

2.1 图搜索策略

2.2 盲目搜索

2.3 启发式搜索

2.3.1 启发函数

2.3.2 经典A*算法

2.3.3 实时启发式搜索

2.4 本章小结

3 带局部搜索空间的动态目标搜索算法

3.1 MTS算法

3.1.1 问题描述

3.1.2 算法主要思想

3.2 启发值更新策略

3.2.1 更新策略

3.2.2 更新策略分析

3.3 带局部搜索空间的动态目标搜索算法

3.3.1 算法思想

3.3.2 算法流程描述

3.3.3 LSS-MTS算法分析

3.4 本章小结

4 实验与性能分析

4.1 实验环境

4.2 实验设计

4.2.1 实验场景设计

4.2.2 主要设计思想

4.3 实验结果对比分析

4.3.1 LSS-MTS算法性能

4.3.2 不同的障碍物分布比例下算法性能对比

4.3.3 不同智能体相对目标速度比下算法性能对比

4.4 实验结果分析

4.5 本章小结

5 总结与展望

5.1 总结

5.2 展望

参考文献

致谢

个人简历、在学期间发表的学术论文与研究成果