I recognize that AAI miners are a way to automate digging additional space underground, but the AAI Programmable Vehicles mod is poorly optimized, and eats UPS like no tomorrow.

The alternative is to manually dig my own tunnels. In a game about automation, that's less than great.

Is there an alternative that I'm missing?

What kind of automation do you need? Dig a straight line forever or clear an area?
You could try recursive blueprints for the former. The latter can be done by deconstructing this area with bots

I'm not sure that recursive blueprints would actually do anything, as bots don't seem to actually do anything.

https://youtu.be/tx7lyfPbQvo

In this video, I have power armor with roboports and construction bots, and they aren't deconstructing the rocks. I also have the nanobots mod, they also are not deconstructing the rocks.

I have been mining everything by hand.

I would love it if these things worked.

Please check your other mods. What happens if you mark other things for deconstruction? Seems that you have a mod that "deletes" deconstruction requests.
In your video, the red crosses with the clock symbol above the walls disappear. But actually they turn into the "real" red cross without a clock.

Something very strange is happening.

https://youtu.be/_-YujUdo-3Q

I made this first video with the intent of proving or disproving that the bug would happen in Vanilla Factorio. I showed that only Subsurfaces was built, I generated a brand new world, I dug a hole, and then the bots worked.

I therefore began a binary search, disabling half of my mods at a time to find the problem mod. This took hours. Eventually, I believed I found the problem mod and disabled it...

And then that didn't solve the problem.

https://youtu.be/-DpPMf7XyFg

In this video, I show that two saves with identical mods have completely different results.

In my Star Empire save, I couldn't deconstruct the rocks.

In the Deconstruction Testing save, I could.

What's the difference between the two saves?????????

Star Empire save.
https://drive.google.com/file/d/1jOL-js_SoLNntoHF5zLHqYsmIcpfxjXN/view?usp=sharing

Deconstruction Testing save.
https://drive.google.com/file/d/11dkU5zIZm6bYsKcnjXqfYisMIMELcITY/view?usp=sharing

They dont have the same mods.
And the second video is private

https://youtu.be/j5MCDjZ2M1Y

Star Empire save. I go underground, I try digging rocks with bots, I cannot.

Using the exact same mods as Star Empire, I make a creative mode world, I go underground, I try digging with bots, I can.

I develop a hunch. The difference in the two saves is technology, maybe?

Unresearch all technologies. I try digging with bots, I cannot.

Force Research Cliff Explosives. I try digging with bots, I can.

New Deconstruction Testing Save to compare against Star Empire save.
https://drive.google.com/file/d/1TmySW3rlo32Lx8Pb6oF-axj6RldbG2yB/view?usp=sharing

If this is intentional, I guess I just need to hunker down, go to Vulcanus, and unlock cliff explosives.

Explosives are the point. Unfo there's no way to tell robots to use the explosive (which was my intention).
The walls are basically cliffs which can be mined by hand and by throwing explosives. Seems that you can't deconstruct them without the technology, because the game things that robots need it. But because they can be mined by hand, as soon as you can mark them for deconstruction, they just fly there and mine it