Friam

solving mazes

Classic

List

Threaded

17 messages Options

thompnickson2

solving mazes

Hi, All,

Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.

So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.

Nick

Nick Thompson

[hidden email]

https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

cody dooderson

Re: solving mazes

I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

On Sat, Feb 27, 2021, 1:48 PM <[hidden email]> wrote:

Hi, All,

Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.

So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.

Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

Alexander Rasmus

Re: solving mazes

Nick,

Assuming that every intersection is 3-way isn't enough to guarantee that the maze is simply connected, see attached. If you put the exit in the no go region then the wall following strategy doesn't work, as entrance and exit won't be connected.

Best,

Alex

On Sat, Feb 27, 2021 at 5:10 PM cody dooderson <[hidden email]> wrote:

I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

On Sat, Feb 27, 2021, 1:48 PM <[hidden email]> wrote:
Hi, All,

Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.

So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.

Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

thompnickson2

Re: solving mazes

Hi, Rasmus, It’s great to hear from you. I wondered about that, although the way I conceived of it was different. What, I wondered, if they put a smaller Hampton maze inside the goal box of a Hampton maze. I would walk right by the entrance not matter if I had my whiskers on the right wall or the left.

Hi, Cody, Thanks for the tip

Nick

Nick Thompson

[hidden email]

https://wordpress.clarku.edu/nthompson/

From: Friam <[hidden email]> On Behalf Of Alexander Rasmus
Sent: Saturday, February 27, 2021 6:43 PM
To: The Friday Morning Applied Complexity Coffee Group <[hidden email]>
Subject: Re: [FRIAM] solving mazes

Nick,

Best,

Alex

On Sat, Feb 27, 2021 at 5:10 PM cody dooderson <[hidden email]> wrote:

I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

On Sat, Feb 27, 2021, 1:48 PM <[hidden email]> wrote:
Hi, All,

Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.

So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.

Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/
- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

Jochen Fromm-5

Re: solving mazes

In reply to this post by cody dooderson

Jamis Buck is very interested in mazes. He even wrote a book about it named "Mazes for programmers"

https://www.jamisbuck.org/mazes/

It contains algorithms for generating and solving mazes

https://pragprog.com/titles/jbmaze/mazes-for-programmers/

-J.

-------- Original message --------

From: cody dooderson <[hidden email]>

Date: 2/28/21 01:10 (GMT+01:00)

To: The Friday Morning Applied Complexity Coffee Group <[hidden email]>

Subject: Re: [FRIAM] solving mazes

I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can.

On Sat, Feb 27, 2021, 1:48 PM <[hidden email]> wrote:

Hi, All,
Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.
So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.
Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

Roger Critchlow-2

Re: solving mazes

In reply to this post by cody dooderson

Okay Nick,

So you draw the maze as a graph where the nodes of the graph are positions in the maze that can be occupied, and the edges of the graph are one step open paths between adjacent positions. Easy to draw on graph paper, here is a site which generates graph paper pdfs for printing: https://incompetech.com/graphpaper/, just fill in the cells that are walls and draw lines to connect the remaining open cells. Each open cell is a node, each line connecting adjacent cells is an edge.

The graph of the maze must be connected or parts of the maze will be cut off from each other and no algorithm will ever work if it starts in the wrong connected component. Nasty trick to play on a rat.

If the graph of the maze contains loops, then wall following will get trapped in the loops, in fact, I think each loop defines a wall following domain, and to solve the maze you'll have to detect when you've completed a loop and switch to following the opposite wall when it's one you haven't already followed. If you just switch to the opposite wall at random, you'll most probably end up on the same loop going in the opposite direction.

Just to demonstrate how graph properties end up trapping the unwary, an open courtyard in your maze ends up being an area of fully connected graph, which is all loops all the time, which is a counter example to my proposal that "each loop defines a wall following domain" since lots of the loops in the courtyard will have no adjacent walls at all. So I must have meant something subtler than loop, something that is a loop that has walls on both sides.

-- rec --

On Sun, Feb 28, 2021 at 9:39 AM Jochen Fromm <[hidden email]> wrote:

Jamis Buck is very interested in mazes. He even wrote a book about it named "Mazes for programmers"
https://www.jamisbuck.org/mazes/

It contains algorithms for generating and solving mazes
https://pragprog.com/titles/jbmaze/mazes-for-programmers/

-J.

-------- Original message --------
From: cody dooderson <[hidden email]>
Date: 2/28/21 01:10 (GMT+01:00)
To: The Friday Morning Applied Complexity Coffee Group <[hidden email]>
Subject: Re: [FRIAM] solving mazes

I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

