Skip to content

Wednesday, 16 May 2018: NODES Seminar, Newcastle

General meeting of all members of NODES and their PhD students.

Location:

Room USB.1.006, Urban Sciences Building, Newcastle University, 1 Science Square, Newcastle upon Tyne NE4 5TG, for a map see here.

Timetable:

14.00-14.45 David Bourne (Durham, Maths): Semi-discrete optimal transport theory 14.45-15.15 Tea/Coffee break
15.15
-16.00 Sadegh Soudjani (Newcastle, CS): The Robot Routing Problem for Collecting Aggregate Stochastic Rewards


David Bourne (Durham, Maths): Semi-discrete optimal transport theory

Abstract: In this talk I will introduce the topic of semi-discrete optimal transport theory and present some results in pure maths (best approximation of L^1 functions by discrete measures) and some applications in economics, information theory and materials science. Along the way I’ll make connections with some other research areas in NODES, including computational geometry and optimal tiling problems.


Sadegh Soudjani (Newcastle, CS): The Robot Routing Problem for Collecting Aggregate Stochastic Rewards


Abstract: Reward collecting problems on metric spaces are at the core of many applications, and studied classically in combinatorial optimization under many well-known monikers: the traveling salesman problem, the knapsack problem, the vehicle routing problem, the orienteering problem, and so on. Typically, these problems model the metric space as a discrete graph whose nodes or edges constitute rewards, either deterministic or stochastic, and ask how to traverse the graph to maximize the collected rewards.
In most versions of the problem, rewards are either fixed or cumulative. In particular, once a reward appears, it stays there until collection. However, in many applications, existing rewards may disappear (e.g., a customer changing their mind) or have more “value” if they are collected fast. In this talk, I introduce the Robot Routing problem, which combines the spatial aspects of traveling salesman and other reward collecting problems on graphs with stochastic reward generation and with the possibility that uncollected rewards may disappear at each stage. I discuss preliminary results on both finite and infinite-horizon versions of the problem. I also discuss extensions to incorporate (stochastic) continuous dynamics of the robot.
The results are obtained jointly with my collaborators at Max Planck Institute.