TY - GEN
T1 - Planning for multiple goals with limited interactions.
AU - Nau, Dana S.
AU - Yang, Qiang
AU - Hendler, James
PY - 1988
Y1 - 1988
N2 - A description is presented of the problem of finding an optimal global plan for a multigoal planning problem by combining plans that solve the individual goals. This problem arises in process planning, when one tries to combine the process plans for individual machinable features into a global process plan for the entire workpiece. It also arises in the planning of robot actions, when one tries to combine the plans for the handling of individual objects into a global plan. The problem can show to be NP-hard in general. However, if only one plan is available for each goal, then the problem can be solved in time O(n2) by imposing restrictions on the kinds of intergoal interactions involved. If more than one plan is available for each goal, the problem is still NP-hard even if these restrictions are satisfied, but in this case a heuristic search algorithm has been developed which performs well.
AB - A description is presented of the problem of finding an optimal global plan for a multigoal planning problem by combining plans that solve the individual goals. This problem arises in process planning, when one tries to combine the process plans for individual machinable features into a global process plan for the entire workpiece. It also arises in the planning of robot actions, when one tries to combine the plans for the handling of individual objects into a global plan. The problem can show to be NP-hard in general. However, if only one plan is available for each goal, then the problem can be solved in time O(n2) by imposing restrictions on the kinds of intergoal interactions involved. If more than one plan is available for each goal, the problem is still NP-hard even if these restrictions are satisfied, but in this case a heuristic search algorithm has been developed which performs well.
UR - http://www.scopus.com/inward/record.url?scp=0024170852&partnerID=8YFLogxK
M3 - Conference Paper published in a book
AN - SCOPUS:0024170852
SN - 0818619023
T3 - Proc Fifth Conf Artif Intell
SP - 263
EP - 270
BT - Proc Fifth Conf Artif Intell
A2 - Anon, null
PB - Publ by IEEE
T2 - Proceedings - Fifth Conference on Artificial Intelligence Applications
Y2 - 6 March 1989 through 10 March 1989
ER -