Inteligencia artificial IV: Algoritmos genéticos

Hay una clase de problemas en los que la dificultad consiste en encontrar la mejor solución. El ejemplo típico es el problema del viajante: si tenemos un conjunto de ciudades y una serie de caminos que llevan de unas a otras, el problema consiste en indicarle a un viajante cual es el camino más corto que pasa por todas las ciudades.

Matemáticamente se ha estudiado muchísimo, y no se ha encontrado un algoritmo que resuleva este problema en un tiempo razonable. Este es un ejemplo de problema en el que se puede aplicar un algoritmo genético.

Los algoritmos genéticos no son más que una estrategia de programación que intenta imitar la selección natural. Cada generación es un conjunto de soluciones (no óptimas, ya que entonces tendríamos la solución deseada). Se empieza con unas cuantas soluciones del problema aleatorias (en el caso del problema del viajante, rutas escogidas de cualquier manera). Entonces, se obtiene la siguiente generación a partir de los mejores individuos (es decir, combinando las rutas más cortas obtendríamos otras creadas a partir de ellas). Los mejores individuos se combinan muchas veces. Los peores, se utilizan poco o se descartan.

Además, para calcular las siguientes generaciones, también se introducen mutaciones (es decir, cambios inesperados y normalmente bastante malos en cuanto a encontrar la solución) que sirven para no estancarse en soluciones que parecen óptimas pero que en realidad no lo son.

A base de calcular unas cuantas generaciones, se llega a soluciones cada vez mejores. A pesar de que es muy difícil resolver el problema exactamente por este método, las soluciones obtenidas son bastante buenas. Este método presenta la ventaja de que es muy general ya que se puede aplicar a una gran cantidad de problemas.

Como es más fácil entender las cosas viéndolas, puede que este vídeo sea muy clarificador:

(Las opciones de la derecha son diversos tipos de algoritmos genéticos distintos, con más o menos mutaciones).

Quadcóptero VII: Acelerómetro y magnetómetro

Ya hace un tiempo que pedí unos acelerómetros y magnetómetros para la estabilidad del quadcóptero, pero aún no me han llegado. Estos, como ya comenté en otro post, sirven para orientar el quadcóptero. Los dispositivos en cuestión son:

  • Un acelerómetro MMA8451QT: es de 3 ejes, soporta el protocolo I2C (lo cual quiere decir que se puede comunicar con el PIC mediante un protocolo digital), soporta frecuencias de hasta 800 Hz y tiene un encapsulado SMD.
  • Un magnétometro MAG3110FCR2: también tiene 3 ejes, soporta el protocolo I2C (es decir, es digitial), tiene un encapsulado SMD y una frecuencia de medidas de hasta 80Hz.

Ambos trabajan con bajo voltaje (entre 1.6V y 3.6V), por lo que habrá que utilizar un dido Zener o algo parecido. Lo que más me preocupa es que ambos tengan un encapsulado SMD, ya que nunca he utilizado componentes tan pequeños… tendré que arreglármelas de alguna manera.

Para que se vea un poco la complicación de soldar componentes de este tipo, aquí hay un video que demuestra la delicadeza con la que hay que hacerlo:

En cuanto me lleguen los motores o el acelerómetro y el magnetómetro prometo ponerme a trastear de una vez por todas.

Pequeños grandes retos

Hoy, como en los últimos 20 días, me toca postear. Y digo que me toca porque me propuse estar 30 días seguidos posteando.

Hoy me ha llamado la atención la historia de alguien que ha llevado esto de los retos un poquito al extremo: ha decidido grabar un segundo al día durante el resto de su vida. Calcula que a los 80 años (ahora mismo tiene unos 30) habrá grabado más de 5 horas de vídeo.

De momento ya tiene 6 minutos y 11 segundos grabados:

(Vía Microsiervos, con charla TED explicando el reto incluida)

Esto me ha hecho acordarme de otros retos como el de «Un día, una foto» de los cuales hay varios en youtube:

Son retos curiosos que asombran por la fuerza de voluntad que se demuestran. La verdad es que a su lado parece que postear una vez al día sea cosa de niños… ¡aunque para mi no está siendo nada fácil!

JNLP: Java Network Launching Protocol

Las aplicaciones escritas en Java tienen la capacidad de poderse ejectura en una gran cantidad de máquinas distintas (desde móviles y tablets hasta ordenadores con casi cualquier sistema operativo). Además, también está muy extendida su ejecución en páginas web como applets.

