Investigadores del DC desarrollaron una técnica innovadora para construir automáticamente componentes de software.

Investigadores del DC lograron caracterizar los modelos de interacción en entornos no deterministas con observabilidad parcial y desarrollaron una técnica de síntesis de controladores que permitiría construir automáticamente componentes de software para ejecutar en esa clase de entorno.

El trabajo fue publicado a través del artículo “Interaction Models and Automated Control under Partial Observable Environments» (Modelos de Interacción y Control automatizado bajo Entornos Parcialmente Observables) en la revista IEEE Transactions Software (Volume: 43, Issue: 1, Jan. 1 2017), una de las publicaciones más prestigiosas del área. Los autores del artículo pertenecen al área de Ingeniería de Software: Daniel Ciolek (doctorando), Víctor Braberman (investigador y director del grupo LAFHIS), Nicolás D’Ippolito (investigador), Nir Piterman (investigador y colaborador invitado de la Universidad de Leicester) y Sebastián Uchitel (investigador y director del grupo LAFHIS).

La síntesis de controladores consiste en la generación automática de modelos de comportamiento de modo que teniendo en cuenta la forma en la que interactúan estos modelos con su entorno se satisfagan sus objetivos. El modelado de comportamiento es ampliamente utilizado en el diseño de sistemas y resulta útil para descubrir errores de software en etapas tempranas de proceso de desarrollo. Para este trabajo, los investigadores del DC consideraron los protocolos de comunicación subyacente que pueden encontrarse en diferentes modelos de interacción, basados en estados y transiciones, y qué tipo de problemas podrían resolverse con o sin ese protocolo. En este caso, se trata de preguntarse si el software que se está intentando sintetizar puede asumir ese protocolo.

Con el fin de conocer más sobre el artículo, el DC entrevistó a Daniel Ciolek:

¿Cuál es el principal aporte que presenta este artículo?

El aporte más importante es la caracterización de los modelos de interacción. Hasta ahora en el área de Síntesis de Controladores, cuando se da el caso de entornos con una observabilidad parcial (donde hay información que deducir del entorno), no se había considerado la disponibilidad de ciertos protocolos de comunicación subyacente que pueden simplificar el problema en algunos casos. Si uno quiere construir automáticamente un software que haga la consulta, la pregunta sería si este mecanismo de síntesis tiene en cuenta las características del protocolo subyacente o no las tiene en cuenta. Si no las tiene en cuenta va a estar intentando resolver un problema más difícil del que tiene que resolver, porque el protocolo subyacente le resuelve algunos problemas.

Entonces lo que hicimos fue caracterizar este proceso. Identificamos dos modelos de interacción relativamente comunes (Autómata de Interfaz y Autómata de Interfaz Débil) y describimos sus algoritmos con o sin protocolo subyacente.

¿Podrías dar un ejemplo?

En el Paper tenemos un buen ejemplo que es una agencia de viajes en un servidor web, que puede estar en un estado donde se espera que el usuario haga una reserva o que haga una compra directa. Pero no se sabe el estado del servidor en cada momento dado. Si no se cuenta con un protocolo subyacente, no se sabe qué mensaje, que consulta enviar y si se envía el mensaje incorrecto se puede llegar a generar un error.

La idea es que este componente nuevo se construya automáticamente, que esté incluido dentro del software. Entonces nos preguntamos si se puede construir ese componente automáticamente, que en este caso va a depender de si existe un protocolo subyacente. Si el software que estamos intentando sintetizar puede descubrir cuáles son los mensajes que están disponibles en la agencia de viajes (Reservar o Comprar), toma la decisión en función de este descubrimiento. Ve el estado en que está disponible y usa ese mensaje. Si no llega a descubrir cuáles son los mensajes disponibles, quizás exista una ingeniería más grande para descubrirlo.

Y en cuanto a los problemas de control con observabilidad parcial, ¿podrías comentar los aportes más importantes?

Con una demostración más simple, el trabajo evidencia que los problemas de control con observabilidad parcial son equivalentes a problemas no deterministas. Existen ciertos elementos del ambiente que no se pueden apreciar, por ejemplo si se está en una computadora muy lejana no se puede saber en qué estado está en ese momento el servidor.

Otra demostración del trabajo es que todos estos problemas se pueden reducir a un problema determinista y con observabilidad total. Pero hay un fuerte incremento de complejidad en este punto.

Imaginemos el caso de un robot que tiene 10 cajas y en una de las cajas debe encontrar una bomba. Pero no sabe dónde está la bomba. Hay información desconocida, que se debe ir descubriendo. En ese caso se trata de observabilidad parcial, porque no se tiene información completa del estado del problema. Lo que tendría que hacer el controlador que queremos sintetizar es un robot que abre caja por caja y mira adentro de cada una de las cajas hasta que encuentra el explosivo.

