The informal research seminar of the ALGO and AGA groups. Talks last roughly 25 minutes, with five extra minutes allocated for discussion. Many presentations are focussed on recent conference presentations, or practice talks for upcoming conferences. New members are often asked to give an overview of their field of research. Talks given by invited speakers may take up to 45-60 minutes including questions.
To be kept up-to-date about noon seminar presentations, please subscribe to the algoseminar-l mailing list.
This is the schedule for 2020. Schedules are available between 2005 and 2020.
Send an email to Jules to schedule your talk.
Recently, studies in multi-robot motion planning more and more often consider the unlabeled variant of the problem. Efficient algorithms that solve the unlabeled multi-robot motion planning problem have already been explored. Most recently, Adler et al. considered the case of unlabeled multi-robot motion planning within a simple polygon workspace. They show that under certain conditions, a motion schedule can be computed efficiently. In this thesis, we investigate their algorithm experimentally and aim to extend it in two directions. Firstly, we consider the case of non-simple workspace polygons. We show that, if we allow infinitely small holes, simultaneous movement of robots might be necessary. Secondly, we aim to improve the quality of the motion schedule in terms of quality metrics like the lengths of the paths traversed by the robots or how often they need to be activated. To compute improved schedules, we present an alternative approach to solving the pebble motion problem on graphs. We compare the resulting motion schedules experimentally.
Cartograms are popular for visualizing numerical data for map regions. Maintaining correct adjacencies is a primary quality criterion for cartograms. When there are multiple data values per region (over time or different datasets) shown as animated or juxtaposed cartograms, preserving the viewer's mental-map in terms of stability between cartograms is another important criterion. We present a method to compute stable Demers cartograms, where each region is shown as a square and similar data yield similar cartograms. We enforce orthogonal separation constraints with linear programming, and measure quality in terms of keeping adjacent regions close (cartogram quality) and using similar positions for a region between the different data values (stability). Our method guarantees ability to connect most lost adjacencies with minimal leaders. Experiments show our method yields good quality and stability.