Στο πλαίσιο της διοργάνωσης των σεμιναρίων του τμήματος θα πραγματοποιηθεί διαδικτυακά μέσω της εφαρμογής Ms Teams την Παρασκευή 05/11/2021 και ώρα 12:00, ομιλία με τίτλο «Exploring Graphs with Time Constraints by Mobile Robots». Ομιλητής θα είναι ο  κ. Ευριπίδης Μάρκου, Αν. Καθηγητής, Τμήμα Πληροφορικής με Εφαρμογές στη Βιοϊατρική, Πανεπιστήμιο Θεσσαλίας. Μπορείτε να παρακολουθήσετε την ομιλία μέσω του παρακάτω συνδέσμου: Link MS Teams

ΠΕΡΙΛΗΨΗ

Imagine a graph with weights on its edges and nodes. A node weight represents a deadline for this node and an edge weight represents the time a robot needs to traverse this edge. A robot needs to visit each node of the graph before its deadline.

Can we decide within polynomial time whether such a `successful’ exploration can be achieved?

We survey this area of research presenting some positive results for special graph topologies and also negative results for more general graph topologies. We compare the computational complexity of this problem with the complexity of the problem where each node must be visited not just once but periodically and the maximum allowed time-period between any two consecutive visits of the same node should not exceed its deadline.

We also present some results when more than one robots can collectively explore the graph and conclude with mentioning a few results when some robots may crash.

The above exploration-scheduling problems find applications in diverse areas like mobile monitoring and facility service and maintenance but even digital-signal processing.