We consider the problem of optimal planning in determinis- tic domains and reduce it to the problem of finding an optimal solution of a corresponding constraint optimization problem incorporating a bound n on the maximum length of the plan. By solving the latter, we can conclude whether (i) the plan found is optimal even for bounds greater than n; or (ii) we need to increase n; or (iii) it is useless to increase n since the planning problem has no solution. Our approach (i) sub- stantially generalizes previous approaches for optimal sym- bolic deterministic planning; (ii) allows to compute non triv- ial lower bounds on the cost and length of optimal plans; and (iii) produces an encoding linear in the size of the planning problem and the bound n
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | Optimal Planning as Constraint Optimization | |
Autori: | ||
Data di pubblicazione: | Being printed | |
Abstract: | We consider the problem of optimal planning in determinis- tic domains and reduce it to the problem of finding an optimal solution of a corresponding constraint optimization problem incorporating a bound n on the maximum length of the plan. By solving the latter, we can conclude whether (i) the plan found is optimal even for bounds greater than n; or (ii) we need to increase n; or (iii) it is useless to increase n since the planning problem has no solution. Our approach (i) sub- stantially generalizes previous approaches for optimal sym- bolic deterministic planning; (ii) allows to compute non triv- ial lower bounds on the cost and length of optimal plans; and (iii) produces an encoding linear in the size of the planning problem and the bound n | |
Handle: | http://hdl.handle.net/11567/1087524 | |
Appare nelle tipologie: | 04.01 - Contributo in atti di convegno |