On Sat, Feb 27, 2021, 1:48 PM <[hidden email]> wrote:
Hi, All,
Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.
So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.
Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

thompnickson2

Re: solving mazes

Hi Roger,

Here is a picture of a typical rat maze. I was going to crop it but I thought the image of a former English major trying to manipulate technology was too funny not to send along. Notice that it’s all t’s.

You wrote:

This is the kind of thing that rats should be extremely good at. If there is one thing a rat should know it’s where it’s been and how recently and even, how often.

Nick

Nick Thompson

[hidden email]

https://wordpress.clarku.edu/nthompson/

From: Friam <[hidden email]> On Behalf Of Roger Critchlow
Sent: Sunday, February 28, 2021 11:03 AM
To: The Friday Morning Applied Complexity Coffee Group <[hidden email]>
Subject: Re: [FRIAM] solving mazes

Okay Nick,

-- rec --

On Sun, Feb 28, 2021 at 9:39 AM Jochen Fromm <[hidden email]> wrote:

Jamis Buck is very interested in mazes. He even wrote a book about it named "Mazes for programmers"
https://www.jamisbuck.org/mazes/

It contains algorithms for generating and solving mazes
https://pragprog.com/titles/jbmaze/mazes-for-programmers/

-J.

-------- Original message --------
From: cody dooderson <[hidden email]>
Date: 2/28/21 01:10 (GMT+01:00)
To: The Friday Morning Applied Complexity Coffee Group <[hidden email]>
Subject: Re: [FRIAM] solving mazes

I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

On Sat, Feb 27, 2021, 1:48 PM <[hidden email]> wrote:
Hi, All,
Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.
So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.
Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/
- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

MAZE PIC.jpg (200K) Download Attachment

Stephen Guerin-5

Watching a Moose solve a Maze Re: solving mazes

In reply to this post by cody dooderson

Late September 2009, a young M0ose (Cody Smith) walked into the Santa Fe Complex.

He approached me and said he heard about the place and wanted to help contribute. He showed me some of his computational sketches on his laptop.

One that caught my eye was his Javascript breadth-first maze solver:
http://www.m0ose.com/oldpage/breadth_first_with_graph.html

and a genetic algorithm solver: http://www.m0ose.com/oldpage/maze_evolution8.html

His repository has grown over the decade: http://m0ose.com

Note his maze generator here: http://www.m0ose.com/javascripts/maze/test1.html
And his WebGL Doom maze walker from Ed Angel's WebGL class at SF_X: http://www.m0ose.com/javascripts/maze/testGl.html

-Stephen

_______________________________________________________________________
[hidden email]

CEO, Simtable http://www.simtable.com

1600 Lena St #D1, Santa Fe, NM 87505

office: (505)995-0206 mobile: (505)577-5828

twitter: @simtable

z oom.simtable.com

On Sat, Feb 27, 2021 at 5:10 PM cody dooderson <[hidden email]> wrote:

I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

On Sat, Feb 27, 2021, 1:48 PM <[hidden email]> wrote:
Hi, All,

Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.

So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.

Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

Edward Angel

Re: Watching a Moose solve a Maze Re: solving mazes

I used to give this problem to my graphics students. Here’s one 2D version

https://drive.google.com/drive/folders/1fTNJb4hhgR-6LySQspgM9k-J27KwuLpl?usp=sharing

It will generate a new maze each time it’s rerun. Every cell is connected to every other cell. Next step is to knock out two edge segments for an entrance and exit. Extrude all the segments up to get a 3D maze.

On Feb 28, 2021, at 10:33 AM, Stephen Guerin <[hidden email]> wrote:

Late September 2009, a young M0ose (Cody Smith) walked into the Santa Fe Complex.

He approached me and said he heard about the place and wanted to help contribute. He showed me some of his computational sketches on his laptop.

One that caught my eye was his Javascript breadth-first maze solver:
http://www.m0ose.com/oldpage/breadth_first_with_graph.html

and a genetic algorithm solver: http://www.m0ose.com/oldpage/maze_evolution8.html

His repository has grown over the decade: http://m0ose.com

Note his maze generator here: http://www.m0ose.com/javascripts/maze/test1.html
And his WebGL Doom maze walker from Ed Angel's WebGL class at SF_X: http://www.m0ose.com/javascripts/maze/testGl.html

-Stephen
_______________________________________________________________________
[hidden email]
CEO, Simtable http://www.simtable.com
1600 Lena St #D1, Santa Fe, NM 87505
office: (505)995-0206 mobile: (505)577-5828
twitter: @simtable
z oom.simtable.com

On Sat, Feb 27, 2021 at 5:10 PM cody dooderson <[hidden email]> wrote:
I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

