Well, it's an autonomous robot. You only need to communicate with it on the surface. (Maybe some emergency communication feature is handy?)
You give it some kind of sensor. When it finds something bigger than 3 m at a depth of more than 500 m you start following it. I'm not saying that's easy, but we have self-driving cars and we send robots to Mars (average distance 200 million km). I'm sure we could do it, if there was interest.
It's has to orient itself in 3d space somehow. Wikipedia says the best you can get with dead reckoning drifts by .6nm/hr. I'm guessing that can be useful in some cases, but it probably limits a lot.
You give it some kind of sensor. When it finds something bigger than 3 m at a depth of more than 500 m you start following it. I'm not saying that's easy, but we have self-driving cars and we send robots to Mars (average distance 200 million km). I'm sure we could do it, if there was interest.