PRE2018 1 Group3 1024503

Introduction

Automation through robots is becoming more and more commonplace, so it is only a matter of time until it makes its way into supermarkets by replacing tasks for, for example, store clerks. One part that is crucial for robots, is still being able to navigate from point A to B efficiently despite the store being crowded. The supermarket's security cameras can help with this, in combination with a model that keeps track of where customers might be now and in the future.

Problem Statement

The goal of this project will be to find an effective and good way of guiding a robot through a crowded supermarket.

Requirements

To determine what exactly makes a navigation method 'good', we will have a look at the users that are involved. There are three classes of users: human store clerks, customers, and the supermarket management. Each of these will have requirements that need to be taken into account when designing a navigation system:

1. Be safe: Robots should not bump into people or objects

2. Feel safe: People should feel comfortable around the robot(s)

3. Not get in the way: People should have to change their behaviour as little as possible to accommodate for the robot(s)

4. Not take too much time: Robots should not get stuck or take unreasonably long

5. Be economically viable: New equipment and maintenance should not cost more than they save and take at most a few years to pay for itself

6. Respect privacy: Keeping profiles of customers is ethically dubious and will upset them

Supermarkets

Edited from https://www.ah-ouddorp.nl/klantenservice/plattegrond/

There are a couple of things that make navigation and behaviour in a supermarket stand out. First of all, the environment itself is completely known; a map of the supermarket should not be hard to acquire. Another interesting factor is that most (if not all) supermarkets have a few security cameras installed on the ceiling. These can be used to keep track of people in some of the areas the robots can't directly see. We can then use image recognition and our knowledge of the environment to place all clearly visible customers on the map. We can add more cameras, but we also have to keep the cost (requirement 5) in mind. This means there will inevitably be blind spots. We can, however, use a model that keeps track of the probability distribution of customers in those blind spots. This can be used to improve navigation by staying away from potentially crowded spaces and avoiding collisions in a timely manner.

The behaviour of people in a supermarket is also very different from people on the street: people will often stop in front of a shelf or change direction. It would be possible to base the probabilities of a customer stopping in front of a shelf on their age, outwardly appearance or even their customer card, but this would very much be against requirement 6.

Model

To model the possibility distribution of customers in invisible areas, we will make a grid based on the map. The advantage of this is that we will now be able to assign a probability to each grid square and use that for an A* navigation algorithm.

The distribution of customers in areas without camera coverage will be modelled as a so-called cellular automaton. Each cell gets two variables: probability of it being occupied (a number between 0 and 1) and the direction a person in that cell would most likely be moving in (a vector of two numbers between -1 and 1, of at most length 1). After each time step, the cell's probability is distributed over its neighbours, most of which to those closest to the direction of movement.

In the general situation, the largest fraction will go in the direction of movement. Smaller fractions go off to the sides, and the smallest fraction stays put.

When a cell that would have been spread to is occupied, the spread to the rest of the cells is scaled so it still sums up to the original chance.

When a cell's direction is (0,0), the chance for spreading to any neighbouring cell is equal, but the chance to stay stationary is the highest.

When two cells spread to the same cell, the chance is added and the cell's direction is calculated as the weighted component-wise mean of the directions each cell would give it, scaled by the chance that comes from each of the cells.

Navigation Algorithm

Using this model, we can both estimate how busy the unseen areas of the store are and as a bonus it can also be used to try to predict what the customer distribution will be after a number of time steps. The one key difference between these to uses is that for estimating the current distribution we can let cells we know to be visible function as walls, as we know exactly if a customer moved towards it or if it is empty. When we attempt to make a prediction we cannot use this. To make a navigation algorithm that uses this knowledge, we can modify the basic A* algorithm to add a cost to each grid cell dependent on the probability of it being occupied when the robot reaches it. We will use 1 plus some constant times the cell's probability after running a model step for each preceding cell in the path. The optimal value of this constant very much depends on the situation and as such stays a parameter. Since the minimal cost per grid cell is one and we only let the robot move to cells that are directly adjacent, the Manhattan distance makes for a good heuristic.

Simulation

