Global ETD Search

1	Learning Partial Policies for Intractable Domains on Tractable Subsets. / Lärande av ofullständiga strategier för svårlärda domäner via lättlärda delmängder. Carlsson, Viktor January 2023 (has links) The field of classical planning deals with designing algorithms for generating plans or squences of actions that achieve specific goals. It involves representing a problem domain as a set of state variables, actions and goals, and then developing search algorithms that can explore the state of possible plans to find the one that satisfies the specified goal. Classical planning domains are often NP-hard, meaning that their worst-case complexity grows exponentially with the size of the problem. This means that as the number of state variables, actions and goals in the problem domain increases, the search space grows exponentially, making it very difficult to find a plan that satisfies the specified goal. This thesis is concerned with investigating these NP-hard domains, specifically by simplifying these domains into ones that have a polynomial solving time, creating a general policy of conditions and rules for which actions to take for the simplified domain, and then attempting to apply this policy onto the original domain. This creates a partial policy for the original domain, and the performance of this policy can be measured in order to judge its effectiveness. This can be explained as simplifying an intractable domain into a tractable one, creating a general policy for the tractable domain and then measuring its performance as a partial policy for the intractable domain. Classical Planning Planning Artificial Intelligence Transport Nurikabe NP-hard NP-hardness Computational Complexity Polynomial Polynomial Time P P-SPACE Planning Domain Planning Domains Planning Task Planning Tasks State States State Space General Policy Partial Policy Computer Systems Datorsystem
2	New Heuristics for Planning with Action Costs Keyder, Emil Ragip 17 December 2010 (has links) Classical planning is the problem of nding a sequence of actions that take an agent from an initial state to a desired goal situation, assuming deter- ministic outcomes for actions and perfect information. Satis cing planning seeks to quickly nd low-cost solutions with no guarantees of optimality. The most e ective approach for satis cing planning has proved to be heuristic search using non-admissible heuristics. In this thesis, we introduce several such heuristics that are able to take into account costs on actions, and there- fore try to minimize the more general metric of cost, rather than length, of plans, and investigate their properties and performance. In addition, we show how the problem of planning with soft goals can be compiled into a classical planning problem with costs, a setting in which cost-sensitive heuristics such as those presented here are essential. / La plani caci on cl asica es el problema que consiste en hallar una secuencia de acciones que lleven a un agente desde un estado inicial a un objetivo, asum- iendo resultados determin sticos e informaci on completa. La plani caci on \satis cing" busca encontrar una soluci on de bajo coste, sin garant as de op- timalidad. La b usqueda heur stica guiada por heur sticas no admisibles es el enfoque que ha tenido mas exito. Esta tesis presenta varias heur sticas de ese g enero que consideran costes en las acciones, y por lo tanto encuentran soluciones que minimizan el coste, en lugar de la longitud del plan. Adem as, demostramos que el problema de plani caci on con \soft goals", u objetivos opcionales, se puede reducir a un problema de plani caci on clasica con costes en las acciones, escenario en el que heur sticas sensibles a costes, tal como las aqu presentadas, son esenciales. unfolded hyperpath STRIPS Steiner tree soft goal compilation set-additive heuristic soft goal search satisficing planning relaxed plan heuristic relaxed plan relaxation recursive conditioning planning domain planning landmark optimal planning oversubscription independence independence assumption inference landmark heuristic hypergraph heuristic heuristic search graph dtree delete relaxation cost constraint satisfaction conjunctive landmark classical planning complexity choice variable Bayesian network additive heuristic algorithm AND/OR graph action cost 62

Search results

Learning Partial Policies for Intractable Domains on Tractable Subsets. / Lärande av ofullständiga strategier för svårlärda domäner via lättlärda delmängder.

New Heuristics for Planning with Action Costs