Michael Buro's 2021-2022 MSc Projects Mar-8, 2021: I am looking for 3 MSc students for the following projects - 2021 and 2022 summer funding is secured Mar-28, 2021: update: added busy beaver project and other project ideas Project 1 --------- Topic: Learning Motion Tracking via Simulations Description: Tracking mobile objects is crucial for effective traffic navigation. Humans excel at this task and autonomous driving will require it. In this project we will investigate how to efficiently track objects by means of supervised learning based on video footage generated by 3d object trajectory simulators. Prerequisites: - Machine learning expertise - in particular deep-network learning - Familiarity with PyTorch or Tensorflow, Python, and C++ - Computer vision background will also help ============================================================================= Project 2 --------- Topic: Applying Machine Learning to Variable Selection in SAT Solvers Description: Many important real-world combinatorial problems can be reduced to determining whether a propositional formula has a satisfying variable assignment. Satisfiability (SAT) solvers have come a long way in solving large formulas, but haven't used modern machine learning techniques much. In this project we will study how deep-neural network learning can be used to select split-variables more effectively - which has the potential to speed-up SAT solvers considerably. Prerequisites: - Machine learning expertise - in particular deep-network learning - Familiarity with PyTorch or Tensorflow, Python, and C++ - Theoretical CS background will also help ============================================================================= Project 3 --------- Topic: Learning pathfinding policies Description: In this project we will study how pathfinding algorithms can be improved by applying deep-network learning to potentially large maps to train heuristics or motion policies directly from optimal path training data. Prerequisites: - Heuristic Search expertise, in particular pathfinding algorithms - Machine learning expertise - in particular deep-network learning - Familiarity with C++ and PyTorch or Tensorflow ============================================================================= Project 4 --------- Topic: Learning vehicle driving policies Description: In this project we will study how local vehicle driving policies can be learned in a simulated traffic environment, using look-ahead search and deep reinforcement learning Prerequisites: - Heuristic Search expertise, in particular MCTS - Machine learning expertise - in particular deep-network and reinforcement learning - Familiarity with C++ and PyTorch or Tensorflow ============================================================================= Project 5 --------- Topic: Learning RTS game combat policies Description: In this project we will study how large unit battle groups can cooperate effectively in simulated combat scenarios, based on look-ahead search and deep reinforcement learning Prerequisites: - Heuristic Search expertise, in particular MCTS - Machine learning expertise - in particular deep-network and reinforcement learning - Familiarity with C++ and PyTorch or Tensorflow ============================================================================= Project 6 --------- Topic: Determining S(5) and ∑(5) Description: How long can halting Turing machines with k states and 2 symbols run, and how many 1-cells can they leave behind on the tape? The related functions S(k) and ∑(k), defined by Rado in 1962 and also known as "busy beaver" functions, are non-computable in general, and their exact values are only known for k ≤ 4. The best known lower bounds for S(5) and ∑(5) - 4,098 and 47,176,870, respectively - were found in 1990, but the exact values are still unknown. In this project we will reduce the number of undecided Turing machines further by developing automated non-termination proofs, with the goal of reaching 0, and establishing the exact values of S(5) and ∑(5) Prerequisites: - Theory: automata, Turing machines, computability, proof techniques - Programming expertise (C++ or Java preferred) ============================================================================= Other project ideas to be worked on in collaboration with PhD students: A) Speed up best-response computations in imperfect information games B) Learning to cooperate in multi-player imperfect information games C) Hierarchical planning in domains with huge state and action spaces