Caracterización de los modelos de búsqueda de un agente con descripciones generalizadas de los nodos origen y destino

Linares López, Carlos (2001). Caracterización de los modelos de búsqueda de un agente con descripciones generalizadas de los nodos origen y destino. Tesis (Doctoral), Facultad de Informática (UPM) [antigua denominación].

Descripción

Título: Caracterización de los modelos de búsqueda de un agente con descripciones generalizadas de los nodos origen y destino
Autor/es:
  • Linares López, Carlos
Director/es:
  • Gómez-Pérez, Asunción
Tipo de Documento: Tesis (Doctoral)
Fecha: 2001
Materias:
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) (Texto) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (2MB) | Vista Previa
[img]
Vista Previa
PDF (Document Portable Format) (Anexo) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (447kB) | Vista Previa

Resumen

Los algoritmos de búsqueda de un agente son, en principio, una técnica muy útil para la construcción de sistemas inteligentes. Sin embargo, su estudio se ha restringido habitualmente a pocos dominios, en casos muy restringidos y, en términos generales, no existe una comprensión definitiva sobre su comportamiento. Por lo tanto, esta tesis está dedicada al estudio de algoritmos de búsqueda de un agente, con el propósito de caracterizar su comportamiento en un entorno que garantice la igualdad de condiciones en dos dominios de muy diversa naturaleza, y que sirvan para caracterizar su utilidad y la forma en que pueden mejorarse, fundamentalmente con el uso de estrategias bidireccionales, o de perímetro, con las que es posible mejorar muy significativamente los resultados obtenidos. Para ello, se ha empleado el algoritmo unidireccional RBFS y se proponen dos versiones bidireccionales, los algoritmos BRBFS* e IBRBFS*, y una versión de perímetro, el algoritmo RBFPS*. Asimismo, se propone también una versión de perímetro, denominada, DFBnBPS*, del algoritmo unidireccional de ramificación y acotación en profundidad. Por último, introduce conceptos novedosos sobre la utilidad de los algoritmos de este tipo, tradicionalmente circunscritos a la resolución de problemas de optimización con descripciones explícitas y únicas de los nodos finales, que servirán para generalizar la descripción de los nodos origen y final con el uso de formulaciones lógicas que deben ser necesariamente satisfechas. ABSTRACT Single-agent search algorithms are, at first, a very useful technique for constructing intelligent systems. However, their study has been severely restricted to a few very well-defined domains and, in general terms, there is not a comprehensive description of their behaviour. Thereby, this thesis is devoted to the research in single-agent search algorithms, with the main purpose of characterizing its behaviour. For that, a computational environment which guarantees the same conditions for all the algorithms in two very different domains has been devised. Besides, it is considered the way they can be improved, mainly with the use of bidirectional strategies which lead to significant improvements. For that, the RBFS search algorithm is employed and two new bidirectional versions of it are proposed, BRBFS* and IBRBFS*, along with a perimeter versión of the same algorithm, called RBFPS*. Likewise, a new perimeter search algorithm is introduced, the DFBnBPS*, which employs the dept-first branch-and-bound search algorithm. At last, it introduces new concepts about the utility of the algorithms of this category. Indeed, a new framework is presented where the same search algorithms can be used for any logical description of start and goal nodes. This approach guarantees a wider aplicability, as long as the same set of search algorithms have been traditionally dedicated to the task of solving optimality problems with explicit descriptions of unique goal states.

Más información

ID de Registro: 9822
Identificador DC: http://oa.upm.es/9822/
Identificador OAI: oai:oa.upm.es:9822
Depositado por: Archivo Digital UPM 2
Depositado el: 12 Dic 2011 15:32
Ultima Modificación: 20 Abr 2016 18:06
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM