PGT Projects 2023 - Enright

--- tags: msc_2024, projects, pgt --- # PGT Projects 2024 - Enright ---- Title: **Finding location-avoiding paths** Student: **Text here** Project Outline The localization game is played by two agents on a graph. One is the **finder** and one is the **hider**. The hider wants to escape detection for as long as possible, and the finder wants to locate the hider using towers or sensors that tell the finder how far the hider currently is from the sensors. In this project, you would solve a sub-problem of this game. Given a graph and a specified set of locations for towers, you would compute the longest possible path that the hider can walk along that avoids detection by the finder. You might want to do this using an exhaustive combinatorial search, or perhaps try using an integer programming or constrainbt programming approach. The expectation is that the project student will expand and evolve the product beyond this initial specification. Key skills: Coding, algorithmic reasoning. Willingness to learn combinatorial optimisation techiques. Useful starting points: - a seminar on a similar game: https://www.youtube.com/watch?v=b-F-EyUB7ro ---- Title: **Characterising temporal animal contact networks** Student: **Text here** Project Outline: Animal social networks can change over time, and some data (linked below) are available. In this project you would implement a number of temporal graph measures (e.g. causal fidelity, Jaquard distance, etc) to characterise the changes in a network over time. You would then compare these measures for different animal networks, and describe the similarities and differences. The expectation is that the project student will expand and evolve the product beyond this initial specification. Key skills: Coding, learning/understanding network measures, plotting outputs. Useful starting points: - https://networkrepository.com/asn.php - https://en.wikipedia.org/wiki/Temporal_network ---- Title: **Experimentally finding equilibria in a networked game** Student: **Text here** Project Outline Imagined agents networked together all playing a game (in the classic game theoretic sense). Perhaps it is a coordination game, and the individual payoff of a node is related to how well they coordinate with their network neighbours. Depending on the initial state of the game, the network may end up at any of a number of equilibria, or might end up oscilating back and forth between states. In this project, you will implement a simulation of this sor tof game and investigate how small changes to a network can impact the eventual overall outcome. The expectation is that the project student will expand and evolve the product beyond this initial specification. Key skills: Coding, algorithmic reasoning. Running large-scale experiments, plotting outputs. Useful starting points: - https://en.wikipedia.org/wiki/Nash_equilibrium - https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3082671 ---- Title: **Developing and evaluating heuristic infectious vaccine strategies** Student: **Text here** Project Outline We can imagine an infectious vaccine for a disease: that is, a vaccine that can spread over the same network of contacts as the disease itself. In this project you will develop and test several heuristic strategies for deploying an infectious vaccine. You will also build a simulation model of the disease/vaccine system and use this to research the effectiveness of different vaccine strategies. The expectation is that the project student will expand and evolve the product beyond this initial specification. Key skills: - coding, algorithmic thinking, large-scale experiments, plotting outputs Useful starting points: - a survey of a replated problem: https://www.unf.edu/~wkloster/3210/FireSurvey.pdf ---- Title: **Alpha-beta game search for cops-and-robbers** Student: **Text here** Project Outline: In the game of cops and robbers on a graph two players (the cop player and the robber player) place themselves on the vertices of the graph. Then on each turn the robber moves and then the cop moves. The cop wins if they are able to capture the robber in finite time. In this project, you will develop a minimax game search that implements the cops-and-robbers game, and will therefore give an exact and optimal set of behaviour for both players. You will investigate research questions around what approaches or guiding heuristics give improved performance of the search. Key skills: Coding, algorithmic reasoning. Running large-scale experiments, plotting outputs. Useful starting points: - https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning - https://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves - https://en.wikipedia.org/wiki/Pursuit%E2%80%93evasion - https://www.youtube.com/watch?v=9mJEu-j1KT0 ---- Title: **Finding dominating sets** Student: **Text here** Project Outline: A dominating set in a graph is a set of vertices $D$ such that every vertex is either in $D$ or adjacent to something in $D$. Finding dominating sets of minimum size is, in general NP-hard. You will implement any of a number of combinatorial search approaches and answer research questions about the relative effectiveness of various approaches or heuristics for this problem. The expectation is that the project student will expand and evolve the product beyond this initial specification. Key skills: Mathematical reasoning, combinatorial search, coding. Useful starting points: - https://en.wikipedia.org/wiki/Dominating_set - https://en.wikipedia.org/wiki/Combinatorial_search