View source for PRE2018 1 Group3 0969145

=introduction=
The navigation algorithms for a robot in a supermarket are explored.

==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. People in supermarkets will show behaviour unique to supermarkets like constantly stopping to pick out products.


==relevant requirements==
The main requirements we are taking into consideration here are:

User requirements
1. The robot should not invade a person’s  personal space.
2. The robot should not get in the way of a person’s path
3. The robot should move predictably. 
4. The robot should not surprise people with its presence 
5. The robot should get to its destination as fast as possible.
6. Privacy

These requirements are mentioned in the various  articles describing robot navigation. The main objective here is to make people comfortable around the robots

==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 <ref> https://smartech.gatech.edu/bitstream/handle/1853/37968/04107827.pdf </ref> 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 <ref> https://www.doi.org/10.1145/2157689.2157769 </ref> 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 <ref> https://smartech.gatech.edu/bitstream/handle/1853/37968/04107827.pdf </ref> and people this <ref> https://smartech.gatech.edu/bitstream/handle/1853/37968/04107827.pdf </ref> 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.




=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 to recognize certain patterns, these patterns can be based on the locations that people visit in the store.  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. 
==== privacy ====
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 <ref> https://www.nrc.nl/nieuws/2018/04/06/hoe-bepaalt-de-zelfscankassa-welke-klanten-gecontroleerd-worden-a1598456 </ref> 

=Behaviour=
When we are observing our supermarket with cameras there are some questions we must ask:
What can we use this camera footage for? , ethical and legal questions. The questions is simple if we only think about using the footage directly but what if we use it to study people’s behaviour. 
When we look at behaviour there are a number things we can separate.
behaviour model for people walking in a supermarket.
behaviour model for people when a robot approaches. – can also be based on robot mounted camera.

Behaviour prediction specific to a person based on: 
Current behaviour.
Location.
Behaviour in previous visits assuming we can identify people.
Things like appearance, maybe data from their phone.

