Results - Details
Search command : Author="Φλουρής"
And Author="Γεώργιος"
Current Record: 14 of 22
|
Identifier |
000408047 |
Title |
Repairing of sequential plans in dynamic environments |
Alternative Title |
Επιδιόρθωση ακολουθιακών σχεδίων ενεργειών σε δυναμικά περιβάλλοντα |
Author
|
Γουίδης, Φίλιππος Ε.
|
Thesis advisor
|
Πλεξουσάκης, Δημήτρης
|
Reviewer
|
Τσαμαρδινός, Ιωάννης
Φλουρής, Γεώργιος
|
Abstract |
Planning is one of the oldest and most fundamental research areas of Artificial
Intelligence. Apart from its theoretical importance, it is utilized very frequently in a wide
range of practical applications that spans from space
missions to factory line production.
A common complication that occurs after the production of plans, is their rendering
invalid or suboptimal during their execution, due to the dynamic nature of the
environments where they are executed. A fast response m
echanism can be proven crucial
for domains where the assumption of a static environment is very optimistic, if not
untenable. This thesis presents an algorithm for plan repairing that utilizes previous
information and computational effort, in order to acce
lerate the production of new plans
that correspond to the altered conditions of their environment.
This algorithm is an expansion of the A* algorithm, a standard planning
algorithm of the
relevant literature, upon which many of the state
-
of
-
the
-
art plann
ers are based. This
expansion is tailored to the repairing of the plans in non
-
static environments of certain
characteristics. Namely, dynamic goal
-
sets and modifiable action costs can be addressed.
The experimental protocol that we used for the assessment of the algorithm's
performance is the following. First, a plan is produced for the initial environment's
conditions. Consequently, assuming that the plan has been executed up to a certain
percentage
, either the problem's goal
-
set or some of its actions' costs is changed. Finally,
the repairing and the
A*
algorithms
are executed from the latter point. The type of
domains and problems that we used for the evaluation are standard benchmarks, derived
from the international planning competitions.
The experimental results indicate that the performance of the algorithm depends from
the following factors: the ratio of the original graph search size to the final graph search
size, the branching parameter of t
he problem, the density of the graph search, the
percentage of the original plan already executed and the volume of the changes in the
environment. For sparse search graphs and small to moderate environment changes, the
algorithm outperforms A*in terms of
speed by a factor of 10% to 80% in the majority of
the cases, if the percentage of the plan that has been already executed is less than 40% to 50%.
We consider that this thesis can provide useful insights and hints towards the
development of more efficient plan repairing techniques, since the A* constitutes the
backbone of many actual planners.
Moreover, we believe that our work can be further
improved and expanded, by incorporating new features, such as a decentralized approach
and a real
-
time response functionality.
|
Language |
English |
Subject |
Artificial intelligence |
|
Planning |
|
Σχεδιασμός ενεργειών |
|
Τεχνητή νοημοσύνη |
Issue date |
2017-03-17 |
Collection
|
School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses
|
|
Type of Work--Post-graduate theses
|
Permanent Link |
https://elocus.lib.uoc.gr//dlib/7/5/c/metadata-dlib-1491376234-264942-13756.tkl
|
Views |
656 |