US Naval Submarines have done this for a long time.
I spent some time on a submarine and navigation is one of the most critical things to the cruise.
A string of submersible robotic submarines linked by really long cables that are dangled into the ocean.
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.
Autonomous underwater vehicles are an active area of research. One of the challenges involved are localization once the vehicle has dived. You cannot get GPS under water, so one way to localize yourself is by tracking your velocity/acceleration once the dive has begun. Another way is to exchange messages with your peer robots and devise a distributed location resolution scheme. See some of the work done in my lab in these areas: http://arl.nus.edu.sg/twiki/bin/view/ARL/STARFISH
http://en.wikipedia.org/wiki/Remotely_operated_underwater_ve...
So say you have a robot that's autonomously floating around look at stuff and then it goes by a giant squid. There is no one to tell it "Hey! Look, a giant squid! Stop and turn your camera at that!" so it just keeps going.
Also, I have no idea how they would know where they're currently located (again, no GPS).. but I'm sure they have some solution.
One huge advantage I could see is potentially you wouldn't need to pressurize anything. Optics can easily be made to work immersed in water, electronics can be slathered in epoxy so you don't get any short circuits. Then there shouldn't be any limit to how deep the thing can go.