Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Artificial Intelligence and Robotics
Research Collection School Of Computing and Information Systems
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Shortest Path Based Decision Making Using Probabilistic Inference, Akshat Kumar
Shortest Path Based Decision Making Using Probabilistic Inference, Akshat Kumar
Research Collection School Of Computing and Information Systems
We present a new perspective on the classical shortest path routing (SPR) problem in graphs. We show that the SPR problem can be recast to that of probabilistic inference in a mixture of simple Bayesian networks. Maximizing the likelihood in this mixture becomes equivalent to solving the SPR problem. We develop the well known Expectation-Maximization (EM) algorithm for the SPR problem that maximizes the likelihood, and show that it does not get stuck in a locally optimal solution. Using the same probabilistic framework, we then address an NP-Hard network design problem where the goal is to repair a network of …
Online Spatio-Temporal Matching In Stochastic And Dynamic Domains, Meghna Lowalekar, Pradeep Varakantham, Patrick Jaillet
Online Spatio-Temporal Matching In Stochastic And Dynamic Domains, Meghna Lowalekar, Pradeep Varakantham, Patrick Jaillet
Research Collection School Of Computing and Information Systems
Spatio-temporal matching of services to customers online is a problem that arises on a large scale in many domains associated with shared transportation (ex: taxis, ride sharing, super shuttles, etc.) and delivery services (ex: food, equipment, clothing, home fuel, etc.). A key characteristic of these problems is that matching of services to customers in one round has a direct impact on the matching of services to customers in the next round. For instance, in the case of taxis, in the second round taxis can only pick up customers closer to the drop off point of the customer from the first …