状态空间搜索的anytime模式及其高效算法研究

As a fundamental problem solving framework, state space search has been applied into many areas, e.g. artificial intelligence, bioinformatics, robotics. With improvements in computer technology, problems needing to be solved in these areas becomes more and more complex, e.g. larger data volume, higher data dimension, etc. Yet, many search algorithms need too much time and/or space to analyze such complex problems. “Anytime search” provides a potential approach to the aforementioned problem by enabling updated solutions to be usable in an arbitrary amount of time. The proposed work focuses on the following problems: (1) Studying tradeoff strategies for time and space resources and establishing their models; (2) Designing anytime search frameworks and efficient search strategies to ameliorate time and space issues; (3) Studying partition methods for state space and designing parallel anytime search frameworks; (4) Solving practical problems to validate the performance of algorithms and studying heuristic knowledge and pruning strategies. This work will provide a general anytime search framework to solve issues around time and space limitations as well as provide a feasible solving strategy for large scale practical problems.

作为一个基本的问题求解框架，状态空间搜索被应用于多个领域，如人工智能、生物信息学、机器人学等。随着计算技术的发展，这些领域需要求解的实际问题呈现复杂化特点，如数据规模大、数据维度高等。传统状态空间搜索算法受时间或空间限制，难以处理这些复杂问题。而anytime搜索采用迭代技术渐进消耗时间与空间来更新优化解的模式为这些复杂问题的求解提供了可能。故本项目以此为切入点，主要研究内容为：（1）状态空间搜索中时空转化策略及其数学建模；（2）面向时空资源受限的anytime搜索框架设计及高效搜索技术研究；（3）并行环境的状态空间划分方法及anytime搜索框架设计；（4）若干复杂应用问题的启发知识、剪枝技术研究及融合这些技术的anytime搜索算法求解。此研究成果可为状态空间搜索提供一个面向时空受限的anytime搜索框架及并行化的anytime搜索策略，同时为复杂实际应用问题提供一种可行的求解方案。

作为一个基本的问题求解框架，状态空间搜索被应用于多个领域，如人工智能、生物信息学、机器人学等。当前的实际应用问题呈现复杂化的特点，如数据规模大、数据维度高等，传统的状态空间搜索算法难以处理这些复杂实际应用问题。因此，本项目致力于构建anytime模式的状态空间搜索技术，使得算法可渐进输出更优解。本项目的主要工作包括：（1）通过状态空间节点的删除及再生成建立状态空间搜索的时空转化策略；（2）建立了基于迭代束搜索的anytime模式状态空间搜索算法，即通过将状态空间分层，逐层迭代搜索，且每次迭代中限制每层的节点数目，该算法可在较短时间内输出近似解，并持续输出更优解，且在空间消耗达到限制时通过时空转化维持搜索的持续；（3）在串行算法的基础上，针对状态空间的分层结构，采用按层循环划分的策略，建立并行化的anytime状态空间搜索。在维持anytime搜索性质的同时，提高搜索效率；（4）将合成生物学中的合成生物元件链路构建问题转化为状态空间搜索问题，合成生物元件对应于状态空间节点，合成生物元件链路对应于状态空间中的路径，通过应用状态空间搜索算法，实现了合成生物元件链路的推荐；（5）进一步通过非线性空间降维，将合成生物元件压缩到2维或3维空间中进行可视化，检验合成生物元件质量，指导状态空间搜索；（6）针对多机器人协同路径规划问题，在状态空间建模中引入多机器人的冲突规避措施，包括运动速率的改变与路径的调整，通过状态空间搜索获得多约束下的路径最优求解。通过本项目的开展为状态空间搜索提供一个面向时空受限的anytime搜索框架及并行化的anytime搜索策略，同时为复杂实际应用问题提供了一种可行的求解方案。