Integer Programming Approaches for Automated Planning
ProQuest, 2008 - 145 pages
In particular, this research makes the following contributions. (1) It introduces novel integer programming approaches where causal considerations are separated from sequencing considerations, and where more general interpretations of action parallelism are introduced. The combination of these ideas leads to very effective integer programming formulations that are solved using a branch-and-cut algorithm. (2) It shows how to exploit these novel integer programming formulations in solving partial satisfaction problems, which are planning problems that typically require an increased emphasis on the modeling and handling of plan quality. (3) It develops a novel framework based on linear programming that gives rise to finding provably optimal plans. Moreover, this framework can also be used in heuristic search approaches for automated planning.
What people are saying - Write a review
We haven't found any reviews in the usual places.
PLANNING BY INTEGER PROGRAMMING
PARTIAL SATISFACTION PLANNING
DIRECTIONS FOR FURTHER RESEARCH
automated planning automaton binary Blocksworld branch-and-cut algorithm Briel change arcs change variables classical planning components corresponding CPLEX defined delete denotes deterministic automaton domain transition graph encodings executed feasible solution finite Freecell G1SC G2SC GlSC formulation goal utility Graphplan Graphplan-style parallelism heuristic initial integer programming formulations International Planning Competition IP formulation IPC2 IPC3 Kambhampati layers linear programming loc2 loci loosely coupled LP relaxation Miconic multi-valued state description multi-valued state variables mutex network flow problems network representation nodes nonmonotonic number of plan objective function optimal plans Optiplan ordering constraints ordering implication constraints package partial satisfaction planning path PathSC formulation personl plan period plan step planner planning domain planning graph planning problem precedence graph preconditions presolve prevail condition problem instances propositional PSP Net Benefit PSPACE PSPACE-complete represented resource Rovers SAS+ Satellite satisfied SATPLAN04 sequence of actions set of actions solve subnetwork trajectory constraint utility dependencies value transitions Vossen Zenotravel