Álgebra Geométrica en las Ciencias de la Computación

Las Ciencias de la Computación tienen sus raíces en las matemáticas. De este hecho dan cuenta el Análisis de Algoritmos, la Geometría Computacional, los Métodos Numéricos y muchas más ramas de las Ciencias de la Computación. No es de sorprendernos que en éstas ramas existan problemas computacionales que encuentran su mejor expresión en lenguaje matemático. Resulta imprescindible contar con las herramientas matemáticas adecuadas que nos permitan expresar de forma simple y concisa ésta clase de problemas para así poder encontrar soluciones computacionales óptimas.

En éste post presento una nueva herramienta matemática, considerada por no pocos matemáticos y físicos como la más poderosa disponible a la fecha. Se trata de la denominada Álgebra Geométrica (en inglés, Geometric Algebra). El Álgebra Geométrica (AG) es una teoría matemática avanzada y a la vez una herramienta práctica para la representación y solución de problemas geométricos que impacta directamente en las Ciencias de la Computación, pero especialmente en las áreas de Geometría Computacional, Computación Gráfica y Visión Computacional.

Sus orígenes se remontan hasta hace más de 100 años. Fue concebida por el matemático inglés William K. Clifford (1845-1879) en la década de 1870 y desde entonces ha venido impactando en varias áreas de la Matemática, la Física y la Ingeniería. Recientemente ha sido introducida en las Ciencias de la Computación a través de conferencias como ACM SIGGRAPH, AGACSE (Applied Geometric Algebra for Computer Science and Engineering), GRAVISMA, entre otras.

Orígenes del Algebra Geométrica

Si bien el álgebra geométrica (conocida también como álgebra de Clifford) fue concebida por W. K. Clifford a fines del siglo XIX, no todo el crédito es suyo. El álgebra inventada por Clifford se basó fundamentalmente en las teorías del matemático alemán Hermann G. Grassmann (1809-1877) y en las del físico irlandés Sir William Rowan Hamilton (1805-1865). La muerte prematura de Clifford, a sus 33 años, cortó de golpe los avances en la teoría del álgebra geométrica ya que sus contemporáneos no la supieron interpretar y terminaron adoptando un álgebra mucho más simple, pero también mucho más limitada, como es el álgebra vectorial introducida por el físico norteamericano Josiah W. Gibbs (1839-1903) y el físico inglés Oliver Heaviside (1850-1925). Desde entonces, el álgebra vectorial y el cálculo vectorial fueron el estándar de facto tanto para física como para ingeniería, en cuanto a las aplicaciones geométricas del álgebra lineal concierne.

Recientemente, el físico norteamericano David Hestenes (1933-presente) buscando mejores representaciones matemáticas para la mecánica cuántica y la relatividad se dio cuenta de que el álgebra de Clifford casi no había sido explorada en sus aspectos geométricos (el sentido original que le trató de dar su creador W. K. Clifford) y comenzó el redescubrimiento de un “álgebra universal” que está conduciendo a la reformulación de la física cuántica: el álgebra geométrica.

¿Qué es y para qué sirve?

Clickea aquí para leer el artículo completo.

Vectores y Multivectores

Clickea aquí para leer el artículo completo.

Implementaciones y Eficiencia

Clickea aquí para leer el artículo completo.

Advertisements

Aplicaciones de Aprendizaje por Refuerzo en Video Juegos

Reinforcement Learning es una metodología que forma parte del campo de Machine Learning y de las Ciencias Cognitivas. Los algoritmos de Reinforcement Learning permiten a uno o varios agentes tomar decisiones optimas de acuerdo a su conocimiento del ambiente. En Reinforcement Learning, el agente aprende gracias a técnicas de ganancia y castigo. El agente aprende a realizar tareas a través de la repetición de acciones correctas e incorrectas. Es así que cada acción que realiza el agente tiene asociada una ganancia.

La precisión del aprendizaje está en función del tiempo que tiene para aprender. En general, un aprendizaje rápido le dará una mala representación de la tarea que realizará, mientras que un aprendizaje a largo plazo le dará una mejor representación y por lo tanto un mejor resultado en la tarea que realizará. Todas las metodologías de RL requieren un balance entre la búsqueda de nuevas estrategias y el uso del conocimiento ya adquirido.

Cuando un agente usa el conjunto de acciones que ya realizó y su ganancia como premisas para escoger una nueva acción a realizar, entonces estamos hablando de “Explotación”. Cuando un agente está buscando nuevos caminos, estamos hablando de “Exploración”. Un buen aprendizaje requiere la combinación de estrategias de Explotación tanto como de Exploración.

Reinforcement Learning es usado frecuentemente para el aprendizaje de políticas de control y para tomar decisiones en casos específicos donde se aplican esas políticas. En realidad virtual se esta utilizando Reinforcement Learning como modelo para generar automáticamente controladores para tareas típicas en 2D y 3D. Se investiga la animación del comportamiento de agentes autónomos que se desenvuelven como humanos virtuales y son capaces de tomar decisiones. La industria de los video juegos es un campo de prueba de muchos algoritmos de control, (por ejemplo control de la navegación de vehículos) y de aprendizaje de estrategias. El objetivo de este post es hacer una revisión del estado del arte de los algoritmos de control y aprendizaje de estrategias desarrollados bajo el paradigma de Reinforcement Learning usados en Video Juegos.

El post completo es de 36 páginas, por lo que preferí editarlo en PDF, descárgalo aquí.

Aproximación de curvas con BSpline

Comienzo este Blog con uno de los temas fundamentales de la Computación Gráfica, las curvas y superficies están en el corazón de la disciplina y entre las representaciones más poderosas para curvas y superficies tenemos a la BSpline.

Como programador de gráficos creo que no hay mejor forma de conocer este hermoso tema que poner las manos en la masa. En este post voy a mostrar cómo aproximar e interpolar datos n-dimensionales con BSpline usando el método de los mínimos cuadrados. Mostraré tanto las ecuaciones como el código fuente y trataré de hacer algunos paralelos entre ellos, las optimizaciones de código las dejaré como ejercicio para los lectores :).

BSpline Fitting
Aproximación de BSpline

¿Para qué aproximar datos con BSpline? en la práctica la aproximación BSpline se usa para:

  • Poder suavizar datos ruidosos (e.g. series de tiempo)
  • Generar curvas C^n continuas (cuyas n diferenciales existan) lo cual es importante para optimización, si se quiere encontrar los mínimos y máximos por ejemplo
  • Comprimir datos reduciéndolos a unos pocos puntos de control
  • Poder modificar los datos manteniendo continuidad C^n a través de puntos de control
  • Animar objetos a través de trayectorias suaves y continuas

Es necesario distinguir la aproximación de la interpolación. Una curva aproximada no necesariamente pasa por los todos los puntos (pero trata de acercarse), mientras que una curva interpolada si pasa por todos los puntos. La interpolación BSpline se utiliza para computar todos los “datos intermedios” conociendo sólo unas pocas muestras, por ejemplo permite computar colores intermedios en una fotografía, animaciones intermedias en una secuencia de key frames, deformaciones intermedias en una secuencia de deformaciones, transformaciones intermedias, etc.

Pero antes de entrar de lleno a la aproximación repasemos los conceptos básicos de BSplines y su formulación.

Continue reading