טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentRoss Chana
SubjectLearning to Anticipate
DepartmentDepartment of Applied Mathematics
Supervisors Professor Tamir Hazan
Dr. Erez Karpas


Abstract

  Many planning problems are often characterized as combinatorial optimization problems where a large number of iterations is required in order to achieve an optimal result. This process can be long since it often includes complicated search processes and many calculations. In our research we will attempt to use prior knowledge on the problem and knowledge gained throughout the solution in order to reduce run time in each iteration for a close to optimal solution. The algorithm suggested will be an anticipatory online planner that is data driven and utilizes knowledge about the probability distribution of future changes in the problem. Future requests will be predicted based on the probability function learned throughout the simulation using machine learning methods. The algorithm will be tested and validated on Uber data and compared to policies found using standard planning methods. Our methods is an extended version of the anticipatory algorithm presented in the past with three main contributions. First, learning the future goal distribution rather than using the theoretical distribution. Second, accelerating the run-time using a more efficient offline solver and last taking into account the multi-agent structure in order to minimize the combinatorial action-space.