Robot Volleyball

Aquí esta el robot haciendo magia del Volleyball =D

Gual-e primeras entregas.

Linea:

Gual-e y su determinación en la vida, jamás desviarse de su camino, aunque sea negro y torcido.

Sonido:

Al ritmo de algo que parece ser una canción, Gual-e y su fiel compañero Vasodeunicel buscan la felicidad eterna.

Laberinto:

Gual-e demostrando que no tiene las llantas calibradas

Definicion PAGE

Salir de un Laberinto
Perceptions-Muros, paredes, caminos.
Actions- Caminar, moverte por los caminos, dar vuelta.
Goals-Encontrar una salida.
Enviroment-Un circuito o espacio rodeado de paredes o muros, caminos transitables.

Explorar habitaciones y reconocer objetos
Perceptions-Muros, objetos, pasillos, puertas, muebles.
Actions- Recorrer el cuarto, sostener cosas, observar los objetos.
Goals-Reconocer que tipo de objetos son y saber que tipo de habitacion es.
Enviroment-Un cuarto que tiene objetos dentro de el, caracteristicos.

Jugar Ajedrez
Perceptions-Piezas, tablero, mesas, sillas.
Actions- Mover las piezas en el orden y forma que puedan.
Goals-Ganar la partida.
Enviroment-Un lugar que contenga un espacio para acomodar un tablero y sus oponentes.

Cuiadar una persona mayor en su casa.
Perceptions-Casa, muebles, cuartos, persona, medicamnetos, comida.
Actions- Alimentar, dar medicinas, llevarla al baño, platicar.
Goals-Que sobreviva la persona mayor.
Enviroment-Una casa ajustable y condicionada con todos los servicios necesarios.

Relaciones Familiares

Vx,y Brother(x,y)<-> x#ý^ Male(x)^Ep parent(x) = parent(y)

Vy,x Sister(y,x)<-> y#x ^Female(y)^Ep Parent(y) =parent(x)

Vgp,c Grandpa(gp,c)<->Ep parent(gp,p) ^ parent(p,c)^male(gp)

Vgm,c Grandma(pm,c)<->Ep paren(gm,p)^parent(p,c)^female(gm)

Resolución de Actividad.

Resolución de Actividad

-Que esta claro?

Una heurística es usado para definir el estudio de los métodos para descubrir
e inventar técnicas para solucionar problemas, particularmente para los que
requieren pruebas matemáticas. Tales métodos no se consideran susceptibles de
explicación.

El método de Greedy Search. Se mueve a la siguiente posición más atractiva.

Aquel nodo cuyo estado se inclina más a la meta es expandido primero.

Usa una función heurística para estimar el costo del camino más barato desde el
estado del nodo “n” hasta la meta.

Es incompleto, puede seguir un camino infinito y nunca regresara probar otras
posibilidades.

-Que es lo mas importante?

Conocer la definición de heurística, comprender como funcionan los algoritmos de
búsqueda, y sus mejoras, es decir que podamos comprender la complejidad y optimisidad
para cada uno de los eventos o posibilidades que se nos pueda presentar y saber que método
es el mas acertado a utilizar.

-Que dudas quedan?

Del método de A* El problema es que, para la mayoría de los problemas, el número de
nodos en el espacio de búsqueda del contorno meta sigue siendo exponencial en la longitud
de la solución. Aunque la prueba del resultado está fuera del alcance de este libro, se
ha demostrado que el crecimiento exponencial se producirá a menos que el error en el
heurístico no crece más rápido que el logaritmo de la ruta real de costos.

Es una método de búsqueda que es el mejor-primera búsqueda que utiliza “f” que es la
función de evaluación y admite las funciones de “h”.

Como g (n) se obtiene el costo del camino desde el nodo inicial al nodo n y h (n) es el costo
estimado de los caminos más baratos de n a la meta

/ («) = Costo estimado de la solución más barata a través de n

f(n) = g(n) + h(n).

Busquedas Heuristicas.

¿Qué es una heurística?

Etimológicamente significa “búsqueda” o “descubrir”.
Es usado para definir el estudio de los métodos para descubrir e inventar técnicas para
solucionar problemas, particularmente para los que requieren pruebas matemáticas. Tales
métodos no se consideran susceptibles de explicación.
Actualmente se usa más para describir que cualquier técnica mejore el rendimiento en
casos promedio de una tarea de solución de problemas. En el caso específico de los
algoritmos de búsqueda, se refiere a una función que proporciona el coste de una solución.