On Sat, Feb 27, 2021, 1:48 PM <[hidden email]> wrote:
Hi, All,

Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.

So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.

Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

jon zingale

Re: Watching a Moose solve a Maze Re: solving mazes

This post was updated on .

In reply to this post by Stephen Guerin-5

Note that this is really slow. Is there a higher performance version of this algorithm?

Cody,

This statement piqued my interest. Is there somewhere I can see your code? If this algorithm is anything like diffusion limited aggregation (which at a glance it likely might be) then I suspect there really are not good optimizations that preserve structural clarity. Anyway, I am interested.

cody dooderson

Re: Watching a Moose solve a Maze Re: solving mazes

@Jonzingale. I think you are talking about the Cellular Potts page. The code for it is on Github, https://github.com/m0ose/onepagers/blob/master/potts2.html. I spent a lot of time tweaking values and just staring at that model.
I don't know enough about DLA to make a good comparison. Maybe it is similar in the way it randomly chooses a move whether it can perform the move or not.

[hidden email]. Here is Owen's homework assignment from back in 2011 for your class, http://backspaces.net/CS591/hw3/hw3.html .

Cody Smith

On Mon, Mar 1, 2021 at 9:35 AM jon zingale <[hidden email]> wrote:

Note that this is really slow. Is there a higher performance version of this algorithm? Cody, This statement piqued my interest. Is there somewhere I can see your code? If this algorithm is anything like diffusion limited aggregation (which at a glance it likely might be) then I suspect there really are not good optimizations that preserve structural clarity. Anyway, I am interested.
Sent from the Friam mailing list archive at Nabble.com.
- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

Marcus G. Daniels

Re: Watching a Moose solve a Maze Re: solving mazes

https://arxiv.org/abs/1508.05647

From: Friam <[hidden email]> On Behalf Of cody dooderson
Sent: Monday, March 1, 2021 10:52 AM
To: The Friday Morning Applied Complexity Coffee Group <[hidden email]>; Angel Edward <[hidden email]>
Subject: Re: [FRIAM] Watching a Moose solve a Maze Re: solving mazes

[hidden email]. Here is Owen's homework assignment from back in 2011 for your class, http://backspaces.net/CS591/hw3/hw3.html .

Cody Smith

On Mon, Mar 1, 2021 at 9:35 AM jon zingale <[hidden email]> wrote:

Note that this is really slow. Is there a higher performance version of this algorithm? Cody, This statement piqued my interest. Is there somewhere I can see your code? If this algorithm is anything like diffusion limited aggregation (which at a glance it likely might be) then I suspect there really are not good optimizations that preserve structural clarity. Anyway, I am interested.

Sent from the Friam mailing list archive at Nabble.com.
- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

jon zingale

Re: Watching a Moose solve a Maze Re: solving mazes

In reply to this post by cody dooderson

Thanks, man! I will take a look and let you know if any ideas pan out. It is
a pretty cool model and I am having a bunch of fun watching the little blobs
work their way through the "maze".

--
Sent from: http://friam.471366.n2.nabble.com/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

thompnickson2

Re: solving mazes

In reply to this post by thompnickson2

I want to push this conversation about mazes a bit. So, we a visual creatures and we tend to understand mazes as a visual problem, not a tactile or olfactory problem. The rat brings to a maze all sorts or skills that humans do not. So wall following is just a matter of putting the vibrissae on one side of your face on a wall and keeping them there until you get somewhere. You have all pointed out the flaws of wall following in the case that there is a maze hidden within a maze, in which case the rat will never enter the surrounded maze.

However the complications of introducing olfaction in to our understanding of the rat’s behavior are myriad. Let’s put a side the possibioity that the odor of the food diffuses down the maze. Let’s put aside the thought that stigmergy is at work here because the rat-runners are not expunging all odor cues from the maze between different rats, or different runnings of the same rat. Let’s ONLY consider the cues that a running rat leaves for himself. Olfactory cues being what they are, I assume that a running rat ALWAYS knows if he has been to a particular point in the maze, and how recently he has been there. He also knows what direction he was running whenever he encounters his own trail. And the rat always knows whether he has found food or not.If you add those skills to your AI maze running kit, don’t you add a lot?

So, for instance, add to wall following some rules about what you do if you encounter your own odor going in the opposite direction without a trace of food odor. That might lead you to change walls, in which case you would FIND the maze within the maze and eventually the maze-within-the-maze-within-the-maze .

Do any of you remember piglet tracking hefalumps? So add to your conception of the maze that you are solving it in the snow and that you leave footprints showing your direction of walking and little bits of crème brule falling off your beard where ever you go after you have been fed.

Eh?

Nick Thompson

[hidden email]

