PRE2018 1 Group3 0969145

From Control Systems Technology Group

Revision as of 12:39, 14 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.

Human robot interaction

One problem we encounter in a supermarket environment is not entering people's personal space when passing them in the aisles. This [1] paper describes this exact scenario. They describe a solution for manoeuvering around people in a corridor which comes down to always passing them on their right side. The lack of space in such a corridor can however mean that the personal space of some people is still invaded. Some articles like this one [2] describe this personal space, this article in particular also found that a robot that approaches slowly can make people more unconfortable. In the case of people moving in a corridor it seems that this space is eliptical extending in front of the person [3] and people this [4] article also claims that people prefer robots to stay out of their intimate zone which is given by a distance up to 45cm.



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.


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. Higher concentrations of people should be weighted much higher since these are the situations we defintely want to avoid.


Personal tools