Busqueda

8. Introducción a los Sistemas de Búsqueda
En Inteligencia Artificial (IA) los términos resolución de problemas y búsqueda se refieren a un núcleo fundamental de técnicas que se utilizan en dominios como la deducción, elaboración de planes de actuación, razonamientos de sentido común, prueba automática de teoremas, etc. Aplicaciones de estas ideas generales aparecen en la práctica totalidad delos sistemas inteligentes, como por ejemplo en los programas que tratan de entender el lenguaje natural, en los programas que tratan de sintetizar un conjunto de reglas de clasificación en un determinado dominio de actuación, o en los sistemas que realizan inferencias a partir de un conjunto de reglas. En este capítulo y en el siguiente examinaremos los algoritmos de búsqueda como una herramientapara resolver problemas y los trataremos de un modo general con objeto de que sirvan de base para abordar una variedad de problemas de distinta naturaleza. La resolución de problemas en IA requiere, normalmente, determinar una secuencia de acciones o decisiones. Esta secuencia será ejecutada posteriormente por un agente con el fin de alcanzar un objetivo a partir de una situación inicial dada.Dependiendo del problema concreto, la ejecución de la secuencia de acciones o decisiones tiene asociado un coste que se tratará de minimizar, o bien tiene asociado un beneficio que se tratará de maximizar. En la descripción de los sistemas de búsqueda que se realiza en este capítulo, supondremos que el agente se mueve en un entorno accesible, o lo que es lo mismo, que es capaz de percibir el entornocon precisión. Además, supondremos también que tanto el efecto como el coste de las acciones se pueden predecir con exactitud. De este modo, la secuencia de acciones se puede obtener antes de su ejecución; en otro caso, la siguiente acción no podría ser determinada hasta conocer el resultado de la ejecución de la anterior.

8.1. Algunos Ejemplos
Con el fin de introducir las ideas y componentesesenciales de los sistemas de búsqueda, comenzaremos introduciendo algunos ejemplos clásicos que se resuelven con este tipo de algoritmos. El objetivo es mostrar distintos tipos de problemas de búsqueda y caracterizar los métodos de aplicación más general.

8.1.1.

Generación de Planes de Actuación de Robots

Este ejemplo está tomado de (Nilsson 2001, sección 7.2). La investigación sobreresolución de problemas de robots ha dado lugar a muchas técnicas de resolución de problemas generales que se usan en IA. El planteamiento típico de uno de estos problemas consta de un robot que tiene un repertorio finito de acciones que puede ejecutar y de un entorno de actuación. La situación más paradigmática es la del "mundo de bloques". En este caso se dispone de unos cuantos bloquesdistinguibles unos de otros situados sobre una mesa y un brazo móvil (el robot) capaz de cambiarlos de sitio; suponemos, además, que el robot es capaz de localizar a estos bloques al objeto de realizar alguna tarea con ellos. Programar un robot consiste en integrar varias funciones, entre las que se incluye la percepción del entorno que le rodea, la formulación de planes de actuación y el seguimiento de esosplanes. Para ello el primer paso es disponer de un modelo del entorno que permita representar lo relevante de todas las situaciones que se puedan producir.

Técnicas Basadas en Búsqueda a Ciegas - 1/24

A B A B
a) Inicial

C

C
b) Objetivo

Figura 1. Estados inicial y objetivo para una instancia del problema de generación de planes de actuación de robots con tres bloques

Supongamosque el entorno está formado por tres bloques A, B y C, inicialmente situados en el suelo, y que el objetivo es llegar a una situación en la que los tres bloques estén formando una pila de modo que el bloque C esté en el suelo, el bloque B sobre C y el bloque A sobre B, tal y como se muestra en la Figura 1. El modelo del entorno nos debe permitir representar lo relevante de estas, y otras,...