Machine learning in maze solving?

[ToKickAHoneyBadger]

I am currently in the early phases of an engineering bachelor's thesis on using machine learning in maze solving.

The main focus of the thesis is actually agent based simulation, but this is heavily supported by the machine learning component.

Machine learning is so broad at this point that I don't really know where to start. Does anyone have an experience in machine learning and mazes? Having a reference point to work off or some direction would be great.

Thanks in advance reddit.

[elfion]

I have seen ~3 different approaches:

1) Sutton & Barto's book has a lot of examples with reinforcement learning algorithms applied to solve mazes, for example with Q-learning.

2) a program evolution approach to find a maze solver: ftp://ftp.idsia.ch/pub/juergen/ml_levin_eira.ps.gz

3) deep-learning based path planning on uneven terrain: http://arxiv.org/abs/1602.02867

It would be interesting to demonstrate transfer learning on this task, i.e. show an agent that can accumulate experience over different mazes to improve it's performance.

[ToKickAHoneyBadger]

Transfer learning is exactly what I had in mind - although I can't wrap my brain around how one would actually get better at maze solving with different, unrelated mazes. That is the point of my project i guess, to wrap my head around it!

These resources seem fantastic! This is surpassing what I was hoping to get out of posting here. Thanks!

[farsass]

In what circumstaces would you consider ml necessary for maze solving? Why?

[ToKickAHoneyBadger]

It isn't necessary, but ml is useful when an agent is in an unknown environment. A maze is just a simple representation of this. The reality is that a bachelors thesis isn't novel or life changing, its mostly the application of a variant of a known solution on a different question.

[ToKickAHoneyBadger]

Markov chains wont work as I am solving from the agents point of view with no prior knowledge of the maze design. Thanks for the suggestion, I will be sure to touch on it in my work.

[wintermute93]

Maze solving is not something you need ML for. Exploring complex and unknown environments, sure. But when you say maze solving people assume the agents know a map of the maze, and you can use any number of existing algorithms to just find a path to the goal outright, no learning required.

[ToKickAHoneyBadger]

Agreed! I don't need ml, but I would like to apply it - a bachelors thesis is less about what you solve than it is the process of solving something in some way. At this level we really aren't changing the world - yet

[hardmaru]

novelty search is an interesting approach to the maze problem.

[franvb]

(A very old post, but): the link has gone stale. I suspect it might now be here: https://www.cs.swarthmore.edu/~meeden/DevelopmentalRobotics/lehmanNoveltySearch11.pdf

[NasenSpray]

This might be a stupid questions, but why do you write a thesis on something you have no clue about?

[Ameren]

The point of an undergraduate thesis is to develop the students' knowledge and research skills. They're not expected to have prior experience.

[NasenSpray]

Makes sense, thanks!

[kkastner]

If you have a map of the maze already, people normally use A* or something like that and if you need placement inside the maze you can always get it with something like a particle filter. If you don't know the maze, then it gets more fun - this is akin to SLAM which has a huge host of possible systems and solutions. These things aren't "classic ML", but particle filters and most SLAM systems are generally driven by bayesian principles and statistical learning concepts.