Metric dimension & robot navigation (Spring 2019)
We study robot navigation in a graph-structured framework in which the robot moves from node to node and can locate itself using the presence of distinctively labeled landmarks. Given a graph, we would like to use the minimum number of landmarks so that the robot can determine its current node just from that node's distances to the landmarks. This minimum number is called the metric dimension of the graph. In this project, we will investigate unsolved problems about metric dimension and some of its variants, including edge metric dimension in which the robot moves from edge to edge instead of node to node.
People
Jesse Geneson (PostDoc)
Misa Hamanaka (Undergrad)
Leslie Hogben (Faculty)
Carolyn Reinhart (Grad)
Brandon Tague (Undergrad)
Pre-requisites
A course with proofs such as Math 301, 304, 314, 317, 341, 350, 407, 414, 435, or 436
Experience with graph theory (Math 314) is desirable, but not necessary
Programming experience is not required, but may be useful for gathering data