PRE2018 1 Group3 0969145

From Control Systems Technology Group

Revision as of 13:29, 7 October 2018 by S158456 (Talk | contribs)
Jump to: navigation, search



A robot navigating through a supermarket will not only have to avoid collision but also choose a route to their destination. The obvious choice is of course to always take the shortest path, however a supermarket will typically have multiple paths of the same length because of their grid-like layout and distance should not be the only factor we take into account when choosing a path, for example we might want to avoid dense groups of people. This research looks at the theoretical options for choosing a path and compares them.

Note that people will still be encountered and will still have to be avoided locally but the point is to minimize the amount this occurs.

relevant requirments

The main requirements we are taking into consideration here are:

1. Customers should feel safe

2. Robots should not get in the way

These requirements are respected by trying to avoid situations that are difficult to navigate through, minimizing situations where the robot has to move erratically or get too close to people to avoid them.


Compare different navigation algorithms, potentially by simulating them in a program like NetLogo.



The robot has to function in a supermarket which is a mostly fixed environment. When navigating this environment it would be ideal to take advantage of the fact that the whole supermarket could be observed at all times by cameras. At the very least we can assume we know the general layout of the store so that the only thing we must watch for is obstructions. Up to date information on where people and other potential obstructions reside in the supermarket allows the robot to plan a path that minimizes encounters.


People are constantly moving around the supermarket. Their movement may to some extent be predictable but a robot in a supermarket environment should not risk nearly bumping into people or moving out of the way at the last moment since these actions could frighten or annoy some people.

general descriptions of potential algorithms

Utilizing up to date information on the state of the supermarket in navigation If we assume we can see the locations and movement of every person in the supermarket we can try to take this into account when navigating the supermarket, this would allow us to completely avoid busy aisles, where avoiding the people could scare or annoy the people because of the amount of movement required. A very simple implementation of this that would work in a store that is not very busy can be described easily in terms of the standard shortest path method. Mark the area that you expect the people that are in the store could be in within an approximation of the time that it should take you to reach your destination then find the shortest path that avoids this area. Alternatively each aisle could be marked with a time, until this time you expect it is unlikely that anybody is there. These times can then be used to find a path where it passes each point before the time that it is marked with. The idea here is that the closer you already are, the less time people have to move into the isle and thus the smaller the chance that there will be people by the time you get there. If no valid path is found the amount you expect people to move should reduced and if no paths are possible even if nobody moved it should simply take the shortest path. ==improvements== There are 2 main ways to improve this simple algorithm. First it is possible to change the planned route while already underway, simply rerunning the algorithm from the current position while prohibiting backtracking would be a simple implementation of this. The other thing that should be improved is that it should avoid larger groups of people instead of just trying to avoid people altogether, one easy way to implement this is to add a cost based on the concentration of people in the area to the distance of each isle that is used to find the shortest path.

advanced movement prediction

If we want to be complete we should produce for each aisle a list of times and the estimated probability distribution of the amount of people that are there at that moment. If we can detect where people are moving, how old they are and potentially any information that would affect how they move this can be taken into account. A quick example:

in aisle 1 in 20 seconds. there is a ~50% chance of 1 person being there and a ~25% chance of 2 people being there and ~0 chance of 3+ people being there so if we expect to e there over 20 seconds we assign some extra length to this aisle based on the cost of these chances.

Personal tools