PRE2018 1 Group3 1024503: Difference between revisions

From Control Systems Technology Group
Jump to navigation Jump to search
No edit summary
 
(34 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Introduction=
=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=
=Requirements=
The robot has 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:
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. <u>Be safe</u>: Robots should not bump into people or objects
1. <u>Be safe</u>: Robots should not bump into people or objects
Line 21: Line 25:
There are a couple of things that make navigation and behaviour in a supermarket stand out.
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.
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<ref>http://pedestrian.msstate.edu/docs/IERC%202008%20Lee.pdf</ref>. Combined with a model that keeps track of the probability distribution of customers in the areas that cannot be seen, this can be used to improve navigation by staying away from potentially crowded spaces and avoiding collisions in a timely manner.
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<ref>http://pedestrian.msstate.edu/docs/IERC%202008%20Lee.pdf</ref>. 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.
 
[[File:1024503-CA_transition1.png‎]] 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.
 
[[File:1024503-CA_transition4.png]] 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.
 
[[File:1024503-CA_transition2.png‎]] 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.
 
[[File:1024503-CA_transition3.png‎]] 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.
 


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 5.
==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=
=Simulation=
To be able to easily test and compare algorithms and their parameters, a simulation will come in handy.  
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.
 
 
==Optimising Parameters==
Now that the simulation gives us a concrete situation, we can figure out the accompanying optimal value for the parameter that determines how heavily the probability of a cell being occupied is taken into account. For this, we will run a couple of tests with many different parameter values and compare the results. Each test will consist of the robot having to move to 50 different positions, while reporting the amount of times it landed in an occupied cell and the amount of time steps the total procedure took.
 
First, a test with the constant ranging from 0 to 200 is done. Here, it appears that low values for the collisions and time are more often taken in the interval from 0 to 50. 
Using this, we run four tests on all constants between 0 and 50. From these we conclude that values between 18 and 30 give the best outcomes. 
Finally, we run ten tests on all constants between 18 and 30. The conclusion we draw from this is that 28 is the best value for the weight parameter in this situation.
 
[[Media:1024503-parameter_tests.zip | The test results are given here.]]
 
=Results=
[[File:1024503-BoxplotC.png|512 px|thumb|Amount of collisions (robot's camera only, without model, with model)]]
[[File:1024503-BoxplotT.png|512 px|thumb|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:
{| class="wikitable"
|-
! 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.


[[Media:StoreSim.zip]]
[[Media:1024503-tests.zip | A ZIP file with the results of all tests can be found here]]


=Conclusion=
=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 [[Media:StoreSim.zip | found here]] and was compiled from [[Media:1024503-source.zip | these source files]].
=Discussion=
=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<ref>https://arxiv.org/ftp/arxiv/papers/1406/1406.3567.pdf</ref> 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=
=Planning=
Line 68: Line 145:
|}
|}


----
''Work In Progress below this line''
=State of the Art=
The use of robots in a retail environment like stores and supermarkets has been a frequent subject for research. This research can be subdivided into a variety of smaller fields:
==Navigation of robots in indoor environments with people and/or other robots==
Navigation of the robot in a shopping environment is an essential function it should have. Several approaches to navigation were found:
Articles here describe the use of models that describe buildings in stores, rooms, a set of places in each room and connectors among these. There is made use of so-called ‘highways’ for pre-determined robot paths and ‘off-roads’ where the robot plans its own path <ref>Gert L. Andersen, Anders C. Christensen, Ole Ravn, Mobile Robot Navigation In Indoor Environments Using Highways And Off-roads, Institute for Automation. bldg. 326, Technical University of Denmark</ref>. A different approach is the use of a sensor space as elaborated on in <ref>Narongdech Keeratipranon, Robot Navigation in Sensor Space, Faculty of Information Technology Queensland University of Technology</ref>.
Other articles describe a modelling approach that predicts the surrounding pedestrian’s actions so that the robot can develop its own path. One promising example is an agent-based modelling approach where surrounding pedestrians are assigned the behaviours interact, watch, curious, ignore, cautious and avoid <ref>Usher, J. M., McCool, R., Strawderman, L., Carruth, D. W., Bethel, C. L., & May, D. C. (2017). Simulation modeling of pedestrian behavior in the presence of unmanned mobile robots. Simul. Modell. Pract. Theory, 75, 96–112. doi: 10.1016/j.simpat.2017.03.012</ref>.
==Design of appropriate actuators==
The robot should be able to move around various objects, these could be heavy or fragile. Article <ref>Lauzier, N. (2018, September 04). Robot Gripper Force Control. Retrieved from https://blog.robotiq.com/bid/53319/Robot-Gripper-Force-Control</ref> describes the use of a force control parameter for robot grippers, so that fragile objects will not be damage by actuators. Article <ref>Michael Zinn, Bernard Roth, Oussama Khatib J. Kenneth Salisbury. A New Actuation  Mastrogiovanni, F., & Casalino, G. (2018). Flexible human-robot cooperation models for assisted shop-floor tasks.Approach for Human Friendly Robot Design. Department of Mechanical Engineering
Stanford University</ref> emphasises the challenge of designing safe actuators for human-centred robotics. The articles states that by reducing the effective impedance while maintain high frequency torque capability in actuators, safety and performance requirements can be achieved.
==Design of appropriate sensors==
Various sensors are needed, especially for localisation and navigation purposes but also for object recognition. According to <ref>Payá, L., Gil, A., & Reinoso, O. (2017). A state-of-the-art review on mapping and localization of mobile robots using omnidirectional vision sensors. Journal of Sensors, 2017. DOI: 10.1155/2017/3497650
</ref> the advances in computer vision have led to an increase in the use of cameras as sensors. They are often combined with other sensors such as odometry or lasers. Omnidirectional sensors stand out in the richness of information they provide. These sensors, together with robust models of the environment are important for designing an autonomous mobile robot.
==Object recognition (in a shop context)==
(Camera) sensors could be used for object recognition, which is an essential task for this robot application. The robot should be able to distinguish a large variety of shopping goods and should be able to detect if the product is misaligned or missing in the shelves. Article <ref>Makihara, Y., Takizawa, M., Shirai, Y., Makihara, Y., Takizawa, M., Shirai, Y., ...Shimada, N. (2002). Object recognition supported by user interaction for service robots. Object recognition supported by user interaction for service robots, 3, 561–564vol.3. doi: 10.1109/ICPR.2002.1048001</ref> describes a vision system where the user can specify an object the robot has to find and bring. When the recognition result is shown, the user can provide additional information, such as point out mistakes. Article <ref>Kejriwal, N., Garg, S., Kumar, S., Kejriwal, N., Garg, S., & Kumar, S. (2015). Product counting using images with application to robot-based retail stock assessment. 2015 IEEE International Conference on Technologies for Practical Robot Applications (TePRA), 1–6. doi: 10.1109/TePRA.2015.7219676</ref> proposes a novel method for obtaining product count directly from an image using a monocular camera. Article <ref>Agnihotram, G., Vepakomma, N., Trivedi, S., Agnihotram, G., Vepakomma, N., Trivedi, S., ...Kumar, R. (2017). Combination of Advanced Robotics and Computer Vision for Shelf Analytics in a Retail Store. 2017 International Conference on Information Technology (ICIT), 119–124. doi: 10.1109/ICIT.2017.13</ref> describes a patrolling robot that detects misaligned and out of stock products and provides the store associates with alert messages.
==The social or legislation issues that arise when robots enter the workspace==
Robots working alongside humans could pose safety issues as well as open up question on how robots should interact (verbally) with humans. Another problem is that the use of robots could make humans redundant in this field of the job market.
Article <ref>Romeo, J. How Will Robot Store Clerks Disrupt Retail? - Robotics Business Review. (2016, July 26). Retrieved from https://www.roboticsbusinessreview.com/supply-chain/how-will-robot-store-clerks-disrupt-retail</ref> says that retail automation is essential in competitiveness, but could lead to the minimum-wage employees being redundant as the robots are far cheaper. Robot store clerks are likely to be a disruptive force for the retail industry, this article states.
Article <ref>Gonzalez-Jimenez, H. (2018). Taking the fiction out of science fiction: (Self-aware) robots and what they mean for society, retailers and marketers. Futures, 98, 49–56. doi: 10.1016/j.futures.2018.01.004</ref> emphasises more on self-aware robots that become a part of society (including the retail sector) where brands are used as self-expression. Article <ref>Darvish, K., Wanderlingh, F., Bruno, B., Simetti, E., Mastrogiovanni, F., & Casalino, G. (2018). Flexible human–robot cooperation models for assisted shop-floor tasks. Mechatronics, 51, 97–114. doi: 10.1016/j.mechatronics.2018.03.006</ref> describes a means for robots to detect human action to make the cooperation between humans and robots in the workspace more attractive.
==Human-robot interactions during shopping activities==
A robot store clerk should also be able to interact with humans. Humans might want information about a product or want to know where it is located. Article <ref>Bertacchini, F., Bilotta, E., & Pantano, P. (2017). Shopping with a robotic companion. Computers in Human Behavior, 77, 382–395. doi: 10.1016/j.chb.2017.02.064</ref> proposes a robotic shopping companion to help customers in their shopping activities. Furthermore, the robot collects the emotional state of people through social interactions and then use that to influence people’s buying decisions. Article <ref>Lee, S. A., & Liang, Y. (. (2018). Robotic foot-in-the-door: Using sequential-request persuasive strategies in human-robot interaction. Computers in Human Behavior. doi: 10.1016/j.chb.2018.08.026</ref> goes further with investigating ways in which robots can persuade people. This could be applied to the robot store clerk in persuading people to buy a certain product.
Article <ref>Gallé, M., Kynev, E., Monet, N., Gallé, M., Kynev, E., Monet, N., & Legras, C. (2017). Context-aware selection of multi-modal conversational fillers in human-robot dialogues. 2017 26th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN), 317–322. doi: 10.1109/ROMAN.2017.8172320</ref> describes ways in which verbal output of a robot can be made more human-like by introducing context-aware conversational fillers.
==A combination of above fields, applied to a designed robot==
These articles describe a fully working system of a robot working in a retail environment. Especially article <ref>Kumar, S., Sharma, G., Kejriwal, N., Kumar, S., Sharma, G., Kejriwal, N., ...Chauhan, V. K. (2014). Remote retail monitoring and stock assessment using mobile robots. 2014 IEEE International Conference on Technologies for Practical Robot Applications (TePRA), 1–6. doi: 10.1109/TePRA.2014.6869136
</ref> is a great example, where a system is built that automates data collection for surveying and monitoring the shelves. The robot here can monitor shelves autonomously or through tele-operation. It can automatically detect out of stock situations. According to this article it will improve customer satisfaction, as shelve products are filled more frequently. The deployment also would not require modifying the existing store infrastructure and has a short return-on-investment period.
'''Navigation'''
[3] Guizzo, E. Ackerman. E. (2015). iRobot Brings Visual Mapping and Navigation to the Roomba 980. IEEE Spectrum: Technology, Engineering, and Science News. Retrieved from https://spectrum.ieee.org/automaton/robotics/home-robots/irobot-brings-visual-mapping-and-navigation-to-the-roomba-980
'''USE'''
[6] Heinzmann, J., & Zelinsky, A. (2000). Building Human-Friendly Robot Systems. SpringerLink, 305–312. doi: 10.1007/978-1-4471-0765-1_37
[7] Wisskirchen, G., Biacabe, B T. et al. Artificial Intelligence and Robotics and Their Impact on the Workplace, April 2017, IBA Global Employment Institute
'''Sensors'''
[10] Mantha, B. R. K., Menassa, C. C., & Kamat, V. R. (2018). Robotic data collection and simulation for evaluation of building retrofit performance. Autom. Constr., 92, 88–102. doi: 10.1016/j.autcon.2018.03.026
[15] Rajithkumar, B. K., Deepak, G. M., Uma, B. V., Hadimani, B. N., Darshan, A. R., & Kamble, C. R. (2018). Design and Development of Weight Sensors Based Smart Shopping Cart and Rack System for Shopping Malls. Mater. Today:. Proc., 5(4, Part 3), 10814–10820. doi: 10.1016/j.matpr.2017.12.367
'''Store clerk robot implementation (technical)'''
[16] Tomizawa, T., & Ohya, A. (2006, October). Remote shopping robot system,-development of a hand mechanism for grasping fresh foods in a supermarket. In Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on (pp. 4953-4958). IEEE. DOI: 10.1177/1729881417703569
[18] Cheng, C. H., Chen, C. Y., Liang, J. J., Tsai, T. N., Liu, C. Y., & Li, T. H. S. (2017, September). Design and implementation of prototype service robot for shopping in a supermarket. In Advanced Robotics and Intelligent Systems (ARIS), 2017 International Conference on (pp. 46-51). IEEE. DOI: 10.1109/ARIS.2017.8297181
[23] Lin, T., Baron, M., Hallier, B., Lin, T., Baron, M., Hallier, B., ...Dugan, J. (2016). Design of a low-cost, open-source, humanoid robot companion for large retail spaces. 2016 IEEE Systems and Information Engineering Design Symposium (SIEDS), 66–71. doi: 10.1109/SIEDS.2016.7489329
[24] Kamei, K., Ikeda, T., Kidokoro, H., Kamei, K., Ikeda, T., Kidokoro, H., ...Hagita, N. (2011). Effectiveness of Cooperative Customer Navigation from Robots around a Retail Shop. 2011 IEEE Third International Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third International Conference on Social Computing, 235–241. doi: 10.1109/PASSAT/SocialCom.2011.173
=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<ref>http://roboticopenplatform.org/wiki/AMIGO</ref> 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.


=References=
=References=
<references/>
<references/>

Latest revision as of 23:54, 29 October 2018

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

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[1]. 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.

1024503-CA transition1.png 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.

1024503-CA transition4.png 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.

1024503-CA transition2.png 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.

1024503-CA transition3.png 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.


Optimising Parameters

Now that the simulation gives us a concrete situation, we can figure out the accompanying optimal value for the parameter that determines how heavily the probability of a cell being occupied is taken into account. For this, we will run a couple of tests with many different parameter values and compare the results. Each test will consist of the robot having to move to 50 different positions, while reporting the amount of times it landed in an occupied cell and the amount of time steps the total procedure took.

First, a test with the constant ranging from 0 to 200 is done. Here, it appears that low values for the collisions and time are more often taken in the interval from 0 to 50. Using this, we run four tests on all constants between 0 and 50. From these we conclude that values between 18 and 30 give the best outcomes. Finally, we run ten tests on all constants between 18 and 30. The conclusion we draw from this is that 28 is the best value for the weight parameter in this situation.

The test results are given here.

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[2] 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[3] [4] [5] [6]
  • 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


References