En el caso de la agencia de viajes, o de una compañía aérea, cuando el usuario desea sacar un pasaje si el avión está vacío, desde el momento que se le ofrece el pasaje hasta que lo compre, le puede dar un tiempo para tomar la decisión. En ese caso puede reservarlo, por ejemplo, por un día. Ahora bien, cuando los asientos se van llenando y el avión está casi completo, reservar al usuario ese pasaje por un día significa que no se lo puede ofrecer a otro cliente porque el avión está prácticamente lleno. En ese caso el software puede tomar una decisión interna, como ser: a partir de la carga del 75% del avión, dejo de ofrecer el paso de reserva. Allí pasaría al estado de compra directamente. Y ahí competiría con los otros que están tratando de comprar directamente, entonces puede fallar. En ese caso, el servidor de la agencia de viajes, en el momento en que vendió el 75% del vuelo, hizo un cambio interno y desconocido en su estado (tomó la decisión de manera completamente privada sin que nadie lo pueda saber) de dejar de ofrecer el paso de reserva.

Entonces cuando un controlador, un nuevo software, se quiere conectar, no puede saber en qué estado está el servidor en ese momento, ya que no sabe de antemano si le va a ofrecer el paso de reserva o de compra directa. Por ello si uno tiene el protocolo subyacente, en algún momento cuando llegue ese paso lo va a poder descubrir. Porque se puede conectar al servidor web, preguntarle si tiene un pasaje para esa fecha y recién cuando responda eso se puede preguntarle si está reservando o vendiendo.

El protocolo de comunicación nos brinda un conocimiento adicional en el momento que se llega al punto en el que se debe ejecutar esa acción de no saber si está disponible un estado o el otro. No brinda esa información de antemano sobre la transición de un estado al otro. Si la diera desde un principio el problema sería más sencillo.

¿Cuál es la diferencia entre los modelos de interacción fuertes y débiles?

Creo que la forma más fácil de explicarlo es que el modelo de interacción Autómata de Interfaz Fuerte no asume un protocolo de comunicación subyacente. En cambio, el Autómata de Interfaz Débil sí asume un protocolo subyacente. Por ende, el primero tiene que resolver un problema más difícil porque dispone de menos información pero el segundo puede descubrir más información del ambiente.

Entonces el problema de la agencia de viajes, ¿con qué modelo se resuelve?

Se resuelve con el modelo débil, que asume un protocolo subyacente, pero no se puede resolver con el fuerte.

Por último, ¿podrías dar un ejemplo de problema que se resuelva con el Autómata de Interfaz Fuerte?

Tenemos otro caso de estudio que es un robot guardia que tiene que patrullar un galpón, en donde hay obstáculos que bloquean su visión. El robot, si uno lo imagina en una grilla como si fuera un tablero de ajedrez, puede ver todo lo que sucede en la misma fila y en la misma columna en la que él está parado. Pero las columnas que están en cada una de las intersecciones, le obstruyen la visión de lo demás. Un intruso entra a algún casillero y él escucha una alarma pero potencialmente si no está en su fila y su columna no lo ve. Esa es la observabilidad parcial.

Entonces el robot necesita una estrategia para moverse a través del galpón hasta encontrar al intruso. Y ese problema, como es del mundo físico, no puede asumir un protocolo de comunicación subyacente. Porque hay un componente que modela el comportamiento del intruso. Y otro componente que modela el comportamiento del robot. Acaso le gritaría al intruso “¿Estás ahí?” y el otro le contestaría por voluntad propia “Sí, estoy acá”. Como no se comunican entre sí, de ningún modo, uno está forzado a resolver el problema fuerte.

En ese caso, se le provee la herramienta de síntesis. Se asume que el robot no tiene tantos mecanismos para aislar la información que le está faltando. Y de ese modo el robot intenta sintetizar la técnica. Si uno asume que el intruso se mueve a la misma velocidad que el robot, no hay estrategia. La técnica asume que no lo puede capturar. En cambio, si uno agrega un segundo robot guardia con las mismas características que el primero, en ese caso la técnica procesa y determina que hay una estrategia. La estrategia que computa es parecida a dar un “jaque mate” en el ajedrez, porque implica mover de forma sincronizada a los dos robots para ir acorralando al intruso. Entonces entre los dos robots pueden separar el tablero. Lo interesante es que la técnica lo hace automáticamente. Separa el tablero como en cuatro cuadrantes y, en algún momento, cuando ve pasar al intruso lo aísla en un cuadrante. Entonces los robots pasan a posicionarse en ese cuadrante y a hacer de nuevo la subdivisión ahí. Si en algún momento el intruso sale de ese cuadrante, lo pueden aislar en otro cuadrante. Y así le van achicando los lugares en donde puede estar sin que lo vean. Eventualmente llegan a una esquina, lo acorralan y lo atrapan.