Diseño de un algoritmo de búsqueda informada mediante el simulador robótico Stage

• Autor: Marcelo Saavedra Alcoba - Luigi Pedro Enríquez Paz
• Cargo: Instituto de Investigaciones en Ciencia y Tecnología, Universidad La Salle Bolivia
• Páginas: 39-59

39

FIDES ET RATIO VOL. 10: ( ), SEPT. 2015 ISSN 2071-081X

ISSN 2411-0035

39-59

DISEÑO DE UN ALGORITMO DE BÚSQUEDA INFORMADA

MEDIANTE EL SIMULADOR ROBÓTICO STAGE

Marcelo Saavedra Alcoba, Luigi Pedro Enríquez Paz

Instituto de Investigaciones en Ciencia y Tecnología

Universidad La Salle Bolivia

msaavedra@doc.ulasalle.edu.bo, lpenriquez@est.ulasalle.edu.bo

Resumen

Se propone una nueva metodología para una búsqueda informada de

objetos mediante un robot móvil. La metodología está basada en una

combinación de un algoritmo de búsqueda en espiral y un algoritmo de

búsqueda mediante un enfoque bayesiano que usa convoluciones entre

“probabilidades de observación” y “máscaras de relaciones espaciales”

para estimar un mapa probabilidad donde se pueda encontrar el objeto

de búsqueda. Las relaciones espaciales entre objetos son representadas

mediante el uso de máscaras circulares denidos como sumas ponderadas

de relaciones espaciales básicas utilizando matrices de co-ocurrencia como

pesos. La metodología está validada en un ambiente tipo ocina en la que

existen cuatro clases de objetos comunes (“monitor”, “teclado”, “cpu” y

“router”) y se consideró cuatro relaciones espaciales básicas (“muy cerca”,

“cerca”, “lejos” y “muy lejos”). Se realizaron un total de 500 experimentos

que comparan 5 métodos de búsqueda utilizando el simulador robótico

Stage. Los resultados muestran que el uso de la metodología propuesta

tiene una tasa de detección mayor que un 70%, comparado a otros métodos

como ser: Método de búsqueda en espiral, Método de búsqueda informada

usando partículas entre otros.

Palabras Claves

Búsqueda informada, búsqueda en espiral, robótica móvil, inteligencia

articial.

40

Marcelo Saavedra Alcoba

Luigi Pedro Enríquez Paz

Abstract

A novel methodology for robots executing informed object search is

proposed. The methodology is based mainly on a heuristic spiral search

algorithm and a Bayesian framework that uses convolutions between

observation likelihoods and spatial relation masks for estimating the

probability map of the object being search for. The spatial relationships

between objects can be dened as weighted sums of basic spatial relations

using co-occurrence matrices as weights. The methodology is validated in

an ofce environment in which four object classes (“monitor,” “keyboard,”

“system unit,” and “router”) and four basic spatial relations (“very near,”

“near,” far,” and “very far”) are considered. A total of 500 experiments

comparing ve object search algorithms were realized by using the robotics

simulator Stage. The results show that using the proposed methodology

has a higher detection rate of 70%, compared to other methods such as:

Method spiral search, method using particles informed, among others.

Key Words

Informed search, spiral search, mobile robot, articial intelligence.

I. Introducción

La búsqueda de objetos en la vida cotidiana es una de las tareas más

fundamentales de los seres humanos. Por esta razón, “buscar” es una de

las tareas más básicas que se espera de un robot. Los problemas sobre

búsqueda de rutas óptimas han sido muy estudiados en el área de la

Inteligencia Articial, pero buscar un objeto en un ambiente real es un

trabajo más costoso ya que los objetos no siempre estarán al alcance del

robot, y pueden estar ocluidos por otros objetos. El realizar una búsqueda

en un ambiente real implica identicar y elegir un conjunto de acciones

apropiadas de un conjunto muy grande de posibilidades. En contraste con

los problemas clásicos de búsqueda de IA, en la búsqueda robótica se

desea no volver a moverse entre lugares ya visitados (Burlington S, Dudek

G., 1999). La situación más común al buscar un objeto en un ambiente

interior es que el objeto pueda estar fuera del rango de visión del robot,

otro ejemplo puede ocurrir en un ambiente interior como una ocina donde