No obstante, a la hora de ejecutar alguna aplicación de escritorio en java las cosas no son tan fáciles. Sin ir más lejos, a nivel de usuario no es posible ejecutar un .JAR con windows ni con MacOS. Además, en linux la implementación de Java no está tan introducida (ya que Java no es libre).

Es por ello que el JNLP es un buen sistema para lanzar aplicaciones de usuario. Una aplicación que utilice la tecnología JNLP es una aplicación que puede abrirse desde internet como un simple link con extensión .JNLP (que en realidad es un archivo .XML con una estructura predefinida), que descarga la última versión del programa (si es necesario) y lo ejecuta. Un ejemplo de código para usar el sistema JNLP se puede ver en la wikipedia.

Para probar un poco, he creado un pequeño programa con Netbeans que implemente el JNLP. En Netbeans implementarlo es tan fácil como activar el Java Web Start en las propiedades del proyecto en cuestión, y él solo se encarga de crear el archivo .JNLP.

El código fuente que he utilizado ha sido:

package pruebajnlp;

import java.awt.FlowLayout;
import javax.swing.JFrame;
import javax.swing.JLabel;

public class Main {
public static void main(String[] args) {
JFrame f = new JFrame();
JLabel b = new JLabel(«Bienvenido!  (Prueba JNLP)»);
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setLocation(100, 100);
f.setSize(200, 100);
f.setLayout(new FlowLayout());
f.getContentPane().add(b);
f.setVisible(true);
}
}

Y el resultado se puede comprobar pinchando aquí (es necesario abrirlo con «Java Web Start», que si no lo tienes puedes conseguirlo aqui). Esta es una prueba más de las facilidades de Java a la hora de programar fácilmente aplicaciones reales.

Todos los archivos (código fuente, ejecutable .JAR y archivo .JNLP) están comprimidos aqui:

Ejemplo JNLP (Java)
Ejemplo JNLP (Java)
PruebaJNLP.zip
5.3 KiB
93 Downloads
Details

In Circuit Serial Programming (ICSP)

ICSP es un método para programar PICs muy cómodo. Habitualmente para programar un PIC hay que sacarlo del circuito en el que está, ponerlo en un programador (como el TE-20), conectar el programador al PC, programarlo y volver a colocar el PIC en el circuito correspondiente.

Todo eso se acabó con ICSP. Con este método, basta con colocar algunos contactos en el circuito en el que esté el PIC. Se basa en que para programar el PIC en realidad no son necesarios más que unos cuantos pines. Por tanto, con tal de utilizar esos (y tener un poco de cuidado en el resto del circuito para evitar incompatibilidades) es posible programar el PIC.

Los pines necesarios para programar PICs dependen del modelo utilizado:

Pines ICSPAdemás, con un pequeño circuito (sin alimentación externa) es posible crear el programador «en linea». El esquemático en cuestión es el siguiente:

ICSP - Esquemático

Además, en el circuito en el que se coloca el PIC deben estar colocados los siguientes componentes:

ICSP - Esquema PIC

El único problema es que hay que ir con un poco de cuidado con algunas cosas:

  • El voltaje escasea (teóricamente deberían ser 13V, pero el puerto serie sólo da 12V). Por eso, hay que conseguir que los cables sean lo más cortos posibles.
  • No se pueden poner circuitos activos en la patilla conectada al Vpp del conector ICSP.
  • Se debe aislar el pin Vdd del PIC del resto del circuito durante la programación.

Seguro que esto me es muy útil cuando tenga que programar el quadcóptero, porque tendré que reprogramar los PICs una y mil veces!

A ver si mañana me animo y lo pruebo!

(imégenes sacadas de aqui).

Computación distribuida

Hay problemas muy, muy difíciles de resolver. Repito, muy difíciles. Evidentemente, son problemas que no se resuelven a mano, sino con la ayuda de computadores. El gran inconveniente es la cantidad de recursos ingente necesarios para resolverlos (que se traduce en una inversión económica enorme). La solución es muy simple: la computación distribuida.

La computación distribuida consiste en dividir un problema en subproblemas mucho más pequeños y resolverlos por partes. Esto tiene la ventaja de que puedes utilizar ordenadores distintos para cada subproblema, y (aqui viene la idea original) es posible utilizar ordenadores de usuarios voluntarios en el tiempo en el que no se están usando. Es algo así como dejar prestado tu procesador mientras no se utilice.

Cualquiera puede hacerlo descargándose un programa (como BOINC Manager, entre otros) para decidir a que proyectos ayudar. Además, el programa sólo actúa cuando tu ordenador está en reposo (es decir, sin uso). Por tanto, no te quita nada, pero aporta capacidad de cálculo. Existen una gran variedad de proyectos de este tipo:

