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

项目名称： 状态空间搜索的anytime模式及其高效算法研究

项目编号： No.61502135

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 自动化技术、计算机技术

项目作者： 杨矫云

作者单位： 合肥工业大学

项目金额： 20万元

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

英文关键词： heuristic algorithms;state space search;parallel search;multiple longest common subsequences;multiple DOF motion planning