Learning Augmented Methods for Matching: Improving Invasive Species Management and Urban Mobility

Authors

  • Johan Bjorck Cornell University
  • Qinru Shi Cornell University
  • Carrie Brown-Lima Cornell University
  • Jennifer Dean SUNY
  • Angela Fuller Cornell University U.S. Geological Survey New York Cooperative Fish and Wildlife Research Unit
  • Carla Gomes Cornell University

Keywords:

Environmental Sustainability

Abstract

With the success of machine learning, integrating learned models into real-world systems has become a critical challenge. Naively applying predictions to combinatorial optimization problems can incur high costs, which has motivated researchers to consider learning augmented algorithms that can make use of faulty or incomplete predictions. Inspired by two matching problems in computational sustainability where data is abundant, we consider the learning augmented min weight matching problem where some nodes are revealed online while others are known a priori, e.g., by being predicted by machine learning. We develop an algorithm that is able to make use of this extra information and provably improves upon pessimistic online algorithms. We evaluate our algorithm on two settings from computational sustainability -- the coordination of unreliable citizen scientists for invasive species management, and the matching between taxis and riders under uncertain trip duration predictions. In both cases, we perform extensive experiments on real-world datasets and find that our method outperforms baselines, showing how learning augmented algorithms can reliably improve solutions for problems in computational sustainability.

Downloads

Published

2021-05-18

How to Cite

Bjorck, J., Shi, Q., Brown-Lima, C., Dean, J., Fuller, A., & Gomes, C. (2021). Learning Augmented Methods for Matching: Improving Invasive Species Management and Urban Mobility. Proceedings of the AAAI Conference on Artificial Intelligence, 35(17), 14702-14710. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17727

Issue

Section

AAAI Special Track on AI for Social Impact