Ομιλητής: Blair D. Sullivan (University of Utah)
Τίτλος: Navigating at the Confluence of Theory and Practice
Ημέρα: 17-02-2026, 15:00
Μέρος: Α56, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Σύνοψη
As autonomous robots become more prominent in industrial and medical settings, planning for their safe navigation of complex environments is essential. In this talk, we describe how a graph-based abstraction of this navigation task when the robot is being used to perform inspections led to improvements in both theory and practice. Specifically, using techniques from parameterized complexity allows new efficient dynamic programming and ILP algorithms for targeted inspections. This in turn motivates a new "reduce, partition, merge" strategy for scalability, opening a door for future improvements. To demonstrate practicality, we show that on simulated industrial and surgical tasks, our approaches significantly improve coverage and inspection cost over a state-of-the-art solver. Finally, we address the elephant who hangs out in the dynamic programming room, showing that a novel algebraic-circuit based approach using multilinear monomial detection could circumvent memory-usage limitations.