En definitiva, me parece una gran idea ya que no cuesta nada y puede ayudar a resolver problemas abiertos. Ahí lo dejo ;).

Reconocimiento Óptico de Carácteres (OCR)

Un sistema OCR (de las siglas en inglés de Reconocimiento Óptico de Carácteres) es un software que se encarga de leer el texto de una imagen, tanto escrito a mano como mecanografiado.

Son unas aplicaciones útiles y más utilizadas de lo que parece: en los aparcamientos que leen la matrícula del coche, en el software de descarga automática de archivos (que tienen que resolver los captchas), en el escaneo de documentos, etc.

Hoy en día hay una gran variedad de software (tanto libre como comercial) que se ocupa de esta tarea, a pesar de que hasta la fecha no se ha conseguido crear ningún programa realmente eficaz. De entre las distintas opciones están:

  • GOCR: uno de los más potentes, desarrollado (y posteriormente liberado) por HP.
  • JavaOCR: el único decente escrito en Java.
  • Tesseract-OCR: desarrollado con el apoyo de Google.
  • Online OCR y Free OCR: ambos completamente online.

Un software OCR se basa en una serie de procesos:

  • El primer paso es aplicar un preprocesamiento sobre la imagen a convertir:
    • Se convierte la imagen a blanco y negro para evitar información no necesaria.
    • Se detectan las palabras y las letras, y éstas últimas se separan unas de otras.
    • A cada letra se le aplica un proceso de adelgazamiento: se van haciendo los trazos finos hasta que solo tienen un pixel de anchura.
  • Una vez que la imagen se ha preprocesado, se utiliza algún método de comparación de patrones para reconocer la letra.
  • Una vez detectadas todas las letras se puede ir un paso más allá y comprobar si la palabra obtenida tiene significado (si existe en un diccionario) para comprobar (o no) la eficacia de la detección.

Algunos de los métodos de comparación con patrones son: la comparación bit a bit de la imagen con cada uno de los patrones a reconocer, la minimización de alguna función (como una métrica definida sobre las imágenes a reconocer), o algunas técnicas más complicadas como aplicar transformaciones a la imagen: la transformada de Fourier discreta, la transformada de Hough, …

Para acabar, una excelente charla TED sobre para que se pueden utilizar los captchas:

Instrumentación electrónica: Osciloscopio III

Siguiendo con el post anterior, he estado probando el circuito montado con un ejemplo real: una señal cuadrada de 20 ms de período (con una frecuencia fundamental 50Hz). La idea es introducir la señal cuadrada con un PIC y medirla con el osciloscopio en el PC.

El programa utilizado para ello es el Soundcard Oscilloscope, que es un programa para Windows (con licencia gratuita para actividades no comerciales). La verdad es que es un programa bastante completo. ya que también incorpora un generador de funciones.

La primera forma de onda que he obtenido cuando todo estaba conectado (tal y como se explica en el post anterior) ha sido:

Osciloscopio (T=20ms)

Que no se parece demasiado a un pulso rectangular… después de pensar un poco en cual era el problema, ¡me he dado cuenta de que las tarjetas de sonido tienen en la entrada un elemento que impide el paso de corriente contínua! Por eso la única forma de onda que se observa son los picos positivos y negativos cada 10 ms.

Es decir, el osciloscopio solo es capaz de medir corrientes alternas. He intentado añadirle un condensador a la circuitería pero no ha servido de gran cosa, ya que atenuaba demasiado la señal recibida. Para comprobar de una vez por todas si funcionaba correctamente tenía varias posibilidades:

  • Aumentar la frecuencia del PIC y ver que ocurría.
  • Crear una senoide más o menos pura (por ejemplo, filtrando la señal cuadrada con un filtro apropiado, que solo deje pasar un harmónico).
  • Utilizar alguna otra forma de onda, como una triangular.

Finalmente, me he decidido por la primera opción, ya que era la más fácil de implementar (no necesitaba ni un conversor A/D ni una reprogramación estructural del PIC). Los resultados obtenidos han sido:

Con un período de 350 µs (harmónico principal a 2.85 kHz):

Osciloscopio (T=350us)

Y con un período de 100 µs (harmónico principal a 10 kHz):

Osciloscopio (T=100us)

