PhD Thesis
Título (Tittle): Representing and Planning tasks with time and resources
Directores (Supervisors): Dr. Daniel Borrajo Millán and Dr. Daniel Meziat Luna
Any problem solving technique in Artificial Intelligence (AI), as an area in Computer Science, must face two aspects when providing computational solutions to problems: knowledge representation and the methods used to reason. One of the solving techniques that has gained recent importance inside AI is planning and scheduling.
In this Ph.D. thesis we study these two aspects for AI planning and scheduling. The first goal will be to face the problem of knowledge representation in two real domains. First we have dealt with workflow domains by means of the SHAMASH workflow modeling tool and the COSMOSS workflow system at British Telecom. Second, we have used the satellites domain for HISPASAT, a Spanish multi-mission system in charge of satisfying national communication needs. For this domain, we will be in charge of providing a solution to the ground nominal operations for its satellites.
But these domains need the integration of techniques from
planning and scheduling. Traditionally, there is a clear subdivision of techniques
and roles that belong to planning and scheduling. Planning systems select and
order sets of activities such that they achieve one or more goals and satisfy
a set of domain constraints. For most part, planning research has focused on
finding a feasible chain of actions that accomplish one or more goals.
Scheduling systems are in charge of assigning resources and time for activities,
obeying their temporal restrictions and the capacity limitations of shared resources.
Scheduling is an optimisation task where limited resources are allocated over
time among both parallel and sequential activities, such that deadlines and
makespan are minimised.
The second goal will be to study the weak and strong points of both fields. Planning systems have a rich representation of the problem descriptions but they have limitations to reason about time and handle cumulative resources. Scheduling systems can perfectly handle temporal and resources reasoning, but there is a lack of expressive language to represent the problem.
From this perspective, by combining scheduling and planning systems synergistically these weaknesses can be solved. We present here different models to integrate planning and scheduling: from the stand alone approach of using a planner, to the pipeline integration of using a planner and a scheduler, towards the more integrated approach of interleaving planning and scheduling. This last approach will be compared against the other two models and some state of the art planners, showing its effectiveness.
En esta tesis hemos abordado como primer objetivo,
el problema de la representación del conocimiento para planificación
en dos dominios reales.
Uno de los obstáculos en aplicar técnicas de planificación
a dominios reales es la dificultad en modelar dominios. Generalmente se necesita
que las personas que han participado en su desarrollo deban llevar a cabo la
fase de modelado ya que en muchos casos la representación depende bastante
del conocimiento del funcionamiento interno de la herramienta.
Uno de los dominios pertenece a los sistemas de planificación de actividades de negocio, como son los sistemas de gestión de procesos conocidos como sistemas de Workflow. El otro pertenece al dominio de los satélites, en concreto se ha realizado la modelización de las operaciones nominales que desde tierra se deben llevar a cabo en el operador español de telecomunicaciones por satélite Hispasat.
En los sistemas de gestión de procesos se han dedicado
esfuerzos para la defini- ción de lenguajes que permitan a usuarios no
expertos, introducir facilmente el conocimiento de los procesos en las herramientas
con las que trabajan. Se ha utilizado la herramienta de modelado de procesos
Shamash y el sistema de workflow en British Telecom llamado COSMOSS para introducir
el conocimiento. Dicho conocimiento será traducido en términos
de lógica de predicados (por ejemplo al lenguaje estándar de representación
de dominios de planificación PDDL2.1). Después de esta conversión,
se podrán validar y generar automaticamente modelos reales utilizando
cualquier planificador que soporte PDDL2.1.
Con la unión, los planificadores ganan un lenguaje fácil de utilizar
por cualquier usuario y a los sistemas de Workflow les permiten generar
y validar los modelos de los procesos que se deben realizar a diario en sus
empresas.
Para la empresa de telecomunicaciones por satélite Hispasat hemos desarrollado la herramienta CONSAT (CONtrol de SATélites) para ayudar a dar solución al problema de planificar las operaciones que desde tierra deben llevar a cabo el grupo de ingenieros. Cada año este grupo genera toda la documentación necesaria a mano y en papel. Existen dos tipos de documentos, uno que proporciona una visión de las operaciones que se deben realizar cada día del año, y otro que representa con más detalle las operaciones que se deben realizar cada semana. Una vez generados los documentos, se revisan y se verifican. Debido al incremento del número de satélites (actualmente cuatro y en el futuro dos más), esta tarea necesita ser automatizada.
CONSAT da solución a estos problemas gracias a los tres subsistemas de los que consta:
- El subsistema de usuario se encarga de controlar
el acceso de los usuarios así como la manipulación de todos los
ficheros y datos de entrada necesarios para la planificación de todas
las operaciones.
- El subsistema razonador una vez que los datos han sido introducidos
correctamente, un planificador se encargará de dar solución al
problema.
- El subsistema generador: es responsable de mantener la coherencia
entre las dos posibles representaciones que los ingenieros necesitan: la "anual"
y la "semanal". Cualquier modificación que se realice en una
representación será actualizada automaticamente en la otra, evitando
los fallos de incongruencias muy habituales al generarse a mano. Además,
este subsistema genera la solución en el tipo de formato que utilizan
en Hispasat, permite comparar dos soluciones diferentes o generarlas en HTML.
Pero en la planificación de estos dominios se necesita trabajar con tiempo y recursos. Dentro del área de planificación se distinguen básicamente dos grandes campos: la planificación y el scheduling.
Por planificación se entiende la selección de una secuencia de actividades de tal forma que satisfagan una o varias metas y un conjunto de restricciones impuestas por el dominio. La mayoría de las investigaciones realizadas en planificación se han centrado en encontrar un conjunto ordenado de acciones que satisfagan una o más metas.
Por scheduling se entiende la asignación de recursos y tiempos de inicio de las actividades, obedeciendo a las restricciones temporales de las actividades y las limitaciones de capacidad de los recursos compartidos. Scheduling es también una tarea de optimización donde recursos limitados se disponen a lo largo del tiempo entre actividades que se pueden ejecutar en serie o en paralelo de acuerdo con el objetivo de, por ejemplo, minimizar el tiempo de ejecución de todas las actividades.
Como segundo objetivo, en este trabajo, se han identificado los puntos débiles y fuertes de la planificación y scheduling y se ha propuesto una solución que integra ambos campos. Se han presentado distintos modelos de integración: desde la utilización de un planificador para resolver los problemas de los dominios expuestos anteriormente, pasando por la integración en línea de un planificador y un scheduler, hasta el enfoque más integrado que entremezcla planificación y scheduling: IPSS (Integrated Planning and Scheduling System).
En IPSS el razonamiento se divide en dos niveles. El planificador se encarga de la selección de acciones (puede optimizar según una métrica de calidad diferente al tiempo o recurso) y el scheduler de la asignación del tiempo y los recursos. Durante el proceso de búsqueda, cada vez que el planificador decide aplicar un operador, consulta al scheduler para comprobar su consistencia temporal y de recursos. Si es inconsistente el planificador vuelve hacia atrás y genera otra secuencia de acciones.
IPSS consta de tres capas:
- La capa Deordering: tiene como misión convertir
el plan incompleto totalmente ordenado en un plan incompleto parcialmente ordenado.
- La capa Ground-CSP: se encarga de crear una Red Temporal, añadiendo
los operadores y las retricciones causales y temporales entre ellos.
- La capa Meta-CSP: razona sobre los conflictos de
recursos que pueden ocurrir entre pares de actividades que consumen el mismo
recurso.
Los resultados demuestran la eficacia de IPSS frente a los enfoques de integrar planificación y scheduling en línea y respecto a otros sistemas de planificación actuales cuando se puede realizar una separación entre los recursos y predicados lógicos y se puede imponer una duración máxima al plan solución.
Last update: March 2005
© Copyright María Dolores Rodríguez Moreno.