Όλοι ακούμε για την Τεχνητή Νοημοσύνη που τα τελευταία χρόνια αποτελεί όλο και μεγαλύτερο κομμάτι της ζωής μας με εφαρμογές που οι περισσότεροι δε θα φανταζόμασταν ποτέ. Η αναπαράσταση του πραγματικού κόσμου απαιτεί πολύπλοκα μοντέλα που να μπορούμε να δώσουμε σε πράκτορες και να δούμε πώς θα ενεργήσουν. Οι Μαρκοβιανές Διαδικασίες Αποφάσεων (MDP) και κυρίως οι Μερικώς Παρατηρούμενες Μαρκοβιανές Διαδικασίές Αποφάσεων (POMDP) αφορούν τη λήψη αποφάσεων υπό αβεβαιότητα και βοηθούν ιδιαίτερα στην πιστή αναπαράσταση ενός περιβάλλοντος. Οι δυνατότητες φαίνονται ατελείωτες, καθώς οι εφαρμογές κυμαίνονται από «έξυπνους» παίκτες παιγνίων μέχρι αυτοματοποιημένα συστήματα οδήγησης. Ένα τέτοιο πρόβλημα που κεντρίζει συνεχώς το ενδιαφέρον είναι η αυτοματοποιημένη άμυνα ενός δικτύου, δηλαδή ένα δίκτυο που προστατεύεται μόνο του από επίδοξους εισβολείς, προβλέποντας τις κινήσεις τους και παίρνοντας τα κατάλληλα μέτρα ώστε να τους αποτρέψει από το να φτάσουν σε ζωτικά σημεία του δικτύου. Οι επιτηθέμενοι δεν κάνουν απλές ενέργειες, αλλά χρησιμοποιούν πολύπλοκες τακτικές συνδυάζοντας πολλά τρωτά σημεία του δικτύου κι έτσι η ανάπτυξη ενός τέτοιου συστήματος άμυνας καθίσταται αρκετά δύσκολη. Αν και μπορούμε να αναπαραστίσουμε το πρόβλημα αρκετά πιστά σαν POMDP, υπάρχει το ζήτημα της γρήγορης επίλυσης, καθώς το POMDP μοντέλο είναι ήδη περιπλεγμένο αυτό καθ’αυτό. Οι ερευνητές, λοιπόν, εστιάζουν την προσοχή τους στην ανάπτυξη γρήγορων αλγορίθμων που να μπορούν να λύνουν αυτά τα προβλήματα σε ρεαλιστικές καταστάσεις.
Αρχικά, θα εισάγουμε τις βασικές έννοιες και πληροφορίες προκειμένου να γίνει κατανοητό το MDP μοντέλο και θα συνεχίσουμε με το POMDP που επεκτείνει το προηγόυμενο, κάνοντάς το ρεαλιστικά εφαρμόσιμο. Έπειτα, γίνεται η παρουσίαση του προβλήματος της αυτοματοποιημένης άμυνας σαν POMDP και καταλήγουμε στον αλγόριθμο DESPOT, που είναι από τους καλύτερους που μπορούν να ανταπεξέλθουν σε POMDP προβλήματα τέτοιας κλίμακας.
(EL)
In recent years, artificial intelligence becomes all the more significant for our lives with
many applications most of us would not even imagine. Representing the real world
demands sophisticated models, which we “feed” to agents to see how they will respond.
This is where Markov Decision Processes (MDPs) and Partially Observed Markov
Decision Processes (POMDPs) shine. POMDPs provide us with a general framework to
depict many different kinds of problems. The capabilities seem endless; from agents that
play games optimally to driverless cars. One of these problems that is becoming more
and more relevant today is the dynamic defense of a cyber network, which basically
means a network that protects itself from intruders in real time by trying to predict their
moves and stop them from progressing further into the network and reaching vital points.
The development of such a defense system is complicated, since the attackers do not
use simplistic methods, but instead rely on a complex sequence of exploits, combining
many vulnerabilities. The POMDP model can provide a quite realistic representation of
this problem. However, as with most demanding problems modeled as such, it is difficult
to solve them efficiently due to the complicated structure of the POMDP model itself.
Researchers focus on creating sufficient algorithms that can tackle these problems in
realistic situations.
We will begin with introducing the basic information needed to understand the MDP model
and then we continue with the POMDP model which extends the idea to more realistic
applications. Then, we can present the formulation of the dynamic defense problem as
POMDP and after that we take a look into the DESPOT POMDP solver, which is one of
the best algorithms to scale up and cope with such complicated problems.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
