Is there a universal, deterministic sequence of actions that can solve any maze, assuming that the actions are applied blindly with no sensor feedback?
>> "We can then interpret the base 4 digits of p as directions (up, down, left, or right) with the understanding that if the robot tries to move in an obstructed direction then it does nothing and moves on to the next instruction."
I'm not clear on the latter part of that, what it means to move on to the next instruction. Just skip to the next digit, I assume? I wonder what would happen if you reset to the starting position and picked another starting point in the digit sequence. Though, if we're simulating an actual robot navigating, that doesn't fit.
I'm curious about the efficiency. It would be interesting to see how often points in the maze are revisited. Does the robot spend a lot of time wandering around a small area.
It is a cool way to approach mazes with loops preventing a right- (or left-) hand rule from working. I have a maze generator I wrote. Might be fun to try this.
I had some fun a while back using the digits of pi to drive a graphics turtle. Similar to a random walk but driven by the decimal digits of pi. Go a fixed length then turn in the direction given by 360 / (36 * digit). Made kind of an interesting animated video! Random walks using different bases to control the possible angles (3, 4, 5...) make interesting patterns, too.
Sorry for my late reply. Yes, “move on to the next instruction” means “skip to the next digit”. If you pick another starting point, presumably at random, then the process is no longer deterministic, which completely changes the problem.
The question of efficiency is a natural one. The paper claims that the method given is “asymptotically optimal”, but I didn’t find anywhere where they explain exactly what this means. It does seem from the experimental data in the paper that the digits of pi give better results than the digits of Champernowne’s constant, even though pi is not known to be a normal number.
Do you have any publicly available videos from your graphics turtle experiment?
True, a random new starting position wouldn't work. I was thinking you could reset to the original starting point. Thinking about that, it would ultimately depend on whether the digit string that led to being blocked ended at a more favorable or less favorable position relative to the start position and next digits. Seems as if that could go either way and end up being a wash. (Though some part of me thinks some exploration of the maze has to be better than starting over.)
I've been pondering trying it for myself. I have a maze generator. I have a file with ten million decimal digits of pi, but I'd need either base 4 or binary (and then using every two bits as an instruction). Got a lot on my plate right now, but I'll keep it in mind. Might be simple enough to implement.
Champernowne's constant is certainly normal over time, but I wonder if its generation doesn't give it a strange structure on the short scale. As it grows, you'd have "...56001560025600356004..." which seems different from the seemingly random digits of pi. (I had some fun verifying that every possible six-digit sequence does exist at least once in the first ten million digits of pi. A frequency analysis of single-, double-, and IIRC triple-digit sequences showed those digits to be very close to normal.)
Heh, you're right, it does. I suppose 10 million "brush strokes" combines to something very image-like somewhat like how pixels make a picture. Your posts and this conversation have me thinking of some new videos I could do. (At the least, I could upgrade those videos to HD. I'd forgotten they're only 720p. And it would be interesting to see what a "Paths of Champernowne" might look like. Maybe the shape provides some insight to why that paper says pi works better.)
I do know of Dali's painting (very cool). That tesseract net seems appropriately called a "tesscross". I spent some time a while back trying to gain an intuition about tesseracts, which fascinate me. After a lot of thinking and several posts digging into them, I think I sorta kinda in a way get 4D. I keep trying to look along the W axis... 😁
For any maze there are only a finite number of states, so there is a sequence which works for that maze by assuming an initial state, exiting from there, if it doesn’t work crossing off from your list of possible initial states the one that was used up, assuming another initial state, applying the moves you made so far to derive your current state, exiting from there, it that doesn’t work crossing that second assumed initial state off your list, etc.
Any normal number will obviously have somewhere in its sequence of digits the sequence that works for the maze you’re in, so if you haven’t escaped by the time you reach that point you will escape with that sequence.
You're right that any normal number will obviously contain the solution somewhere. The issue is that by the time the robot reaches that point in the sequence, it will probably be at a completely different place in the grid. A related problem, also considered in the paper, is to find a synchronizing sequence for the maze, meaning one that is guaranteed to move the robot to a specific place in the grid, regardless of where it starts.
Some other potential issues with with your proposed solution are (a) that it contains clauses such as "if that doesn't work, then do this:" and (b) that it requires the robot to retain knowledge of things that have already been tried. The point of a universal plan is to avoid these things: there needs to be one true list of instructions (albeit an infinite list) that is guaranteed to work if it is followed, for any choice of maze, start point, and end point.
My solution does that! I’m sure you misunderstood it.
The first point is that, for a given maze, there exists a sequence which works for that maze even if you don’t know where you are starting from in that maze. You can deterministically derive it by the method I gave, the key insight being that when you make a new assumption about your starting point, you apply the previous unsuccessful sequence in an internal simulation to figure out what that assumption about initial state implies that your current state is, but all that matters is that some such sequence exists, this procedure isn’t part of what you need the robot to know. For the general case, you don’t need to make any assumptions or follow any algorithm or know which maze you are in, you just have to have a normal number.
Doesn't your method require us to be able to make conclusions such as "sequence X fails to solve the maze problem when applied to starting point x"? Is this even a computable question?
All solutions to a puzzle like this assume that you are told when you have exited the maze and can stop, even though the infinite sequence can be continued.
My “method” is simply “follow the digits of the normal number until you have exited the maze”.
My proof uses as a lemma that if you know which maze you are in but not where in that maze you are, there is a computable way out, but that lemma is only used to establish the existence of a sequence universal for that particular maze which gets out of that maze no matter where you started in it and what previous moves you made in it.
>> "We can then interpret the base 4 digits of p as directions (up, down, left, or right) with the understanding that if the robot tries to move in an obstructed direction then it does nothing and moves on to the next instruction."
I'm not clear on the latter part of that, what it means to move on to the next instruction. Just skip to the next digit, I assume? I wonder what would happen if you reset to the starting position and picked another starting point in the digit sequence. Though, if we're simulating an actual robot navigating, that doesn't fit.
I'm curious about the efficiency. It would be interesting to see how often points in the maze are revisited. Does the robot spend a lot of time wandering around a small area.
It is a cool way to approach mazes with loops preventing a right- (or left-) hand rule from working. I have a maze generator I wrote. Might be fun to try this.
I had some fun a while back using the digits of pi to drive a graphics turtle. Similar to a random walk but driven by the decimal digits of pi. Go a fixed length then turn in the direction given by 360 / (36 * digit). Made kind of an interesting animated video! Random walks using different bases to control the possible angles (3, 4, 5...) make interesting patterns, too.
Sorry for my late reply. Yes, “move on to the next instruction” means “skip to the next digit”. If you pick another starting point, presumably at random, then the process is no longer deterministic, which completely changes the problem.
The question of efficiency is a natural one. The paper claims that the method given is “asymptotically optimal”, but I didn’t find anywhere where they explain exactly what this means. It does seem from the experimental data in the paper that the digits of pi give better results than the digits of Champernowne’s constant, even though pi is not known to be a normal number.
Do you have any publicly available videos from your graphics turtle experiment?
True, a random new starting position wouldn't work. I was thinking you could reset to the original starting point. Thinking about that, it would ultimately depend on whether the digit string that led to being blocked ended at a more favorable or less favorable position relative to the start position and next digits. Seems as if that could go either way and end up being a wash. (Though some part of me thinks some exploration of the maze has to be better than starting over.)
I've been pondering trying it for myself. I have a maze generator. I have a file with ten million decimal digits of pi, but I'd need either base 4 or binary (and then using every two bits as an instruction). Got a lot on my plate right now, but I'll keep it in mind. Might be simple enough to implement.
Champernowne's constant is certainly normal over time, but I wonder if its generation doesn't give it a strange structure on the short scale. As it grows, you'd have "...56001560025600356004..." which seems different from the seemingly random digits of pi. (I had some fun verifying that every possible six-digit sequence does exist at least once in the first ten million digits of pi. A frequency analysis of single-, double-, and IIRC triple-digit sequences showed those digits to be very close to normal.)
Yes, all my videos are on my YouTube channel:
https://www.youtube.com/user/TheWyrdSmythe/videos
If you scroll down to the "Paths of ..." videos, you'll find two done using pi.
Thanks for the link to your videos. “Paths of pi” looks a lot more like an actual drawing than I imagined.
Do you know Dali’s painting “Corpus hypercubus”? Your unfolding tesseract video reminds me of it.
Heh, you're right, it does. I suppose 10 million "brush strokes" combines to something very image-like somewhat like how pixels make a picture. Your posts and this conversation have me thinking of some new videos I could do. (At the least, I could upgrade those videos to HD. I'd forgotten they're only 720p. And it would be interesting to see what a "Paths of Champernowne" might look like. Maybe the shape provides some insight to why that paper says pi works better.)
I do know of Dali's painting (very cool). That tesseract net seems appropriately called a "tesscross". I spent some time a while back trying to gain an intuition about tesseracts, which fascinate me. After a lot of thinking and several posts digging into them, I think I sorta kinda in a way get 4D. I keep trying to look along the W axis... 😁
Why isn’t this intuitively obvious?
For any maze there are only a finite number of states, so there is a sequence which works for that maze by assuming an initial state, exiting from there, if it doesn’t work crossing off from your list of possible initial states the one that was used up, assuming another initial state, applying the moves you made so far to derive your current state, exiting from there, it that doesn’t work crossing that second assumed initial state off your list, etc.
Any normal number will obviously have somewhere in its sequence of digits the sequence that works for the maze you’re in, so if you haven’t escaped by the time you reach that point you will escape with that sequence.
You're right that any normal number will obviously contain the solution somewhere. The issue is that by the time the robot reaches that point in the sequence, it will probably be at a completely different place in the grid. A related problem, also considered in the paper, is to find a synchronizing sequence for the maze, meaning one that is guaranteed to move the robot to a specific place in the grid, regardless of where it starts.
Some other potential issues with with your proposed solution are (a) that it contains clauses such as "if that doesn't work, then do this:" and (b) that it requires the robot to retain knowledge of things that have already been tried. The point of a universal plan is to avoid these things: there needs to be one true list of instructions (albeit an infinite list) that is guaranteed to work if it is followed, for any choice of maze, start point, and end point.
My solution does that! I’m sure you misunderstood it.
The first point is that, for a given maze, there exists a sequence which works for that maze even if you don’t know where you are starting from in that maze. You can deterministically derive it by the method I gave, the key insight being that when you make a new assumption about your starting point, you apply the previous unsuccessful sequence in an internal simulation to figure out what that assumption about initial state implies that your current state is, but all that matters is that some such sequence exists, this procedure isn’t part of what you need the robot to know. For the general case, you don’t need to make any assumptions or follow any algorithm or know which maze you are in, you just have to have a normal number.
Doesn't your method require us to be able to make conclusions such as "sequence X fails to solve the maze problem when applied to starting point x"? Is this even a computable question?
All solutions to a puzzle like this assume that you are told when you have exited the maze and can stop, even though the infinite sequence can be continued.
My “method” is simply “follow the digits of the normal number until you have exited the maze”.
My proof uses as a lemma that if you know which maze you are in but not where in that maze you are, there is a computable way out, but that lemma is only used to establish the existence of a sequence universal for that particular maze which gets out of that maze no matter where you started in it and what previous moves you made in it.