BEST-FIRST SEARCH
Definición:
Es un algoritmo que explora un grafo, expandiendo el nodo mas prometedor,
determinado por una regla especifica.

Características:
Se escoge el nodo que aparente ser el mejor o mas cercano, de acuerdo a una funcion
que evalué la importancia de los nodos.
function BEST-FiRST-SEARCH(/7/-oWew?, EVAL-FN) returns a solution sequence
inputs: problem, a problem
Eval-Fn, an evaluation function
Queueing-Fn <— a function that orders nodes by EVAL-FN
return GENERAL-SEARCH(proW
Complejidad:

Optimabilidad: No es óptimo, requiere de heuristicas para mejorarlo.

Completud: Es incompleto. La funcion que evalua los nodos puede fallar y tomar un mal camino.

Greedy Search.

Definición:

Búsqueda BFS que busca minimizar el costo estimado para alcanzar la meta.

Características:

Se mueve a la siguiente posición más atractiva.

Aquel nodo cuyo estado se inclina más a la meta es expandido primero.

Usa una función heurística para estimar el costo del camino más barato desde el estado del nodo “n” hasta la
meta.

El código sería:

function GREEDY-SEARCH(problem) returns a solution or failure

return BEST-FiRST-SEARCH(problem, h) //siendo “h” la function heuristic

Complejidad.- En el peor de los casos su complejidad es O(bm), donde “m” es la profundidad máxima del espacio

de búsqueda. Su complejidad espacial es la misma que la temporal porque retiene todos los nodos en memoria. Estas
dependen de la función heurística, si está bien implementada la complejidad se puede reducir.

Optimalidad.- No es óptimo

Completud.- Es incompleto, puede seguir un camino infinito y nunca regresara probar otras posibilidades.

A*

Que es ? Es una método de búsqueda que es el mejor-primera búsqueda que utiliza “f” que es la
función de evaluación y admite las funciones de “h”.

Como g (n) se obtiene el costo del camino desde el nodo inicial al nodo n y h (n) es el costo estimado de
los camino más baratas de n a la meta

/ («) = Costo estimado de la solución más barata a través de n

f(n) = g(n) + h(n).

Principales Características:

Por lo tanto, si estamos tratando de encontrar la solución más barata, una cosa razonable es intentar
primero con el nodo con el menor valor de f.

La restricción es escoger una función h que nunca sobreestima el costo para llegar a la
meta. Tal h se llama una heurística admisible. Heurísticas admisibles son, por naturaleza optimista,
porque creen que el costo de resolver el problema es menos de lo que realmente es.

Esto transfiere el optimismo a la función f, así: Si su trámite, f (n) nunca sobrestima los costes reales de
la mejor solución a través de n.

Propiedades fundamentales

Complejidad

El problema es que, para la mayoría de los problemas, el número de nodos en el espacio de búsqueda del
contorno meta sigue siendo exponencial en la longitud de la solución. Aunque la prueba del resultado
está fuera del alcance de este libro, se ha demostrado que el crecimiento exponencial se producirá a
menos que el error en el heurístico no crece más rápido que el logaritmo de la ruta real de costos.

\h(n) -A*(n)|<0(log/.*(«)),

Optimalidad

Esto contradice la suposición de que G ^ _ no es el óptimo, por lo que debe ser el caso que nunca
A * selecciona un objetivo óptimo para la expansión. Por lo tanto, porque sólo ofrece una solución
después de haberlo seleccionado para la expansión, A * es un algoritmo óptimo. Localmente finito

Completud

Por lo tanto, el comando correcto es que A * es completa de forma local en grafos finitos (gráficos con
una finitos factor de ramificación), siempre hay alguna constante positiva 6 de tal manera que todos los
operadores los costes son por lo menos 6.

R2D2 contra las reinas caníbales y la ciudades de nombres raros.

Lo sé, el título esta medio bizarro, pero de lo que hablaremos aquí es resolver problemas de búsqueda en un árbol. Como ya sabrán los instruidos en el tema los clásicos problemas de ejemplo son:las ciudades (buscar un camino de 'x' ciudad a 'y' ciudad), los caníbales (3 caníbales, 3 misioneros, una lancha, 2 mujeres y un camino), las 8 reinas (reinas neuróticas que no se pueden ver ni en diagonal).

El problema que nos gustaría abordar es el de los caníbales, el problema completo es masomenos algo así:

En una apartada orilla del planeta Rigel VII existe un hermoso río cuántico cuyo brioso caudal no puede ser atravesado a menos que se haga uso de una lancha. En la orilla derecha del río hay 3 caníbales y 3 misioneros que necesitan cruzar al otro lado. Sólo que hay condiciones para que esto se pueda lograr, en la lancha antes mencionada sólo caben una o dos personas y para cruzarla de lado a lado forzosamente alguien debe de conducirla, al mismo tiempo de que si en cualquier lado hay más caníbales que misioneros, éstos ultimos serán cruelmente devorados.
Usted es mediador de la guerra intergaláctica de los caníbales Rigelianos y los Misioneros de Marte, debe de transportar hacia la embajada de las Galaxias Unidas en el lado izquierdo del río a todos los individuos sin causar ningún incidente político que desate la peor de las guerras de la galaxia, pero no está solo, oh no, tiene el poder de la programación y los algoritmos de búsqueda de su lado. Así que, ¡manos a la obra!

Tan simpatico que se ve

El primer paso para una misión exitosa, antes de abordar el algoritmo de búsqueda es la definición formal del problema, aquí yacen los cimientos de lo que será la resolución.


Primero se tienen que definir cuatro cosas:
-Un estado válido del problema.
-Operadores que marcan un cambio de estado.
-El estado inicial del problema.
-El estado objetivo del problema (a dónde queremos llegar).



Estado válido del problema.
Un estado válido es aquél que refleja la situación actual del problema, en éste caso debe definir la cantidad de caníbales y misioneros en cada lado así como la posición de la lancha, o en que orilla está. Esto lo podemos definir con:

# caníbales orilla izquierda
# caníbales orilla derecha
# misioneros orilla izquierda
# misioneros orilla derechaposición de la lancha

Como sabemos la cantidad total de caníbales y misioneros, que no varía, podemos obviar una orilla y remitirnos a simples restas para calcular la otra orilla y entonces el estado válido se resume a:
# caníbales
# misioneros
# lanchas en un lado


Operadores.
Dado el estado que definimos los posibles operadores que hacen un cambio de estado son:

-movimiento de lancha con un misionero
-movimiento de lancha con un caníbal-movimiento de lancha con dos misioneros
-movimiento de lancha con dos caníbales
-movimiento de lancha con un caníbal y un misionero


Estado inicial.
El estado incial es:
(1,3,3)

Donde 1 indica que en el lado presente está la lancha (derecho, si fuse un 0 la lancha estáen el lado ziquierdo), el primer 3 indica que hay 3 caníbalesen el lado derecho y el segundo 3 que hay 3 misioneros. (Si queremos saber cuántos caníbales o misioneros hay en el lado izquierdo simplemente hacemos la operación aritmética de resta para saberlo, dado que sabe que siempre existen 3 misioneros y 3 caníbales).


Estado Objetivo.

(0,0,0)

Dado que aquí la lancha está del otro lado, no hay caníbales ni misioneros en el lado derecho(todos están en el izquierdo).

BÚSQUEDA.

Ya que hemos definido formalmente el problema solo basta seguir este pseudo-algoritmo para encontrar la solución. Nótese que este algoritmo es capaz de resolver cualquier problema similar (8 reinas, ciudades,etc) siempre y cuando la definicion formal del problema sea correcta.
Además, mientras mas detalles tenga la formalizacion de los estados, la obtención de la busqueda sera mas facil, pero hayq ue observar un equilibrio pues estados muy grandes podrian agotar los recursos.


Algoritmo de búsqueda.

1.- Generar cola de Estados.
2.- Meter raíz (Estado inicial) en cola.
3.- Ciclo.
3.1.- Visitar siguiente Estado en la cola.
3.1.1.- Sacar el nodo de la cola.
3.1.2.- Prueba de objetivo.
Si el nodo es objetivo, regresar solucion.
Si no:
Generar todos los nodos hijos del nodo actual.
Meter hijos a la cola.
3.1.3.- Regresar a 3.


Este algoritmo no es el unico que existe, en la siguiente entrada se cubriran distintos tipos de algoritmos, sus características y definiciones.




Enhorabuena, hemos salvado la galaxia una vez mas ;)

Tuuutututututtutururrurtuuuuuuu (musiquilla triunfal)