| dbo:abstract
|
- Der Graphplan-Algorithmus ist ein Algorithmus aus dem Gebiet der künstlichen Intelligenz. Er dient dem automatischen Finden einer Folge von Aktionen, die zu einem gewünschten Ziel führen. Die Lösung wird mit Hilfe eines sog. Planungsgraphen in polynomieller Zeit gefunden. (de)
- Graphplan is an algorithm for automated planning developed by Avrim Blum and in 1995. Graphplan takes as input a planning problem expressed in STRIPS and produces, if one is possible, a sequence of operations for reaching a goal state. The name graphplan is due to the use of a novel planning graph, to reduce the amount of search needed to find the solution from straightforward exploration of the state space graph. In the state space graph:
* the nodes are possible states,
* and the edges indicate reachability through a certain action. On the contrary, in Graphplan's planning graph:
* the nodes are actions and atomic facts, arranged into alternate levels,
* and the edges are of two kinds: 1.
* from an atomic fact to the actions for which it is a condition, 2.
* from an action to the atomic facts it makes true or false. the first level contains true atomic facts identifying the initial state. Lists of incompatible facts that cannot be true at the same time and incompatible actions that cannot be executed together are also maintained. The algorithm then iteratively extends the planning graph, proving that there are no solutions of length l-1 before looking for plans of length l by backward chaining: supposing the goals are true, Graphplan looks for the actions and previous states from which the goals can be reached, pruning as many of them as possible thanks to incompatibility information. A closely related approach to planning is the Planning as Satisfiability (Satplan). Both reduce the automated planning problem to search for plans of different fixed horizon lengths. (en)
- Graphplan es un algoritmo para la planificación automática desarrollado por y en 1995. El algoritmo toma como entrada un problema de planificación expresado en STRIPS y produce, de ser posible, una secuencia de operaciones para llegar a un estado final. El nombre graphplan es debido a la utilización de un grafo de planificación, para reducir la cantidad de búsqueda necesaria para encontrar la solución en la exploración directa de un grafo de espacio de estado. En un grafo de espacio de estado:
* los nodos son posibles estados,
* y las aristas indican la alcanzabilidad a través de ciertas acciones. Por el contrario, en un grafo de planificación:
* los nodos son las acciones y hechos atómicos, dispuestos en niveles alternos,
* y las aristas son de dos tipos: 1.
* de un hecho atómico a las acciones de las cuales es una condición, 2.
* de una acción a los hechos atómicos donde se convierte en verdadero o falso. El primer nivel contiene hechos atómicos verdaderos que identifican el estado inicial. También se mantienen las listas de hechos incompatibles que no pueden ser verdaderos al mismo tiempo y acciones incompatibles que no se pueden ejecutar en conjunto. El algoritmo extiende iterativamente el grafo de planificación, probando que no hay soluciones de longitud i-1 antes de buscar planes de longitud i por encadenamiento hacia atrás: suponiendo que los objetivos son verdaderos, el algoritmo de Graphplan busca las acciones y estados previos desde el cual el objetivo puede ser alcanzado, podando muchos de ellos mientras sea posible gracias a la información incompatible. Un enfoque muy relacionado con la planificación es la Planificación como Satisfacibilidad. Ambos reducen el problema de planificación automática para buscar los planes de diferentes longitudes de tamaño fijo. (es)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 2707 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Der Graphplan-Algorithmus ist ein Algorithmus aus dem Gebiet der künstlichen Intelligenz. Er dient dem automatischen Finden einer Folge von Aktionen, die zu einem gewünschten Ziel führen. Die Lösung wird mit Hilfe eines sog. Planungsgraphen in polynomieller Zeit gefunden. (de)
- Graphplan es un algoritmo para la planificación automática desarrollado por y en 1995. El algoritmo toma como entrada un problema de planificación expresado en STRIPS y produce, de ser posible, una secuencia de operaciones para llegar a un estado final. El nombre graphplan es debido a la utilización de un grafo de planificación, para reducir la cantidad de búsqueda necesaria para encontrar la solución en la exploración directa de un grafo de espacio de estado. En un grafo de espacio de estado: Por el contrario, en un grafo de planificación: (es)
- Graphplan is an algorithm for automated planning developed by Avrim Blum and in 1995. Graphplan takes as input a planning problem expressed in STRIPS and produces, if one is possible, a sequence of operations for reaching a goal state. The name graphplan is due to the use of a novel planning graph, to reduce the amount of search needed to find the solution from straightforward exploration of the state space graph. In the state space graph:
* the nodes are possible states,
* and the edges indicate reachability through a certain action. On the contrary, in Graphplan's planning graph: (en)
|
| rdfs:label
|
- Graphplan-Algorithmus (de)
- Graphplan (es)
- Graphplan (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