https://wordpress.clarku.edu/nthompson/

From: [hidden email] <[hidden email]>
Sent: Sunday, February 28, 2021 11:54 AM
To: 'The Friday Morning Applied Complexity Coffee Group' <[hidden email]>
Subject: RE: [FRIAM] solving mazes

Hi Roger,

You wrote:

This is the kind of thing that rats should be extremely good at. If there is one thing a rat should know it’s where it’s been and how recently and even, how often.

Nick

Nick Thompson

[hidden email]

https://wordpress.clarku.edu/nthompson/

Okay Nick,

-- rec --

On Sun, Feb 28, 2021 at 9:39 AM Jochen Fromm <[hidden email]> wrote:

Jamis Buck is very interested in mazes. He even wrote a book about it named "Mazes for programmers"
https://www.jamisbuck.org/mazes/

It contains algorithms for generating and solving mazes
https://pragprog.com/titles/jbmaze/mazes-for-programmers/

-J.

-------- Original message --------
From: cody dooderson <[hidden email]>
Date: 2/28/21 01:10 (GMT+01:00)
To: The Friday Morning Applied Complexity Coffee Group <[hidden email]>
Subject: Re: [FRIAM] solving mazes

I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

On Sat, Feb 27, 2021, 1:48 PM <[hidden email]> wrote:
Hi, All,
Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way.
So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy.
Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/
- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

jon zingale

Re: solving mazes

Ok, so getting rid of the walls altogether can we imagine these as SteveG's
ants? Is there anything more to it?

--
Sent from: http://friam.471366.n2.nabble.com/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

thompnickson2

Re: solving mazes

Well, except that mazes vastly reduce the number of possibilities and ought,
therefore, to be way simpler than the ant problem

Also, I think that rats get a bit more information from their olfactory cues
than steve's ants do. On the other hand, there are many ants working at
once, and we are concerned, in the maze situation, with a single rat in a
clean maze, a laughably over simplified problem give a rats normal way of
life. It is what it is.

Nick

Nick Thompson
[hidden email]
https://wordpress.clarku.edu/nthompson/

-----Original Message-----
From: Friam <[hidden email]> On Behalf Of jon zingale
Sent: Tuesday, March 2, 2021 1:26 PM
To: [hidden email]
Subject: Re: [FRIAM] solving mazes

Ok, so getting rid of the walls altogether can we imagine these as SteveG's
ants? Is there anything more to it?

--
Sent from: http://friam.471366.n2.nabble.com/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam un/subscribe
http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
FRIAM Applied Complexity Group listserv
Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
FRIAM-COMIC http://friam-comic.blogspot.com/
archives: http://friam.471366.n2.nabble.com/

Edward Angel

Re: solving mazes

Constructing a maze by removing walls and finding a path through a maze are very similar and can be done by recursion or backtracking, both of which are equivalent to a mouse leaving his scent along a path and then backing up to a place opening without a scent when it hits a dead end.

Ed

> On Mar 2, 2021, at 10:07 AM, <[hidden email]> <[hidden email]> wrote:
>
> Well, except that mazes vastly reduce the number of possibilities and ought,
> therefore, to be way simpler than the ant problem
>
> Also, I think that rats get a bit more information from their olfactory cues
> than steve's ants do. On the other hand, there are many ants working at
> once, and we are concerned, in the maze situation, with a single rat in a
> clean maze, a laughably over simplified problem give a rats normal way of
> life. It is what it is.
>
> Nick
>
> Nick Thompson
> [hidden email]
> https://wordpress.clarku.edu/nthompson/
>
> -----Original Message-----
> From: Friam <[hidden email]> On Behalf Of jon zingale
> Sent: Tuesday, March 2, 2021 1:26 PM
> To: [hidden email]
> Subject: Re: [FRIAM] solving mazes
>
> Ok, so getting rid of the walls altogether can we imagine these as SteveG's
> ants? Is there anything more to it?
>
>
>
> --
> Sent from: http://friam.471366.n2.nabble.com/
>
> - .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
> FRIAM Applied Complexity Group listserv
> Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam un/subscribe
> http://redfish.com/mailman/listinfo/friam_redfish.com
> FRIAM-COMIC http://friam-comic.blogspot.com/
> archives: http://friam.471366.n2.nabble.com/
>
>
> - .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .
> FRIAM Applied Complexity Group listserv
> Zoom Fridays 9:30a-12p Mtn GMT-6 bit.ly/virtualfriam
> un/subscribe http://redfish.com/mailman/listinfo/friam_redfish.com
> FRIAM-COMIC http://friam-comic.blogspot.com/
> archives: http://friam.471366.n2.nabble.com/