En esta última captura de pantalla se puede observar como la tarjeta de sonido capta una señal que interpreta como una senoide casi pura. Es importante darse cuenta de que la tarjeta de sonido muestrea a 44.1 kHz, y por tanto solo es capaz de detectar señales hasta los 22 kHz. Como la señal cuadrada tiene harmónicos en múltiplos de 10 kHz, se detectan tan solo dos de los harmónicos: el de 10 kHz y el de 20 kHz. De ahí viene el hecho de que la forma de onda se vea tan claramente senoidal.

De todo esto, yo creo que se puede deducir que el circuito asociado parece estar bien diseñado, a pesar de que el osciloscopio sólo será capaz de detectar señales sin componente contínua.

 

Instrumentación electrónica: Osciloscopio II

La idea de montar un osciloscopio con la tarjeta de sonido ya la comenté aqui. Le he estado dando vueltas al asunto y por fin me he decidido a probarlo. He tenido que cambiar el diseño de la electrónica, ya que faltaba un diodo (estaba protegiendo solo contra tensiones positivas, no contra tensiones negativas).

El diseño nuevo es:

Esquemático - Osciloscopio II

Además, también le he añadido un divisor de voltaje para obtener un rango de entradas más amplio. El divisor es 1:10, y se puede conectar y desconectar.

Para probar el correcto funcionamiento del circuito, he programado un PIC para que encienda y apague un LED cada 10 ms. A simple vista no se aprecia por la persistencia de la visión, que es la capacidad del ojo de mantener durante unos instantes la última imagen recibida. La idea es comprobar en el osciloscopio que se recibe una señal de pulsos del tipo:

Pulso rectangularCon un período de aproximadamente 20 ms.

He montado el circuito en la protoboard y tiene buena pinta:

Protoboard - Prueba osciloscopio PC

Se pueden apreciar dos bloques bien distinguidos: el circuito que se encarga de crear la señal a medir (el PIC) y el diseñado propiamente para el osciloscopio (el potenciómetro). No he puesto el divisor de tensión en la protoboard, ya lo pondré en el diseño final.

Ahora mismo estoy instalando los drivers de la tarjeta de sonido y el software que actúa como osciloscopio, pero no lo podré probar hasta dentro de un par de días. Cuando haya novedades aparecerán por aqui!

Useless machine

Useless machine, o máquina inútil. No pienso describirla porque un vídeo vale más que mil palabras:

Es una tontería… pero la idea me gusta! Puede que hasta algún día con tiempo me anime a crear una. La verdad es que a pesar de su (in)utilidad se pueden encontrar bastantes diseños:

(click) (click) (click) (…)

 

(Bonus: sin alimentación electrónica, 100% manual)

 

 

Arduino (y por qué no lo uso)

Arduino es un pack completo para jugar con microprocesadores. Es un pack porque en realidad es el conjunto de placa, software y programas prediseñados. Es algo así como una herramienta muy potente para utilizar microprocesadores. Últimamente, con la construcción del quadcóptero me estoy dando cuenta de la cantidad de gente que utiliza arduino para sus modelos.

Placa arduinoEn internet se pueden encontrar miles de diseños y una comunidad muy activa y muy creativa. Es algo que está teniendo mucho tirón, gracias a la facilidad que da para construir diseños autónomos.

Tengo que reconocer que nunca lo he utilizado… pero no me parece algo demasiado útil, al menos para mí. Creo que es un avance muy grande en la accesibilidad a este tipo de dispositivos, ya que hay mucha gente que quiere ver resultados, que lo que le interesa es construir un modelo de robot, o crear una alarma, o cualquier otra cosa que se te pueda ocurrir.

Pero en mi caso no es así. Yo opino que la gracia de dedicarse a construir un quadcóptero es construirlo, y no que el último día vuele (o no). Está muy bien eso de que es todo libre (tanto el diseño de la placa como el software son gratuitos), pero la gracia de crear algo con el objetivo de aprender (como es mi caso) no es hacerlo lo más automáticamente posible, sino de la manera más flexible y potente.

Hace poco oí una opinión que me llamó la atención. El comentario venía a ser algo así como «hoy en día es tan fácil instalar Linux como darle al botón siguiente varias veces… y eso parece bueno, pero no estoy tan seguro de que lo sea». No se hasta que punto tiene razón o no, pero en cierto modo comparto esta filosofía a lo principito.

La eversión de la esfera tridimensional

Evertir una esferal consiste en darle la vuelta. Es decir, modificarla  para conseguir que superficie exterior y la interior se intercambien.

En términos más matemáticos, este es un problema topológico, que consiste en encontrar la manera de hacer este cambio sin romper la esfera en ningún momento. Intuitivamente parece imposible, pero existe un resultado positivo: la paradoja de Smale.

