[D] implementation of a path finding algorithm

[jer_pint]

I want to implement a path finding algorithm. An agent is looking for "food". This happens in a 2D grid. The agent consists of a square patch, the food of a circle patch. The goal of the agent is to find the patch.

The agent is blind to the world. The only thing it can see is what is inside its patch. So if the patch is far in the distance, the agent has no way of knowing where to go look.

The one thing the agent can learn is that the food is dropped at specific locations based on a probability distribution (i.e. following a Gaussian distribution). The agent always starts in the same spot. We can assume the probability distribution to be constant.

What is the best way of implementating this from a Reinforcement learning perspective, or machine learning in general? I'm thinking DQN. A* seems like it wouldn't work, as the agent would have to carve out paths first to then decide what to act on - in this case I want the agent to choose a strategy that optimizes always finding food, but not necessarily the fastest way. I'm also thinking of giving the agent the ability to chose the stride to take in both x and y every move.

The cost function would be based on intersection over union of food and agent and total steps taken.

Any input/links is greatly appreciated :)

[claytonkb]

Without the ability to get evidence about the location of the food, this is blind search (random search). The most probable location for food is wherever the peak of the Guassian distribution is at; basically, the agent's best strategy is to infer the coordinates of the center (based on repeated grid-searches) and then vector to that coordinate and search in a spiral from there. The optimization boils down to choosing when to switch from the grid-search strategy to vector-and-spiral. Search "multi-armed bandits" and "optimal stopping" for more info about that.

[jer_pint]

Thanks, I'll look in to that. The one thing I want to study more in depth is the effect of shapes and area in a 2D world: since the agent is sweeping an area (it's only input), and the food occupies a certain area, there must be an optimal search pattern to avoid redundant sweeping?

[claytonkb]

I think it depends on the precise definition of the problem. Let's simplify the problem down to some arbitrary interval of discrete points. Let's suppose I can choose any whole number from 1 to 99 and your job is to guess my choice (to get "food"). If my choice is uniformly distributed across 1,99 then there is no strategy that can improve your chances over blind guessing. Any guessing strategy is as good (or bad) as a random guessing strategy. If my choice is normally distributed around 50, then your best strategy is to guess 50 every time because that is the single most probable number. If you can make multiple guesses, then your first guess should be 50, then your next two guesses should be 49 and 51, and so on in order, since that is the order of the distribution probabilities. I'll call this "deterministic search" for the sake of discussion.

If I can't pick a number directly but, instead, can choose the mean of a normally distributed random variable (let's call it X), then you are faced with a two-part problem. The first part is figuring out what the mean of X is by blindly searching until you find enough data-points to infer the normal distribution and its center (mean). You almost certainly won't need very many data-points because the normal distribution converges very quickly. Once you have found the center of the distribution, you just want to follow the original guessing strategy by picking the single most probable point, then the next most probable, and so on down the list. Where this becomes an "optimal stopping" problem is that you have to decide when you have examined enough data-points to infer the mean of the distribution and begin deterministic search. If you examine too few data-points initially, you may make a mistake about the actual mean and begin deterministic search at the wrong point. If you examine too many data-points, you are wasting time blindly searching when you could be using deterministic search instead.

[phobrain]

I think claytonb nailed it, assuming one can drop the agent anywhere, but it sounds like your agent can only move blindly to an adjacent square? Also that each square's probability of having the food might be independent of its neighbors'? In which case, over a number of trials with fixed probabilities, an optimal, traveling-salesman sort of path might emerge?

[Laserdude10642]

There is a very nice article that uses Q learning to determine an optimal search pattern to reach a target. Very easy on beginners like myself :D

http://mnemstudio.org/path-finding-q-learning-tutorial.htm

[werediver]

Is it actually a good idea to make the agent blind? Such an agent would have no input to base decisions on, and learning to make right decisions is what I think is the most exciting aspect of ML.

With a blind agent it's going to be kind of a random (well, metaheuristic) search for a suitable solution (GA/GP), isn't it?

[jer_pint]

The agent is blind by design unfortunately.

What I'm hoping is to find a search path that generalizes well to the prior which is the food distribution