This thesis looks at the problem of optimally placing binary directional proximity markers to assist a robot as it navigates waypoints through an environment. A simple planar fiducial marker is developed to serve as the binary directional proximity marker. A scoring function is proposed for marker placement as well as a method for random generation of hallway maps. Several common metaheuristic algorithms are run to find optimal marker placements with respect to the scoring function for a number of randomly generated hallway maps. From these results, placements are then evaluated by physical experimentation on an iRobot Create equipped with relatively inexpensive webcams. / Graduate