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. Thesis (Doctoral), Facultad de Informática (UPM).

Description

Title: Caracterización de los modelos de búsqueda de un agente con descripciones generalizadas de los nodos origen y destino
Author/s:
  • Linares López, Carlos
Contributor/s:
  • Gómez-Pérez, Asunción
Item Type: Thesis (Doctoral)
Date: 2001
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF (Texto) - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB) | Preview
[img]
Preview
PDF (Anexo) - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (447kB) | Preview

Abstract

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.

More information

Item ID: 9822
DC Identifier: http://oa.upm.es/9822/
OAI Identifier: oai:oa.upm.es:9822
Deposited by: Archivo Digital UPM 2
Deposited on: 12 Dec 2011 15:32
Last Modified: 20 Apr 2016 18:06
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM