The thing about using a compass is that you must also know where the robot is from other means, like inertial navigational. Therefore you will know what the compass should read at any point. When you find that the compass is giving a wildly off reading you know you are close to your magnet.
A conventional metal detector would also work for you here providing it is not disturbed by the motors.
as the robot will not have to go through a grid pattern that might take a long time to sweep the entire course.
That implies you need a much longer range with proportional sensing.