3
$\begingroup$

I am working on a project which maps to a variant of path finding problem. I am new to this area and I would be very grateful if you could give suggestions/ point to libraries for relevant algorithms.

A simplified version of my problem statement is as follows-

Goal: On a 2D grid, starting from a fixed point reach the destination in exactly N steps.

Allowed actions: 1. At every position, you have a choice of up to three moves (i.e. straight, curve left, curve right). 2. You cannot collide with the path traveled so far (just like in the snake game).

Dimension of the grid: N x N where N is between 100-1000

Scalable: Later on, the problem will be scaled to have multiple such snakes going between different pairs of points on the grid. The ultimate goal is to get ALL snakes to reach their respective destinations in a fixed number of steps without any collisions.

TL;DR: Essentially I have to find a fixed length path on a dynamically generated directed graph. Is there a better choice than a A* / greedy heuristic? Is it worth taking a Q- learning approach?

A rudimentary one snake version written in python can be found here - Github Link Thanks in advance!

$\endgroup$
  • $\begingroup$ I feel the need to add my own snake game... w3schools.com/code/tryit.asp?filename=FOVMY741OC7V $\endgroup$ – FreezePhoenix Apr 10 '18 at 12:04
  • $\begingroup$ The game works great. The user can press left/right keys for controlling the snake. As far as i understand the OP needs a pathplanning and/or q-learning algorithm for bringing the snake autonomously into the goal. Such a feature is very difficult to implement. The SO website has an own tag for the problem a-star. $\endgroup$ – Manuel Rodriguez Apr 10 '18 at 13:06
1
$\begingroup$

A first prototype for the snake game is working, see the figure below. It was realized with the RRT algorithm, or to be more specific with the “hierarchical RRT” variant. That was the easy part, because it is classical pathplanning. The second aspect in the OP is a bit more difficult to handle: heuristics and q-learning. Usually there are constraints given like “bringing all snakes to the goal” or “restrict the number of collisions”. Such features are hard to implement because they are knowledge driven. The problem is to create a formal model which can be later solved with q-learning and similar techniques. I believe, the way to go is to first program a game, which can be played manually and calculates only the points for a human player. This game works as a model to program against it. The second step is to write an agent which reaches in the game a certain score.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Thanks for your response. 1."A first prototype for the snake game is working, see the figure below." What do you mean by that? I am not able to properly understand the picture shared. Does 0 mean start and 1 mean end position? 2. I have working model for the game (Github link in the question). My question is asking for ideas on creating agents. $\endgroup$ – Pranav M Apr 10 '18 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.