This event is open to the public and registration is not required.

Abstract

In search games, a mobile searcher must navigate through the domain so as to locate an immobile hider. These problems are typically studied using a game-theoretic approach, in which the searcher and the hider chose their respective (pure or mixed) strategy. We are interested in two of the simplest, yet most fundamental and well-studied search problems: In the first problem, known as linear search, the domain consists of an infinite lines, whereas in the second problem, known as star search, the domain consists of m infinite, concurrent rays, with their common point designated as the origin. The objective of the searcher is to minimize the competitive ratio of the search, defined as the worst-case ratio of the total distance traversed by the searcher to the distance of the hider from the origin.

In this presentation we discuss some recent new extensions and approaches to these well-studied settings. First, we consider a generalization of star search in which there are more than one hiders, and each hider has a certain weight. The objective of the searcher is then to locate a collection of hiders of aggregate weight at least a specified value W, as efficiently as possible. Second, we consider linear search, and we show how to identify, in the infinite space of competitively optimal search strategies, the one that optimizes certain additional criteria. Last, we argue that the above problems capture essential aspects of resource allocation under uncertainty, and present some applications of our approaches to a scheduling problem often encountered in Artificial Intelligence, namely contract scheduling.

Speaker Bio

Spyros Angelopoulos is a CNRS researcher at the Operations Research group of the Laboratoire d’Informatique of the Sorbonne University in Paris, France. He has a Ph.D. degree in Computer Science from the University of Toronto and has been a postdoctoral fellow at the University of Waterloo and the Max Planck Institute for Computer Science, prior to joining CNRS. He has also held visiting positions at LMU Munich. His research interests include online computation, algorithmic aspects of search theory, and scheduling problems in Artificial Intelligence.

The Operations Research (OR) seminar series brings together graduate students, faculty and researchers from the University of Toronto community to interact with prominent scholars in the field of OR. Seminars feature visiting scholars from around the world as well as professors and post-docs. Topics include all variants of OR theory and their applications. Questions? Contact Merve Bodur at bodur@mie.utoronto.ca.