PRE2018 1 Group3 1024503
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.
The goal of this project will be to find an effective and good way of guiding a robot through a crowded supermarket.
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
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.
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.
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.
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. 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. Left is to figure out what exactly as the constant. (28)
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.
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|
From this can be concluded that both using the security cameras and using the model help fulfil the requirements.
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.
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.
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 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 . A different approach is the use of a sensor space as elaborated on in . 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 .
Design of appropriate actuators
The robot should be able to move around various objects, these could be heavy or fragile. Article  describes the use of a force control parameter for robot grippers, so that fragile objects will not be damage by actuators. Article  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  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  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  proposes a novel method for obtaining product count directly from an image using a monocular camera. Article  describes a patrolling robot that detects misaligned and out of stock products and provides the store associates with alert messages.
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  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  emphasises more on self-aware robots that become a part of society (including the retail sector) where brands are used as self-expression. Article  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  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  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  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  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.
 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
 Heinzmann, J., & Zelinsky, A. (2000). Building Human-Friendly Robot Systems. SpringerLink, 305–312. doi: 10.1007/978-1-4471-0765-1_37
 Wisskirchen, G., Biacabe, B T. et al. Artificial Intelligence and Robotics and Their Impact on the Workplace, April 2017, IBA Global Employment Institute
 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
 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)
 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
 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
 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
 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 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.
- 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
- Narongdech Keeratipranon, Robot Navigation in Sensor Space, Faculty of Information Technology Queensland University of Technology
- 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
- Lauzier, N. (2018, September 04). Robot Gripper Force Control. Retrieved from https://blog.robotiq.com/bid/53319/Robot-Gripper-Force-Control
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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