All of these could also be automatically learned by observing people which can create a model very specific to the supermarket. There are of course ethical and legal questions when we use people’s data In this way.
First a more precise description is given of the information we can use for ways of predicting customer behaviour based on existing technology, ways of implementing this for the robots navigation are then explored  and finally these options are analysed from an ethical and legal standpoint. 
==Usable data==
First we look at the specific pieces of information we can use for our model of their behaviour:
===Time and Date===
We can use The current date and time as this may affect people’s behaviour. For example, people may be in more of a hurry when it is nearly time for dinner.
===Their location===
A customer will over their entire visit always move from the entrance to the exit (cash desk) so their location can give away which direction they will most likely move depending on the store layout. Some places might also have people stand still for longer periods of time, people might take longer deciding between certain types of products compared to others. 
===Their current movement===
The speed and direction a customer is currently moving is probably the most obvious information to use. People do not tend to suddenly change direction so it is fair to assume people will either keep moving in their current direction or stop. People that are standing still are more unpredictable.
===Relationship with others===
Some people may be shopping together in which case their movement patterns will likely be connected. Some people may always be moving next to each other for example.
===Their previous movement===
If we can track a person’s movement through the store we can make a very good guess on which direction they will go next. A person is most likely not going to backtrack to locations they have already been, of course there is always the probability they forgot something but most of the time they should be heading to places they have not been yet.
=== previous visits===
If we can identify people we can go even further, a person’s habits could be analysed based on previous visits. For people that visit often this should produce a very accurate model for how they tend to move. 
=== miscellaneous data===
Miscellaneous information like a person’s appearance or maybe even the wifi-signal they send out: https://dl.acm.org/citation.cfm?id=2611266 , the MAC-adress  in particular could be used to uniquely identify a person. 
===sharing data===
Data could also be shared between different supermarkets, this could potentially extend to other types of stores and services as well and could even be used for things like targeted advertisements. (https://medium.com/wibson/how-much-is-your-data-worth-at-least-240-per-year-likely-much-more-984e250c2ffa estimates that facebook earned $240 per capita from personal data in 2016)


==Using this information==
These information can be used to make models in a multitude of ways. 
===General model===
A general model can be created based on this information that can be applied to any customer, this model can constantly be updated and improved based on the data collected. The model can be dependent on mentioned pieces of information and should probably be based on an existing model for human behaviour.
===Customer specific model ===
If we can identify a person as a regular shopper we can create a model based on their specific behaviour. The accuracy of such a model would depend on how frequent they visit.


===other uses===
It could be used to optimise the store layout which was already described in 2002 https://www.sciencedirect.com/science/article/pii/S0969698902000103 . Another use would be to improve security with self-checkout, since it can see if you went somewhere and did not scan a product there which could be used as a basis for a ‘random’ check.
===Example from doi:10.1109/srii.2012.115 (2012)===
This paper describes the following key figures:  Speed, stops, Duration of Stay and Visits. It describes ways to utilise this including spotting people that are searching something so that they can be helped and displaying special offers they might be interested in using electric signs. It also suggests that other things than movement data could be used including socio-demographic factors.

If we apply this to our robot we could have it identify and help people that need assistance because they are for example, looking for something.
==Ethical and legal aspects==
When we are collecting this data on customers we need to ask whether this is ok legally and ethically. The main questions here are exactly how much are you allowed to remember about your customers without explicitly asking consent and how are you allowed to use it. 

https://www.emeraldinsight.com/doi/abs/10.1108/09590550010356831 (2000) 
This paper addresses ethical concerns when using camera footage for research. Import things to take away from this are:
It is better inform people that they are watched and how. When informing people it is important that everybody is informed so this means that if we  put up a sign to inform people we need to think about blind people since it would not help them.
There should not be more data stored than necessary.
Consent, especially for non-research purposed like marketing. Consent is also needed for sharing data with others.
Data should never be stored to long, with suggested duration differing between 30 days and 1-year. In our case with the robot the raw data could be deleted after a day. 
When we can identify people on our footage we have to comply with data protection legislation.

They quote the EU directive on privacy:
``legitimate and clearly defined purpose, discloses that purpose to the person, gets their permission to use it for that purpose and keeps the data only so long as thay are needed for the stated purpose'' (Minehan, 1999)
===conclusion===
If we collect personal data, where we can identify people there are a lot of requirements that we have to satisfy like asking for consent and making clear what the data will be used for. 
If we collect data hat is not personal we do not really have any ethical concerns aside from the usual that come with the camera footage. This means we should not recognize people when the re-enter the store and only keep the anonymous statistics. We can still collect data on how people move depending on things like location ,previous movement and even appearance. So most applications like spotting people that need help, optimising store layout,  improving a model for customer movement used for navigation and security are still possible. If we do not collect personal information we miss out on a personalised customer model which might be unnecessary anyway if we have a sufficient general model and we miss out on things like personalised advertising (on electric signs for example) and sharing the personal data with others (for their advertising).
==current regulation==
https://business.gov.nl/regulation/cctv-monitoring/
“As a shopkeeper, you may install CCTV cameras in and around your shop. However, you must indicate clearly to customers and employees that CCTV cameras are in use. You may not install cameras at locations where they violate the customer’s privacy, for example in fitting cubicles.”


https://business.gov.nl/regulation/protection-personal-data/ also states that
“You must take suitable measures to protect data pertaining to your customers and employees. You may not, for example, collect and further utilise more personal data than absolutely necessary. You must also limit access to personal data.”
===conclusion===
A sign that says that cameras are watching is already being used in supermarkets so this should suffice if we do not collect any personal information. If we do collect personal data we must be extra careful and we will need some form of explicit consent just like how most websites have to ask for consent to collect data to personalise ads.

=Avoidance=

The point of creating a model for the movement of a customer is to improve our options for avoiding a person. For simplicity we consider 2 specific situations, movement within an aisle. And global movement.
==within an Aisle==
Most of the time the robot will be moving through an aisle, this is practically a fairly narrow corridor. We consider the situations where the robot is moving from one end of the corridor to the other, and the situation where it does the same but has to stop at a specific location.
==globally==
We can define our route from A to B entirely in straight lines so that we can pretend we are only moving through straight corridors. In order to choose our exact route we can simply choose the shortest path however ways to improve on this are mentioned below in its own section.
==Personal space==
We should both avoid running into people as well as invading their personal space. As previously mention we define the personal space as an elliptical  area extending up to 45cm. to the front of the person while being absent behind a person.

https://smartech.gatech.edu/bitstream/handle/1853/37968/04107827.pdf?sequence=1&isAllowed=y 
==Customer behaviour model==
In order to avoid invading peoples personal spaces it will be useful to predict their movement to some extend for this we will use a model which may be adapted to depend on the data we observed from our cameras. 

===examples===
https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1470-6431.2007.00646.x
This article describes using WLAN/RFID for analysing customer behaviour in a do it yourself store. In particular it checked the popularity of different section at different times.



Dirk Helbing’s  social force model:
The social force model is widely used for predicting the behaviour of pedestrians, below is an example.
https://journals.aps.org/pre/abstract/10.1103/PhysRevE.51.4282
In this model the movement of a person is determined by a set of forces. There is a force that pulls  them towards their goal but there are also forces that push them away from walls and other pedestrians. This model can be directly applied to a robot by having it move in this exact manner.  


== Existing avoidance algorithms==
We take a look at existing algorithms used for avoiding people locally


https://ieeexplore.ieee.org/abstract/document/8172447
This article analyses human-aware navigation planners. 

Firt one mentioned is (http://personalrobotics.ri.cmu.edu/files/courses/papers/Sisbot07-humaware.pdf)
This planner associates cost with moving close to people and calculates a minimum cost path. Here we could easily apply our learned data by assigning a high cost to situations where to robot would likely run into a person. One example that is given of things that should be costly are appearing from right behind a person. It is also mention that humans prefer when robots stick to their strategy so they should not make sudden changes in direction, so this should have cost associated as well.

It also mentions planners the social force model. It concludes that navigation planners based on this work well in open spaces but do not work well in constrained situations. These planners require more room for the robot to evade so this will not work in our supermarket.


They  mention a third navigation solution ( https://dl.acm.org/citation.cfm?id=3038374 ) 
“A Human-Robot Cooperative Navigation Planner” . Here possible trajectories for the humans are considered and the robot can suggest a trajectory for the person. For example it can move to one side of a corridor with the expectation that the human will take the other side. This method has been shown to work better in confined spaces compared to the social force model.



=global navigation=
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.

=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 definitely want to avoid.

=conclusion=
In conclusion, existing algorithms will mostly satisfy the user requirements. It is however possible to improve upon these algorithms using information we gather from the security cameras. Simple anonymous data like the positions of people can direcly be applied for slight improvements in the navigation algorithm but when dealing with more personal information a lot of care has to be given to the handling of data and protection of privacy.

=references=
<references/>