规划图框架下用遗传算法求解时态规划问题  被引量:7

Using Genetic Algorithm to Solve Temporal Planning Problems Under the Framework of the Planning Graph

在线阅读下载全文

作  者:伍丽华[1] 陈蔼祥[1] 姜云飞[1] 

机构地区:[1]中山大学软件研究所

出  处:《计算机研究与发展》2008年第6期981-990,共10页Journal of Computer Research and Development

基  金:国家自然科学基金项目(60773201)~~

摘  要:许多现实世界中的规划问题通常希望规划目标能在尽可能短的时间内实现,并且规划动作的执行需要考虑时间因素.在规划图框架下,提出了一种能进行时态约束推理的遗传规划算法.主要工作有以下3个方面:1)介绍基于完全动作图的时序约束推理技术;2)提出能进行时序约束推理的基于规划图的遗传规划技术;3)针对基于规划图的遗传规划技术存在局部搜索能力不足的缺点,提出了在原有遗传操作算子的基础上,引入局部修复算子的混合规划技术.实验表明,这种算法能有效地处理一类时态规划问题.Automated planning is the reasoning side of acting and temporal planning is a broad research area in intelligent planning. In most real-world applications, many real planning problems often require the planning goals can be satisfied in shorter time, and the execution of planning solution must take the time into account. In this paper, a temporal genetic planning algorithm is presented, which is under the framework of temporal planning graph and capable of reasoning about the temporal constraint. The main contributions of this algorithm consist of: (1) Presenting a temporal planning graph under the planning graph by making time explicit in the representation, and giving a new temporal constraint reasoning technology to handle the temporal problems based on the full temporal action subgraph, (2) Encoding the candidate planning solutions into chromosomes and making an adaptive evaluation function, using genetic algorithm to deal with temporal planning problems under the framework of the temporal planning graph, and (3) Stating the meaning of the local fix operator, presenting a hybrid approach which combines this operator with the traditional genetic operators to strengthen the algorithms' capability of local search, so that the algorithms can converge faster and find a planning solution finally. The experiments show that the algorithm can deal with efficiently a kind of simple temporal planning problem.

关 键 词:规划图 动作图 完全动作图 遗传算法 时态规划 

分 类 号:TP18[自动化与计算机技术—控制理论与控制工程]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象