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

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.