PRE2018 1 Group3 1024503

From Control Systems Technology Group
Jump to navigation Jump to search


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 and will be.

Problem Statement


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:

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


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. 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.


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.



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 make the model more realistic by e.g. allowing for different walking speeds and making it possible to make a better judgement of the comfort of customers.


Week Milestones
  • Pin down exactly what to work on and towards
  • Write up a new planning
  • Make wiki skeleton
  • Formulate new user (and technical) requirements
  • 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
  • Finish simulation
  • Experiment with different parameters
  • Finish up final presentation
  • Do final presentation
  • Finalise wiki

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 [7]. A different approach is the use of a sensor space as elaborated on in [8]. 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 [9].

Design of appropriate actuators

The robot should be able to move around various objects, these could be heavy or fragile. Article [10] describes the use of a force control parameter for robot grippers, so that fragile objects will not be damage by actuators. Article [11] 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 [12] 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 [13] 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 [14] proposes a novel method for obtaining product count directly from an image using a monocular camera. Article [15] 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 [16] 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 [17] emphasises more on self-aware robots that become a part of society (including the retail sector) where brands are used as self-expression. Article [18] 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 [19] 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 [20] 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 [21] 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 [22] 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.


[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


[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


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


  7. 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
  8. Narongdech Keeratipranon, Robot Navigation in Sensor Space, Faculty of Information Technology Queensland University of Technology
  9. 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
  10. Lauzier, N. (2018, September 04). Robot Gripper Force Control. Retrieved from
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. Romeo, J. How Will Robot Store Clerks Disrupt Retail? - Robotics Business Review. (2016, July 26). Retrieved from
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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