Inteligencia artificial aplicada a microcontroladores Parte #02
Buenos días estimados lectores. En el día de hoy continuaremos con la segunda parte se inteligencia artificial aplicada a microcontroladores.
Para aquellos que aún no están en contexto, a través del siguiente link podrán ver la primera parte. Analizando la entrada anterior a este tema pudimos ver que de alguna forma un microcontrolador nos daba la posibilidad de poder integrar una red neural artificial, o en general algún método de la inteligencia artificial para optimizar algún tipo de proceso. Quedamos a la espectativa de saber si es posible o no el implementar esto; para fortuna de todos si. Resulta que tras un tiempo de consultas y estudios, pude observar que hay algo llamado programación dinamica; y aquí se encuentra un aliciente pero no el unico de la solución de este contexto.
 |
| Mapa de problema sobre diligencias |
¿Qué es la programación dinámica?
La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas. El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.
Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:
- Dividir el problema en subproblemas más pequeños.
- Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.
- Usar estas soluciones óptimas para construir una solución óptima al problema original.
- Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.
Decir que un problema tiene subproblemas superpuestos es decir que se usa un mismo subproblema para resolver diferentes problemas mayores. Por ejemplo, en la sucesión de Fibonacci (F3 = F1 + F2 y F4 = F2 + F3) calcular cada término supone calcular F2. Como para calcular F5 hacen falta tanto F3 como F4, una mala implementación para calcular F5 acabará calculando F2 dos o más veces. Esto sucede siempre que haya subproblemas superpuestos: una mala implementación puede acabar desperdiciando tiempo recalculando las soluciones óptimas a problemas que ya han sido resueltos anteriormente.
Esto se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama memoización (no confundir con memorización; en inglés es llamado memoization). Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio. En algunos casos, podemos calcular las soluciones a problemas que de antemano sabemos que vamos a necesitar.
Cuando hablamos de optimizar nos referimos a buscar alguna de las mejores soluciones de entre muchas alternativas posibles. Dicho proceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución correcta. Si, dada una subsecuencia de decisiones, siempre se conoce cuál es la decisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz. En otros casos, aunque no sea posible aplicar la estrategia voraz, se cumple el principio de optimalidad de Bellman que dicta que «dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima». En este caso sigue siendo posible el ir tomando decisiones elementales, en la confianza de que la combinación de ellas seguirá siendo óptima, pero será entonces necesario explorar muchas secuencias de decisiones para dar con la correcta, siendo aquí donde interviene la programación dinámica.
Contemplar un problema como una secuencia de decisiones equivale a dividirlo en problemas más pequeños y por lo tanto más fáciles de resolver como hacemos en Divide y Vencerás, técnica similar a la de programación dinámica. La programación dinámica se aplica cuando la subdivisión de un problema conduce a:
 |
| Ejemplo sobre problema de diligencia-programación dinámica |
- Una enorme cantidad de problemas.
- Problemas cuyas soluciones parciales se solapan.
- Grupos de problemas de muy distinta complejidad.
Pero como vimos anteriormente en la definición de programación dinámica, podemos deducir que unos de los problemas fundamentales al momento de intentar programar un algoritmo de forma dinámica es la cantidad de memoria que se necesitaría para poder programar los distintos subproblemas que conllevaría la implementación. Pero bueno, para esto hay una solución y es la implementación de una memoria flash externa controlada por algún periférico SPI que posea el microcontrolador. Entonces, en la actualidad. ¿porqué no se implementan este tipo de programación?, por una sencilla razón, y es que los compiladores no estan optimizados para este tipo de programación. Entonces, ¿si no están optimizados para este tipo de programación, porqué no los optimizan?. Resulta que este tipo de programación no es muy eficiente para distintas situaciones, por tal razón, no es viable optimizar los microcontroladores para estos tipos de algoritmos; pero bueno, no todo son malas noticias, hay situaciones que poco a poco se van presentando en la industria de una manera exponencial y que sugiere la nesecidad de implementar algún tipo de algoritmo autónomo que dependiendo de las variables, pueda decidir la mejor solución sin necesidad de intervención humana. Es en este punto donde entra a jugar las DNN (Deep Neural Networks), que son algoritmos entrenados para para realizar tareas específicas. Anteriormente mencioné que si se puede implementar inteligencia artificial en los microcontroladores; básicamente se puede hacer algunos arreglos, crear compiladores que se ajusten a la necesidad de un algoritmo tan especializado como lo son como los de programación dinámica, pero como dije anteriormente el tiempo es un recurso que no podemos olvidar, y si es para un proyecto de baja escala, posiblemente no valga la pena ponerse a realizar este trabajoso proceso.
Una solución actual y que es muy viable es implementar una DNN, que en cuestión ya es posible. Veremos este apartado de implementación de redes neurales en microcontroladores en una tercera parte para poder tratar mejor el tema.
Aquí podrás ver la Parte #03.
Escrito por: Breismam Alfonso Rueda Díaz
Fuentes:
- http://www.konradlorenz.edu.co/images/stories/suma_digital_matematicas/Programacion%20Dinamica.PDF
- https://www.st.com/content/st_com/en/about/innovation---technology/artificial-intelligence.html
- Xumari, G.L. Introduction to dynamic programming. Wilwy & Sons Inc., New York. 1967.
Bien muchachos, esto es todo por hoy. Estén pendientes de mi canal, de mi blog y de mi pagina de Facebook para más contenido.
Twitter: https://twitter.com/BreismamR
Cualquier duda, trabajo, tutoria personalizada por correo electrónico o pagina en facebook:
Correo: ElectronicaLibreXC@outlook.com
