Εμφάνιση απλής εγγραφής

dc.contributor.advisorΔημόπουλος, Γιάννηςel_GR
dc.contributor.advisorDimopoulos, Yannisen
dc.contributor.authorΣιδέρης, Ανδρέας Γ.el_GR
dc.contributor.authorSideris, Andreas G.en
dc.coverage.spatialCyprusen
dc.coverage.spatialΚύπροςel_GR
dc.date.accessioned2015-09-18T08:52:03Z
dc.date.available2015-09-18T08:52:03Z
dc.date.copyright2015-05
dc.date.issued2015-09-18
dc.date.submitted2015-05-28
dc.identifier.otherQA76.612.S53 2015en
dc.identifier.urihttp://hdl.handle.net/10797/14416en
dc.descriptionIncludes bibliography (p. 173-181).en
dc.descriptionNumber of sources in the bibliography: 130en
dc.descriptionThesis (Ph. D.) -- University of Cyprus, Faculty of Pure and Applied Sciences, Department of Computer Science, 2015.en
dc.descriptionThe University of Cyprus Library holds the printed form of the thesis.en
dc.description.abstractΟ σχεδιασμός δράσης είναι ένα δύσκολο πρόβλημα. Ακόμα και οι πιο απλές του μορφές είναι υπολογιστικά δυσεπίλυτες ('intractable'). Παρόλο που είναι απίθανος ο αποτελεσματικός (ως προς χρόνο) σχεδιασμός δράσης στη γενική περίπτωση, εντούτοις αποτελεσματικές ευρετικές μέθοδοι και αποδοτικοί αλγόριθμοι διάχυσης περιορισμών είναι πολύτιμες τεχνικές για την επίλυση μεγάλων προβλημάτων σχεδιασμού δράσης. Πράγματι, πολλά μοντέρνα συστήματα σχεδιασμού δράσης μετατρέπουν το πρόβλημα λογική, και στη συνέχεια το λύνουν με αλγορίθμους προτασιακής λογικής (SAT solvers), περιορισμών ή ψευδό-προτασιακης λογικής ('Pseudo-boolean'). Πολλά άλλα συστήματα λογισμικού επιλύουν το πρόβλημα κατευθύνοντας την αναζήτηση με αποτελεσματικές ευρετικές μεθόδους που εξάγονται αυτόματα από το ίδιο το κωδικοποίησης των προβλημάτων σχεδιασμού δράσης σε προτασιακή λογική (SAT). Αποδεικνύουμε τόσο θεωρητικά αλλά και πειραματικά ότι οι μηχανισμοί διάχυσης περιορισμών των μοντέρνων επιλυτών προτασιακής λογικής διαχέουν τους περιορισμούς πολύ αποδοτικότερα στο SMP από άλλους τρόπους κωδικοποίησης. Επιπλέον, με τη χρήση λογισμικού που υλοποιήσαμε, βρίσκουμε επιπρόσθετους δυαδικούς περιορισμούς που ισχύουν σε προβλήματα σχεδιασμού δράσης για τους οποίους παραθέτουμε ισχυρές πειραματικές ενδείξεις η προσθήκη τους στο SMP δεν προσφέρει υπολογιστικά οφέλη. Στη συνέχεια η κωδικοποίηση του SMP χρησιμοποιήθηκε σαν βάση στην ανάπτυξη του συστήματος σχεδιασμού δράσης PSP. Το σύστημα PSP μεγιστοποιεί το πλήθος των στόχων (goals) που επιτυγχάνονται σε ένα περιορισμένο χρονικό ορίζοντα, επαναλαμβάνοντας τη διαδικασία για διαδοχικά μεγαλύτερους ορίζοντες. Παρά την αδυναμία του PSP να εγγυηθεί ότι οι λύσεις είναι βέλτιστές (ως προς το μήκος τους) όπως το σύστημα SMP, εντούτοις υπολογίζει σχέδια δράσης καλής ποιότητας για προβλήματα που δεν μπορούν να επιλυθούν από τον SMP ή άλλα συστήματα σχεδιασμού δράσης (που που παράγουν βέλτιστες λύσεις) τα οποία βασίζονται σε προτασιακούς επιλυτές. Ένα βασικό μειονέκτημα του συστήματος PSP είναι η περιορισμένη του αποδοτικότητα σε προβλήματα μεγάλου μεγέθους. Αυτό οφείλεται στο ότι οι κωδικοποιήσεις μεγάλων προβλημάτων σχεδιασμού δράσης είναι συχνά πολύ δύσκολες για τους προτασιακούς επιλυτές. Αυτό ισχύει για όλα τα συστήματα σχεδιασμού δράσης που βασίζονται στην μέθοδο της διαδοχικής επέκτασης του ορίζοντα δράσης, αφού το μέγεθος των κωδικοποιήσεων μεγαλώνει όσο μεγαλώνει και ο ορίζοντας. Η αδυναμία αυτή αντιμετωπίζεται από το σύστημα PSP-H το οποίο επεκτείνει το σύστημα PSP με δύο αποδοτικές τεχνικές που αποσυνθέτουν το πρόβλημα σε μικρότερα υποπροβλήματα ώστε τα προβλήματα προτασιακής ικανοποιησιμότητας που προκύπτουν να μην είναι υπερβολικά μεγάλα. Η πρώτη τεχνική μετατρέπει το πρόβλημα σχεδιασμού δράσης σε μια σειρά προβλημάτων δυαδικής βελτιστοποίησης, σε κάθε ένα από τα οποία ο στόχος είναι να μεγιστοποιηθεί το πλήθος των στόχων (goals) που μπορούν να ικανοποιηθούν εντός ενός περιορισμένου ορίζοντα (μήκος πλάνου). Αυτή η τεχνική συνδυάζεται με μια δεύτερη τεχνική που κατευθύνει την αναζήτηση για κάθε υποπρόβλημα σε μια κατάσταση όπου ικανοποιούνται όλοι οι στόχοι του αρχικού προβλήματος. Τα πειραματικά μας αποτελέσματα αποδεικνύουν ότι το PSP-H είναι ένας ανταγωνιστικός αλγόριθμος σχεδιασμού δράσης.el_GR
dc.description.abstractPlanning is a difficult problem. Even in its simplest forms it is computationally intractable. Although it is unlikely to be able to plan efficiently in the general case, good heuristics and strong constraint propagation methods are valuable techniques for tackling large planning problems. Indeed some modern planners transform planning into a constraint satisfaction problem, such as a boolean formula, and then solve it by invoking a satisfiability, constraint or pseudo-boolean solver. Many other planners solve the problem by guiding the search using powerful heuristics that are automatically extracted from the planning domain. In the context of this work we first implemented SMP, a novel way of transforming a planning domain into a propositional boolean formula (SAT). We prove both theoretically and experimentally that the constraint propagation engines of the modern SAT solvers propagate the constraints much more efficiently in SMP than in previous transformations. We also provide strong experimental evidence that the addition of more implied non-redundant binary constraints to SMP does not improve the planning times. We then use the SAT encoding of SMP in the PSP planner. PSP seeks to maximize the number of goals that can be achieved using the solve and expand method. Although PSP cannot guarantee optimality as SMP, it often generates sub-optimal plans of high quality for planning problems that are beyond the reach of SMP and other optimal SAT-based planners. A drawback of the PSP planner is its limited scalability, as the instances that arise from large planning problems are often too hard for SAT solvers. This holds true for all planners based on the solve and expand method, as the size of the SAT instance grows monotonically with the planning horizon. To address this problem we developed the PSP-H planning system, that extends PSP by combining two powerful techniques that aim at decomposing a planning problem into smaller subproblems, so that the instances that need to be solved do not grow prohibitively large. The first technique turns planning into a series of boolean optimization problems, each seeking to maximize the number of goals that are achieved within a limited planning horizon. This is coupled with a second technique that directs search towards a state that satisfies all goals. Experimental results demonstrate that PSP-H is a competitive planning algorithm.en
dc.format.extentxvii, 181 p. : ill. (some col.), tables ; 30 cm.en
dc.language.isoengen
dc.publisherUniversity of Cyprus, Faculty of Pure and Applied Sciencesen
dc.publisherΠανεπιστήμιο Κύπρου, Σχολή Θετικών και Εφαρμοσμένων Επιστημώνel_GR
dc.rightsThe digital form of the thesis will be released on 28/09/2018.el_GR
dc.subject.lcshConstraint programming (Computer science)en
dc.subject.lcshPropositional calculusen
dc.subject.lcshHeuristic algorithmsen
dc.titleAdvances in SAT-Based planningen
dc.title.alternativeEξελίξεις στο σχεδιασμό δράσης βασιζόμενο στη προτασιακή λογικήel_GR
dc.typeDoctoral Thesisen
dc.contributor.committeememberΔημόπουλος, Γιάννηςel_GR
dc.contributor.committeememberΚάκας, Αντώνηςel_GR
dc.contributor.committeememberΚεραυνού-Παπαηλιού, Ελπίδαel_GR
dc.contributor.committeememberDimopoulos, Yannisel_GR
dc.contributor.committeememberKakas, Antonisen
dc.contributor.committeememberKeravnou-Papailiou, Elpidaen
dc.contributor.committeememberDomshlak, Carmelen
dc.contributor.committeememberGeffner, Hectoren
dc.contributor.departmentUniversity of Cyprus, Faculty of Pure and Applied Sciences, Department of Computer Scienceen
dc.contributor.departmentΠανεπιστήμιο Κύπρου, Σχολή Θετικών και Εφαρμοσμένων Επιστημών, Τμήμα Πληροφορικήςel_GR
dc.subject.uncontrolledtermΕΥΡΕΤΙΚΕΣ ΜΕΘΟΔΟΙel_GR
dc.subject.uncontrolledtermΔΙΑΧΥΣΗ ΠΕΡΙΟΡΙΣΜΩΝel_GR
dc.subject.uncontrolledtermΙΚΑΝΟΠΟΙΗΣΙΜΟΤΗΤΑ ΛΟΓΙΚΩΝ ΠΡΟΤΑΣΕΩΝel_GR
dc.subject.uncontrolledtermΒΕΛΤΙΣΤΟΠΟΙΗΣΗ ΨΕΥΔΟ-ΠΡΟΤΑΣΙΑΚΗΣ ΛΟΓΙΚΗΣel_GR
dc.subject.uncontrolledtermΑΠΛΟΠΟΙΗΣΗ ΤΟΥ ΠΡΟΒΛΗΜΑΤΟΣel_GR
dc.subject.uncontrolledtermΕΥΡΕΤΙΚΟΙ ΑΛΓΟΡΙΘΜΟΙ ΕΥΡΕΣΗΣ ΣΧΕΔΙΩΝ ΔΡΑΣΗΣel_GR
dc.subject.uncontrolledtermΑΛΓΟΡΙΘΜΟΙ ΕΥΡΕΣΗΣ ΣΧΕΔΙΩΝ ΔΡΑΣΗΣ ΜΕΡΙΚΗΣ ΣΧΕΣΗΣel_GR
dc.subject.uncontrolledtermΣΧΕΔΙΑΣΜΟΣ ΔΡΑΣΗΣel_GR
dc.subject.uncontrolledtermCLASSICAL PLANNING__ PROPOSITIONAL PLANNINGen
dc.subject.uncontrolledtermHEURΙSTICSen
dc.subject.uncontrolledtermCONSTRAINTS PROPAGATION__UNIT PROPAGATIONen
dc.subject.uncontrolledtermPROPOSITIONAL SATISFIABILITYen
dc.subject.uncontrolledtermPSEUDO-BOOLEAN OPTIMIZATIONen
dc.subject.uncontrolledtermRELAXATIONSen
dc.subject.uncontrolledtermHEURΙSTIC PLANNERSen
dc.subject.uncontrolledtermPARTIAL ORDER PLANNERSen


Αρχεία σε αυτό το τεκμήριο

Thumbnail

Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές

Εμφάνιση απλής εγγραφής