Ésta dice que aplicando transformaciones topológicas permitidas (esto es, traslaciones, homotecias, deformaciones y autointersecciones, pero no cortes) sí es posible evertir la esfera… aunque no es nada sencillo:

La eversión de la esfera empieza en el minuto 13. Aunque físicamente parezca imposible, la única trampa que se hace es permitir las autointersecciones. El vídeo es bastante curioso.

(Vía Gaussianos)

http://gaussianos.com/la-paradoja-de-smale-o-como-evertir-una-esfera/

Instrumentación electrónica: generador de funciones

El otro día me dediqué a buscar la manera de construir un osciloscopio casero. Realmente, será tan básico que funcionará casi como un frecuencímetro, pero con eso me basta. Hoy vengo con algo un poco más ambicioso: la construcción de un generador de funciones con un PIC.

La idea es utilizar un PIC 16F84A. También habría que añadir un conversor D/A, cuya implementación es muy sencilla: basta una red de resistencias como la siguiente:

Conversor D/A (red de resistencias)A esta misma red de resistencias se le tendría que añadir algún filtro pasabajos en el amplificador sumador.

Dado que la frecuencia del PIC es de 20Mhz (esto es, es capaz de ejecutar 5.000.000 instrucciones por segundo), la velocidad real del generador de funciones llegará a 1 Mhz, aproximadamente, si la programación es óptima. El PIC tiene suficiente memoria como para tabular las seniodes y así ahorrar tiempo.

En cuanto a los puertos, mi idea es utilizar el puerto B (8 pines) para la salida del generador, y el puerto A (4 pines) para seleccionar función (senoide, cuadrada, etc) y frecuencia. La amplitud, si me decido a ponerle un regulador de amplitud, será externa (es decir, amplificará el señal que salga del conversor D/A), así que el PIC ni se entera de que está.

Supongo que existirán cosas más simples para hacer lo que yo quiero, y puede que utilizar un PIC para esto sea matar moscas a cañonazos, pero ya que estoy empezando a programar PICs me gustaría utilizarlos un poco.

 

 

Desafíos de 30 días

Últimamente he estado actualizando mucho el blog… y no es por casualidad. Hace poco vi un vídeo muy recomendable del TED: una conferencia en la Matt Cutts expone qué son los desafíos de 30 días, y por qué pueden ayudarte a hacer cosas que nunca antes has hecho.

El vídeo es:

(Enlace directo)

Espero que lo disfrutéis y que os sea útil!

Instrumentación electrónica: Osciloscopio I

A la hora de ponerse a montar circuitos, muchas veces me doy cuenta de que para comprobar su correcto funcionamiento no bastan unos LEDs y un voltímetro/amperímetro. Por ejemplo, a la hora de montar un oscilador no soy capaz de comprobar que oscile a la frecuencia que quiero.

Es por eso que he decidido montar algunos aparatos básicos para poder trastear un poco. Ahora mismo, se me ocurren varias cosas que me gustaría tener disponibles:

  • Una fuente de alimentación de voltaje variable.
  • Un generador de funciones básicas (sinusoides, pulsos cuadrados, pulsos rectangulares).
  • Un osciloscopio.
  • Un capacímetro y un inductómetro.

Evidentemente, no son necesarias todas estas cosas… pero arreglan la vida bastante. Es por eso que he decidido buscar la manera de montarme un osciloscopio. A priori, parece lo más complicado de todo, pero utilizando un ordenador la cosa se simplifica bastante, ya que las tarjetas de sonido de los ordenadores tienen buenos conversores D/A (buenos hasta unos 20 Khz). Por tanto, con algo de circuitería externa y algún software que lo permita, es posible utilizar un osciloscopio (limitado a tan solo 20 Khz… pero osciloscopio igualmente).

He estado buscando esquemáticos muy sencillos para implementar, pero no he encontrado ninguno que me guste, así que única solución que he encontrado es diseñar uno sencillito. El circuito en cuestión es el siguiente:

Circuito osciloscopio(¡diseño antiguo! reemplazado aqui)

Con este diseño no podré medir el voltaje, pero es una manera básica y barata de obtener algunas medidas útiles. La única función del circuito es la de proteger la entrada de sonido para no cargármela por exceso de voltaje. La protección consiste en que cuando me paso de voltaje aplicado en la entrada, el diodo empieza a conducir electricidad y la tensión en la entrada de audio no supera nunca los 0.7 V.

No se a ciencia cierta que tal se comportará. En cuanto lo pruebe comprobaré si funciona como toca.

En cuanto al software utilizado para ello, tengo planeado probar el XOscope (para Linux).