National and Kapodistrian University of Athens
Έλεγχος της Συνέπειας Δικτύων Ποιοτικών Χωρικών Περιορισμών με Χρήση Χορδικών Γράφων
Abstract
dc:descriptionΟ Λογισμός Σύνδεσης Περιοχών (RCC) είναι η κυρίαρχη προσέγγιση στην Τεχνητή Νοημοσύνη για την αναπαράσταση και την αιτιολόγηση τοπολογικών σχέσεων. Ο RCC λογισμός μπορεί να χρησιμοποιηθεί για να περιγράψει περιοχές που είναι μη-κενά, ανελλιπή υποσύνολα ενός τοπολογικού χώρου μέσω της δήλωσης των τοπολογικών σχέσεων μεταξύ αυτών. Η περισσότερη δημοσιευμένη δουλειά σε αυτό το πεδίο κάνει χρήση ενός υπουνόλου του λογισμού RCC, το οποίο ονομάζεται RCC-8. Το υποσύνολο RCC-8 θεωρεί τις ακόλουθες 8 δυαδικές τοπολογικές σχέσεις: ασύνδετος (DC), εξωτερικά συνδεδεμένος (EC), ίσος (EQ), μερικώς αλληλεπικαλυπτόμενος (PO), εφαπτόμενα εσωκλειόμενος (TPP), εφαπτόμενα εσωκλειόμενος αντίστροφος (TPPi), μη- εφαπτόμενα εσωκλειόμενος (NTPP), μη-εφαπτόμενα εσωκλειόμενος αντίστροφος (NTPPi). Θεωρούμε χορδικά RCC-8 δίκτυα και δείχνουμε πως μπορούμε να ελέγξουμε την συνέπειά τους με την επιβολή μερικές συνέπειας μονοπατιού με αδύναμη σύνθεση. Το αποδεικνύουμε αυτοό χρησιμοποιώντας το δεδομένο πως τα RCC-8 δίκτυα με σχέσεις από τα μέγιστα βατά υποσύνολα H8, C8, και Q8 του RCC-8 έχουν την ιδιότητα της αμαλγάμωσης. Η χρήση της μερικής συνέπειας μονοπατιού έχει σημαντικά πρακτικά επακόλουθα τα οποία επιδεικνύουμε με την υλοποίηση του νέου προγράμματος συλλογιστικής PyRCC8+. Δοθέντος ενός RCC-8 δικτύου με αποκλειστικά βατές RCC-8 σχέσεις, δείχνουμε ότι μπορεί να επιλθυεί πολ΄θ αποδοτικά τριγωνοποιώντας τον υποκείμενο γράφο περιορισμών και εφαρμόζοντας την συνέπεια μονοπατιού σε αυτό τον αραιό γράφο έν αντιθέσει με την πλήρωση του συγκεκριμένου δικτύου. Κατά τον ίδιο τρόπο, η μερική συνέπεια μονοπατιού μπορεί να χρησιμοποιηθεί ως το βήμα ελέγχου συνέπειας σε αλγόριθμους υπαναχώρησης για δίκτυα αυθαίρετων RCC-8 σχέσεων με αποτέλεσμα την βελτιωμένη απόδοση για αραιά δίκτυα, ενώ υπόκειται σε ποινή για πυκνά δίκτυα.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Σιούτης Μιχαήλ
Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:1317543