PRE2018 1 Group3 0969145

introduction

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.

goal

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

Human robot interaction

A robot that navigates a supermarket environment will have to interact in humans in some way, even if it is simply by going around them. This interaction occurs when the robot encounters a person when moving around the supermarket. When a robot like this is designed a big question is how can we make this interaction as pleasant as possible for the customers in the store. There are a couple of aspects where we can help achieve this:

Appearance

Should the robot be visible or difficult to notice. Should the robot be made to somehow appear friendly. Should to robot look nice, like a piece of art.

Ways to achieve this are things like colour and size.

Sound

The robot should be silent enough to not be annoying but maybe it should also not be so quiet that people do not notice it and get surprised by it.

Does it use sound to announce Its presence, communicate.

Movement

The robot should try to move caryfully around people. It should not move to fast and it should try to stay out of their personal space as much as possible.

personal space

One problem we encounter in a supermarket environment is not entering people's personal space when passing them in the aisles. This 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 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 and people this article also claims that people prefer robots to stay out of their intimate zone which is given by a distance up to 45cm.

From this we can conclude that invading somebodies personal space is going to happen from time to time and that this might cause at least some minor discomfort. To minimize this discomfort it may be interesting to minimize encounters where this happens.

environment

Benefits

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.

Difficulties

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.

surveillance cameras

The surveillance cameras could be used for more than just detecting people's current position. For example, a person's previous movements can be used to predict their future ones.

human behaviour

Tracking the movement of people moving through the store could even allow us to learn the behaviour of people in general and learn te recognize certain patterns. People could even be judged by there appearance to predict their movement or maybe a person's movement can be predicted based on previous visits.

ethics

When collecting data on customers there is a big concern of privacy. What information can we store and can it be specific to a customer. A similar case is the selfscanning system from the supermarket chain Albert Heijn, where random checks can be based on previous store visits by that person

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