Fully homomorphic encryption would open the possibility of 100% autonomous robots.
The robots store Bitcoin private keys inside a fully homomorphically encrypted program.
Whenever the robot gets repaired or refuelled (by whoever feels like doing it - there is no central authority maintaining the robots), the robot rewards that person with a few BTC.
Of course the robot would require some unforgeable proof that it has been refuelled or repaired, before sending a BTC transaction. I'm not sure how this could be done.
The robots could also "earn" BTC by delivering stuff for people and getting paid.
Vandalism is discouraged, because if you destroy the robot the BTC stored in its memory are gone forever. Remember that simply copying the memory is useless because it's encrypted, and decryption is only possible by interacting with the robot.
This is wild science fiction. Moreover, I doubt such autonomous robots would be a good thing.
Robots belong to people. There is no point building a robot who belongs to no-one. I also disagree about vandalism being discouraged. If I had such a robot in front of me, I could destroy it, not for the bitcoins, but just for fun. That's what vandalism is about : it is not theft, it is pure desctruction for the sake of destruction.
The only way to prevent vandalism would be to give robots some kind of rights, which is even wilder science fiction.