-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy paththesis.html
More file actions
executable file
·183 lines (179 loc) · 12.5 KB
/
thesis.html
File metadata and controls
executable file
·183 lines (179 loc) · 12.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>MD. R-Moreno's PhD Thesis</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<link href="estilos/estilocss.css" rel="stylesheet" type="text/css">
</head>
<body bgcolor="#fdfeff" background="iconos/fondo_libros.jpg" lang=ES
link=blue vlink=purple style='tab-interval:35.45pt' bgproperties=fixed>
<body>
<p class="texto">PhD Thesis</p>
<p class="texto"> </p>
<p class="fecha"> </p>
<p class="alineada"> <strong>Título</strong> (Tittle): <a href="http://atc1.aut.uah.es/~mdolores/Docs/2003/MDR-Moreno-thesis.pdf">Representing and
Planning tasks with time and resources</a> </p>
<p class="alineada"> <strong>Directores</strong> (Supervisors): <a href= "http://scalab.uc3m.es/~dborrajo/">Dr.
Daniel Borrajo Millán </a> and <a href= "http://atc2.aut.uah.es/~dmeziat/">
Dr. Daniel Meziat Luna</a>
<p class="alineada"><a href = "#abstract">Abstract</a> (<a href = "#resumen">Resumen</a>)
<p class="alineada">
<p align="center" class="normal"><a href = "index.html"> <img src="iconos/home.jpg" width="38" height="38"></a></p>
<hr>
<p class="alineada">
<p class="alineada"><strong><a name="abstract">Abstract</a></strong>
<p class="alineada">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. </p>
<p class="alineada">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. </p>
<p class="alineada">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.<br>
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. </p>
<p class="alineada">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. </p>
<p class="alineada">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.</p>
<p class="alineada"> </p>
<p class="alineada"> </p>
<p align="center" class="normal"><a href = "index.html"> <img src="iconos/home.jpg" width="38" height="38"></a></p>
<hr>
<p class="alineada"><strong><a name="resumen">Resumen Ampliado</a> </strong></p>
<p class="alineada">En esta tesis hemos abordado como <em><strong>primer objetivo</strong></em>,
el problema de la representación del conocimiento para planificación
en dos dominios reales. <br>
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. </p>
<p class="alineada">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 <em>Workflow</em>. 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.</p>
<p class="alineada">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. <br>
Con la unión, los planificadores ganan un lenguaje fácil de utilizar
por cualquier usuario y a los sistemas de <em>Workflow</em> les permiten generar
y validar los modelos de los procesos que se deben realizar a diario en sus
empresas. </p>
<p class="alineada">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.</p>
<p class="alineada"> CONSAT da solución a estos problemas gracias a los
tres subsistemas de los que consta:</p>
<p class="alineada"><em>- El subsistema de usuario</em> 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.<br>
<br>
<em>- El subsistema razonador</em> una vez que los datos han sido introducidos
correctamente, un planificador se encargará de dar solución al
problema.<br>
<br>
<em>- El subsistema generador</em>: 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.
</p>
<p class="alineada">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 <em>scheduling</em>. </p>
<p class="alineada"> 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. </p>
<p class="alineada">Por <em>scheduling</em> 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. </p>
<p class="alineada">Como <strong><em>segundo objetivo</em></strong>, 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 <em>scheduler</em>,
hasta el enfoque más integrado que entremezcla planificación y
<em>scheduling</em>: IPSS (Integrated Planning and Scheduling System). </p>
<p class="alineada">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 <em>scheduler</em>
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 <em>scheduler</em>
para comprobar su consistencia temporal y de recursos. Si es inconsistente el
planificador vuelve hacia atrás y genera otra secuencia de acciones.
</p>
<p class="alineada">IPSS consta de tres capas: </p>
<p class="alineada">- La capa <em>Deordering</em>: tiene como misión convertir
el plan incompleto totalmente ordenado en un plan incompleto parcialmente ordenado.<br>
<br>
- La capa <em>Ground-CSP</em>: se encarga de crear una Red Temporal, añadiendo
los operadores y las retricciones causales y temporales entre ellos.</p>
<p class="alineada">- La capa <em>Meta-CSP</em>: razona sobre los conflictos de
recursos que pueden ocurrir entre pares de actividades que consumen el mismo
recurso. <br>
</p>
<p class="alineada">Los resultados demuestran la eficacia de IPSS frente a los
enfoques de integrar planificación y <em>scheduling</em> 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.
</p>
<p align="center" class="normal"><a href = "index.html"> <img src="iconos/home.jpg" width="38" height="38"></a></p>
<p align="center" class="normal"> </p>
<p class="pieAzul"> <a target="_blank" href="http://v1.nedstatbasic.net/stats?ABSKtgjUUP8kqXiGL/IttkoDSqAg">
<img src="http://m1.nedstatbasic.net/n?id=ABSKtgjUUP8kqXiGL/IttkoDSqAg"border="0" nosave width="18" height="18"></a>
Last update: March 2005
<p class="pieAzul">© Copyright María Dolores Rodríguez Moreno. </p>
</body>
</html>