Since getting enough actual data of the movement of customers in supermarkets is somewhere between difficult and impossible, customer walking behaviour will be simulated instead. Customers enter the simulation through one of the entrance gates with geometrically distributed inter-arrival times. This makes it a Bernoulli process, which is often used to describe similar situations. They will then proceed to pick up a (Poisson distributed) random amount of products. Finally, they will exit at one of the checkout areas. Requirement 3 states that customers should be able to ignore the robot and always assume right of way, so in the simulation they will completely ignore the robot. Any collision that occurs because of that will be blamed on the robot breaking said requirement.

Based on the ceiling cameras and the robot's own position and orientation, certain areas will be declared visible. Only while a customer is in such a visible area will its position and walking direction will be reported to the model; outside these areas it will only know the position of the objects on the given map, such as walls and shelves.

Results

Amount of collisions (robot's camera only, without model, with model)

Time taken (robot's camera only, without model, with model)

To get an idea of the effectiveness of the ideas presented before this, we will want to compare the performance of the robot using only its own camera, using all available cameras, and the robot using the complete model. To compare these well, we need to choose a metric to compare them by. For this, we can bring back the user requirements once again. 1 (safety) and 4 (time) can easily be quantified, so these will be compared directly. Since no cameras are added, the cost (5) is the same (although the computations to be done get slightly heavier). The privacy of customers (6) is respected equally by all three methods, as all that is done is extracting the position and velocity of people from already existing camera images.

After running the same 100 tests of the robot moving to 50 positions on the three methods, these are the results:

Method	Mean Collisions	Median Collisions	Mean Time	Median Time
Robot's camera only	11.7	10	967	991
Without model	10.9	9	922	924
With model	10.6	8	915	912

From this can be concluded that both using the security cameras and using the model help fulfil the requirements.

A ZIP file with the results of all tests can be found here

Conclusion

As seen in the results, the security cameras at supermarkets can definitely help robots navigate when it is crowded. Furthermore, combining this with a with a model based on cellular automata can make this even more effective.

The used simulation can be found here and was compiled from these source files.

Discussion

Something that might still be interesting to look into is the optimal placement of security cameras. It can be expected that having many small or simple blind spots will make it easier to predict where customers are, as we know exactly which blind spot they entered. It would thereby make sense that the model-based navigation will be even better if the security cameras were placed to cover entire intersections.

Using a fine grid for the model and/or switching to a finer or continuous time scale will allow the model to be more realistic by e.g. allowing for different walking speeds and making it possible to make a better judgement of the comfort of customers.

Planning

Week	Milestones
5	Pin down exactly what to work on and towards Write up a new planning Make wiki skeleton Formulate new user (and technical) requirements
6	Research and add realistic camera coverage Look into realistic customer behaviour Add in A*-based navigation that makes use of the movement predictions and customer distribution
7	Finish simulation Experiment with different parameters Finish up final presentation
8	Do final presentation Finalise wiki

---

Work In Progress below this line

Most Important Design Problems

From the literature study, we can conclude that there are four design problems that are the most important. Since our time is limited, we will only be able to focus on one of these.

First of all, there is shelf restocking according to the first in first out (FIFO) principle. Humans are far better at grabbing a variety of objects, while robots can do this but very slow and inefficiently. Also, the task of placing the newest products in the back of shelves as by FIFO is physically hard for a robot to do. Robots like AMIGO already have a lot of problems with the basic issue of grabbing arbitrary objects , so contributing to the state of the art will be difficult.

Another important design problem is helping and interacting with customers; providing information about product location or stock availability. Difficulties lie in human-robot interaction, the design of an appropriate GUI and means of communication. This is an interesting problem, but there is not much that sets this problem apart from other situations outside of supermarkets.

There is also the possible task of shelf analysis to provide shops with retail statistics. This might not be too interesting to research, since robots like Tally (which was previously discussed) already exist that perform this task quite efficiently.

Last of all there is the problem of robot navigation in a crowded supermarket environment. There are already options available for robot navigation in crowded environments. However, robot navigation specifically designed for supermarket environments, taking into account possible (robot) store clerk tasks does not exist. Therefore, this research will focus on giving a design solution for this specific problem.