Estudio y evaluación de plataformas de distribución de cómputo intensivo sobre sistemas externos para sistemas empotrados.
Abstract
Nowadays, the capabilities of current embedded systems are constantly increasing, having a wide range of applications. However, there are a plethora of intensive computing tasks that, because of their hardware limitations, are unable to perform successfully. Moreover, there are innumerable tasks with strict deadlines to meet (e.g. Real Time Systems). Because of that, the use of external platforms with sufficient computing power is becoming widespread, especially thanks to the advent of Cloud Computing in recent years. Its use for knowledge sharing and information storage has been demonstrated innumerable times in the literature. However, its core properties, such as dynamic scalability, energy efficiency, infinite resources... amongst others, also make it the perfect candidate for computation off-loading. In this sense, this thesis demonstrates this fact in applying Cloud Computing in the area of Robotics (Cloud Robotics). This is done by building a 3D Point Cloud Extraction Platform, where robots can offload the complex stereo vision task of obtaining a 3D Point Cloud (3DPC) from Stereo Frames. In addition to this, the platform was applied to a typical robotics application: a Navigation Assistant. Using this case, the core challenges of computation offloading were thoroughly analyzed: the role of communication technologies (with special focus on 802.11ac), the role of offloading models, how to overcome the problem of communication delays by using predictive time corrections, until what extent offloading is a better choice compared to processing on board... etc. Furthermore, real navigation tests were performed, showing that better navigation results are obtained when using computation offloading. This experience was a starting point for the final research of this thesis: an extension of Amdahl’s Law for Cloud Computing. This will provide a better understanding of Computation Offloading’s inherent factors, especially focused on time and energy speedups. In addition to this, it helps to make some predictions regarding the future of Cloud Computing and computation offloading.
Full text
UNIVERSIDAD DE SEVILLA DOCTORAL THESIS Estudio y evaluación de plataformas de distribución de cómputo intensivo sobre sistemas externos para sistemas empotrados. Study and evaluation of intensive distributed computing platforms on external systems for embedded systems Author: Javier J. Salmerón García Supervisor: Dr. Fernando Díaz del Río A thesis submitted in fulfilment of the requirements for the degree of Doctor of Philosophy in the Robotics and Technology of Computers Lab Departamento de Arquitectura y Tecnología de Computadores December 2, 2015
Declaration of Authorship I, Javier J. Salmerón García, declare that this thesis titled, ’Study and evaluation of intensive distributed computing platforms on external systems for embedded systems’ and the work presented in it are my own. I confirm that: •This work was done wholly or mainly while in candidature for a research degree at this University. •Where any part of this thesis has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated. •Where I have consulted the published work of others, this is always clearly attributed. •Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this thesis is entirely my own work. •I have acknowledged all main sources of help. •Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself. Signed: Date: iii
UNIVERSIDAD DE SEVILLA Abstract Escuela Técnica Superior de Ingeniería Informática Departamento de Arquitectura y Tecnología de Computadores Doctor of Philosophy Study and evaluation of intensive distributed computing platforms on external systems for embedded systems by Javier J. Salmerón García Nowadays, the capabilities of current embedded systems are constantly increasing, having a wide range of applications. However, there are a plethora of intensive computing tasks that, because of their hardware limitations, are unable to perform successfully. Moreover, there are innumerable tasks with strict deadlines to meet (e.g. Real Time Systems). Because of that, the use of external platforms with sufficient computing power is becoming widespread, especially thanks to the advent of Cloud Computing in recent years. Its use for knowledge sharing and information storage has been demonstrated innumerable times in the literature. However, its core properties, such as dynamic scalability, energy efficiency, infinite resources... amongst others, also make it the perfect candidate for computation off-loading. In this sense, this thesis demonstrates this fact in applying Cloud Computing in the area of Robotics (Cloud Robotics). This is done by building a 3D Point Cloud Extraction Platform, where robots can offload the complex stereo vision task of obtaining a 3D Point Cloud (3DPC) from Stereo Frames. In addition to this, the platform was applied to a typical robotics application: a Navigation Assistant. Using this case, the core challenges of computation offloading were thoroughly analyzed: the role of communication technologies (with special focus on 802.11ac), the role of offloading models, how to overcome the problem of communication delays by using predictive time corrections, until what extent offloading is a better choice compared to processing on board... etc. Furthermore, real navigation tests were performed, showing that better navigation results are obtained when using computation offloading. This experience was a starting point for the final research of this thesis: an extension of Amdahl’s Law for Cloud Computing. This will provide a better understanding of Computation Offloading’s inherent factors, especially focused on time and energy speedups. In addition to this, it helps to make some predictions regarding the future of Cloud Computing and computation offloading. v
Acknowledgements The project described in this document has been, without room for doubt, one of the biggest challenges in my life. I consider it my first real research, job that I find fascinating and to which I would love to focus my professional career (together with teaching, another passion that I have). After overcoming all the difficulties, I have been able to finish it in the given time. I can honestly say that, if it had not been for all the given support, I would definetly not have succeeded in this task. Hence I would like to dedicate some words to all the people that helped me to make this thesis possible. To begin with, I really want to express my deepest gratitude to my supervisor Fernando Díaz del Río. Not only for all the help and support throughout the whole project, but also for having the patience of attending me every time a problem arose, knocking at his office door without any previous appointment. He trusted helped me so much that I simply cannot imagine a better supervisor. In that sense, I couldn’t have been luckier. In addition to this, I really want to help the assistance and knowledge of Jose Luis Sevillano, Daniel Cagigas and Pablo Iñigo. I really think that, if this thesis was possible, is thanks to being in a research group that is like a second family. My gratitude goes to Elena Cerezuela, Manuel Domínguez, Rocío García, Miguel Ángel Rodríguez, Alejandro Linares, Gabriel Jiménez, Anton Civit, José Luis Guisado, Manuel Rivas, Ángel Jiménez, Francisco Gómez, Lourdes Miró, Saturnino Vicente, Ignacio García, Antonio Ríos, Juan Pedro Domínguez, Ricardo Tapiador and the rest of colleagues of the Robotics and Technology of Computers Lab. I cannot forget all the great moments and support during all these years, especially in our "debate" meals, research trips, classes, and innumerable experiencies. A special mention goes to Daniel Cascado for all his interesting comments, which were really helpful for my thesis. Moreover, this work has been supported by the Spanish grant (with support from the European Regional Development Fund) BIOSENSE (TEC2012-37868-C04-02/01) and by Andalusian Regional Excellence Research Project grant (with support from the European Regional Development Fund) MINERVA (P12-TIC-1300). I also want to thank the University of Seville for my IV Plan Propio grant, which helped me to have full dedication in this thesis. My deepest gratitude for this support. During this period, I also had the opportunity visit foreign institutions and attend international conferences. There I had the chance to meet extraordinary researchers that did help to become the researcher I am today. Among these people, I will never forget Helen Karatza (Aristotle University of Thessaloniki), Rene van de Molengraft and Sjoerd van den Dries (TU/e Eindhoven). Moreover, I am extremely lucky to have my wonderful parents, Mariano and Lourdes, and my greatest friends Daniel, Yesu, Gonzalo, Israel, Alejandro, Luis, Rafael, Jesús, Ángel, Iria, Goretti, Alberto, Antonio, Javier... amongst other extraordinary people. Moreover, I want to thank my family for all their support and love. One of the biggest gratitudes goes to my beloved Elena Rodriguez, with whom I have been living seven years of love, happiness, support and passion, becoming the reason why I feel every day a little more alive and full. For what it has been, and for all that it will be, thank you very much. Obviously, I cannot forget our dear Ini, our first member of our future family together. To all of them, once again, thank you. vii
Contents Declaration of Authorship iii Abstract v Acknowledgements vii I Thesis 1 1 Introduction 3 2 General Objectives 7 3 Summary of results 9 4 Discussion 21 5 Conclusions 29 6 Bibliography 31 II Set of papers 37 A Mobile robot motion planning based on Cloud Computing stereo vision processing 39 B Study of Communication Issues in Dynamically Scalable Cloud-Based Vision Systems for Mobile Robots 47 C A Tradeoff Analysis of a Cloud-Based Robot Navigation Assistant Using Stereo Image Processing 73 D Extending Amdahl’s Law For the Cloud Computing Era 87 ix
4Chapter 1. Introduction FIGURE 1.1: Concept of computation offloading •On-demand virtual resource provision: The cloud is able to provide both computing and storage resources. This is normally done in the form of virtual machines. Should an user require computing power to perform a certain task, then it would only have to spin up as much virtual instances as required to complete it. Most commercial cloud platforms (for example, Amazon EC2, Windows Azure, Google App Engine, etc.) use a pay-as-you-go approach. However, undoubtedly this will be much cheaper than all the capital expenditure required for a cluster, not to mention all the maintenance costs. •Dynamic scalability: This property relates to the ability of the Cloud to dinamically adapt to the user needs. A clear example is that of a web service. If, suddenly, the number of requests dramatically increase, the service might not be able to process them in a reasonable time. In order to address this, the Cloud could increase the number of virtual resources devoted to this task. Moreover, if the number of requests decreases, then the cloud could reduce the amount of virtual resources. Once again, this relates to the "utility" concept behind Cloud Computing. However, this forces the developer to rethink their software architectures so the dynamically scalable property can be exploited. Therefore, a third solution to overcome the aforementioned issues for embedded systems would be the following: •Move the computation to the Cloud: The system would send the information to this external platform. The information would be processed and the results would be sent back. This way, the only computation upgrade the embedded system would need is a proper network connection (see figure 1.1). In this thesis, in order to show the viability of this third choice, Cloud Computing is applied to robotic tasks. The research area is known as as Cloud Robotics (first coined by James Kuffner in 2010) [2]. This term refers to the use the both storage and computing power of the cloud for the successful accomplishment of robotic tasks. In this sense, there are several items of interest in this area[3]: The first one is that of Computation Offloading. The idea is to free the robot from heavy computations and have an external platform (the Cloud in this case) do them and get the results back. This would solve the two aforementioned issues, as it allows the robots to perform more complex tasks, overcoming its hardware limitations
Chapter 1. Introduction 5 FIGURE 1.2: Diagram of the 3DPC Extraction Platform (which is difficult to upgrade). Furthermore, offloading CPU-intensive tasks implies less power consumption in the robot. Following this idea, it will possible for engineers to build cheaper (extremely powerful hardware would not be required) and more energy-efficient robots. However, this does not come without inherent trade-offs and bottlenecks, namely the communication technology and software related issues. A second item is that of Information Storage and Sharing. As stated before, the cloud offers storage resources, hence it is possible for the robots to store and retrieve data like maps, object information, pictures, amongst others. Furthermore, the use of a centralized platform like the Cloud allows the robots to build a common source of knowledge, and just like before, extending its capabilities. For instance, if a robot does not know how to handle a certain object, then it can query the Cloud for information. This concept has been defined as "an Internet for robots"[4]. For this thesis, the use of Computation Offloading in near real time scenarios has been analyzed. More precisely, the focus was on the offloading of stereo-vision tasks to the Cloud. In this sense, a dynamically scalable cloud-based 3D Point Cloud Extraction Platform was initially developed [5] . Afterwards, this platform was used for navigation assistance of mobile robots[6] (see figure 1.2). The experiments showed that, when higher resolutions were required, the limitations of the robot’s embedded hardware started to arise. Therefore, the robot was able to navigate better using the cloud. Furthermore, the study of this case showed the trade-off between computation offloading and communication, and that choosing which tasks should be offloaded to the Cloud is far from trivial. These experiments showed the viability of computation offloading in a near to real time scenario. Moreover, several aspects and challanges of computation offloading were thoroughly analyzed: offloading models, communication bottlenecks, communication delays... etc. However, it was necessary to take a step further, and make a deeper analysis of the concept of computation offloading. Therefore, fruit of this research, an extension of the Amdahl’s Law for Cloud Computing was devised, providing a theoretical analysis for computation offloading in terms of performance and energy efficiency[7]. This helps to set a reference theoretical framework when dealing with computation offloading and Cloud Computing. It helps to get an idea whether an application should or shouldn’t be offloaded. Moreover, it is an extremely useful tool for researchers to study future trends in computation offloading and hardware development. This thesis is made of a series of papers [5]–[7], which are included in part II. In part I, there is a summary structured as follows: in chapter 2the general objectives
6Chapter 1. Introduction of this thesis are described. In chapter 3all the results obtained from this research are explained and analyzed. From these results, in chapter 4we dive into their implications and future challenges. Finally, we outline the conclusions from this research in chapter 5.
Chapter 2 General Objectives As stated in chapter 1, this thesis’ main objective is to study the viability of Cloud Offloading for embedded systems. In order to obtain an answer, it is necessary to analyze various elements. These can be organized in the following categories: Use Case Analysis [UCA] In order to empirically prove that computation offloading in embedded systems is a feasible option, a real use case must be analyzed. In this sense, as stated in chapter 1, Robotics can be an extremely useful application scenario. In addition to this, cases involving extremely heavy computations and near to real time constraints could best showcase the Cloud’s potential. Not to mention the innumerable research challenges that a case like this inherently brings. For all those reasons, the chosen case for this thesis is that of Navigation Assistance based on Stereo Vision. Therefore, the objectives in this category would be: (UCA-1): Build a Cloud Based Stereo Vision platform where robots can offload stereo information processing. (UCA-2): Build a Cloud-based Navigation Assistant that uses the stereo information to avoid obstacles. (UCA-3): Perform tests on the whole system using simulated data, finding its potential benefits and pitfalls. (UCA-4): Perform real navigation tests, comparing two cases: using computation offloading and performing all the computation on-board. Study of Cloud Properties [SCP] As mentioned in chapter 1, the cloud has unique properties that imply a big leap over other technologies such as cluster or grid computing. Because of that, this work must make use of all those properties when providing a Cloud offloading solution for embedded systems. Therefore, this category contains the following objectives: (SCP-1): Analyze the performance impact of different virtual machine types. (SCP-2): Study the existing trade-off when choosing different offloading models and configurations. (SCP-3): Exploit Cloud’s dynamic scalability property when building a solution and study its performance impact when using more and less resources (scaling out and back). 7
8Chapter 2. General Objectives Compare Communication Technologies [CCT] When it comes to offloading, especially when dealing with time constraints, there is unavoidable question that must be addressed: How can we overcome network latencies? Indeed, there is a risk that, even though there are computation speedups, the information does not arrive in time because of delays in the communication technologies. Therefore, in this thesis a thorough research on this area must be done in order to mitigate its effects: (CCT-1): Compare the performance impact when using different kind of technologies. (CCT-2): Perform deeper testing on wireless technologies, vital for mobile robots. Study the current state of 802.11ac technology, as is the newest and most promising. (CCT-3): Propose a way to mitigate the effects of a delay in the information. Devise a Theoretical Framework [DTF] While performing empirical demonstrations is essential for answering this thesis’ main question, not less valuable is providing a small theoretical framework for researchers and developers. This would be extremely useful for future application development, as well as new research areas. Hence, the objectives would be the following: (DTF-1): Provide a general design pattern for offloading robotic applications. (DTF-2): Provide basic theoretical formulae that helps deciding whether an application is worth offloading or not. (DTF-3): Make predictions on the future possibilities of computation offloading.
Chapter 3 Summary of results In this chapter all the obtained research results will be briefly described. These results will make reference to the objectives described in chapter 2. These global results can be divided into two categories: Stereo Vision Offloading applied to navigation assistance In this thesis, an application case is used to study the properties, issues and challenges of Cloud Offloading.In other words, an empirical demonstration of the effectiveness of Cloud offloading is sought. Due to the high computational requirements and their importance in robotics, a case in stereo vision is proposed: several vision tasks use as main input a 3D Point Cloud (3DPC), which can be obtained from several input sources (stereo cameras, laser rangefinders, RGB-D cameras...). Extracting a 3DPC from stereo frame pairs (see figure 3.1) is computationally expensive. In addition to this, if more quality of the environment representation is desired, then higher resolution in the stereo camera is required. As a result, legacy embedded systems may be unable to obtain 3DPCs from stereo frames in a reasonable time. Therefore, developers would have no option but to purchase expensive, cutting-edge embedded systems, and still there would be no warranty that they would be able to process, for instance, HD 1080p stereo frames fast enough. Because of this, a Cloud-based 3DPC Extraction Platform was implemented (UCA- 1) based upon the aforementioned general architecture (DTF-1). This platform is based on the Robotics Operating System (ROS), and specially designed to be able to scale out and back depending on the computational needs at runtime (SCP-3). In order to do so, pipeline-based parallelism is exploited, as it can be seen in figure 3.2. Using a front-end node, the stereo stream is scattered to a set of 3DPC Extractor nodes in a round-robin fashion. This front-end node knows at runtime how many nodes are alive at any moment. Hence, if more computing power is required, more nodes would be dynamically added (thanks to a front-end node, as seen in figure 3.3). On the other side, if less computing power is required, then less 3DPC extractor nodes would be shut down. The performance of the platform was tested using a private cloud and using simulated stereo footage (UCA-3). Several tests were performed, which can be divided into two main categories: scalability and communication performance. In the first category the performance speedup was measured when increasing the number of virtual resources (SCP-1, SCP-3). The results (shown in table 3.1) show that, when the resolution of the image is sufficiently high (and therefore, the amount of required computation increases as well), the solution scales properly and considerable speedup is obtained. 9
10 Chapter 3. Summary of results FIGURE 3.1: 3D Point Cloud Extraction from stereo frames. Images taken from https://erget.wordpress.com/2014/02/01/ calibrating-a-stereo-camera-with-opencv/ FIGURE 3.2: Stereo frame pipeline process. Four nodes process (in a pipeline fashion) the frame pairs that the front-end node delivers in a round-robin form.
Chapter 3. Summary of results 11 FIGURE 3.3: Dynamic adaptation of the platform when the number of 3DPC Extractors changes. Execution Time (s) p/n 32 64 128 256 512 1024 2048 153.97 96.76 173 331 632 1213 2494 232.5 48.47 91.71 178 318 629 1218 425.38 33.84 55.09 106 186 437 904 627.07 36.66 51.48 87.02 171.3 351 635 TABLE 3.1: Total times to process and receive npoint clouds using p 3DPC extractors. Resolution of the stereo pairs is 1920x1080 and communication tehcnology used is that of Gigabit Ethernet.
12 Chapter 3. Summary of results Average Frequency of 3DPC reception (Hz) 320x240 640x480 1024x768 1920x1080 Gigabit 16.3 6.65 2.22 0.84 Wifi 11n 4.04 2.04 0.29 0.14 Wifi 11ac 4.98 3.02 0.76 0.24 Erratic Alone 7.15 2.61 1.01 0.02 TABLE 3.2: Performance measures for different communication technologies. ‘Erratic alone’ means that the Erratic robot is working alone, that is, working as a local stereo vision system. # Robots Mean Transfer Time (s) Average Message Success (%) 1 0.117 100.00 2 0.124 100.00 4 0.157 94.99 5 Hz 6 0.147 87.88 1 0.063 100.00 2 0.086 99.86 4 0.082 94.99 10 Hz 6 0.084 87.79 TABLE 3.3: Performance comparison when adding more robots in the case of 320x240 when no 3DPC extraction is done and only delays in stereo frame transmissions are considered. The wireless technology is that of 802.11ac. Note that the average time is for the messages that have arrived. Hence, a reduction in the number of successful messages In the second category, there are several tests focused on measuring which communication technology performs better (CCT-1). In addition to this, we also compare it with the "all on-board" computation case, so it can be seen when the Cloud outperforms the embedded system. The embedded platform used for testing is the Erratic Robot by Videre LLC, with a Core 2 Duo CPU. Results show that, at the moment, Gigabit Ethernet provides the least communication penalties, with 802.11ac still far behind. This shows that current devices and software drivers are still unable to obtain the promised 867 Mbps bandwidth. However, when the resolution of the stereo footage increases, the limitations of the embedded hardware start to arise, being offloading a reasonable option, even with 802.11ac (see table 3.2). In addition to this, an extra test was done for the case of 802.11ac (CCT-2). As the platform is expected to be used by multiple robots, it is necessary to analyze possible communication penalties when increasing the number of robots using the platform. The results show that, when increasing the number of robot nodes, communication penalties appear. There are two kind of penalties: delay in the message transfer time, and number of messages lost (see table 3.3 and figure 3.4). This shows an inherent tradeoff between the number of robots and wireless performance, and therefore solutions to mitigate this problem must be found (CCT-3). Some methods that can fin this problem are the following: changing the transport layer, changing the robotic middleware, implement TDMA methods[8]... amongst others. Once the Stereo Vision Platform was developed and tested, a real application case was proposeed: a Cloud-based navigation assistant (UCA-2). It is meant to assist the
Chapter 3. Summary of results 13 0.0 0.1 0.2 0.3 0.4 0.0 0.2 0.4 0.6 0.8 1.0 Cumulative histogram of transfer times (320x240, 5Hz) Delay (s) Fn(x) 5Hz − 1 node 5Hz − 2 nodes 5Hz − 4 nodes 5Hz − 6 nodes 0.0 0.1 0.2 0.3 0.4 FIGURE 3.4: Empirical Cumulative Distribution Frequency of delays with 5 Hz and 320x240 stereo frames. Note that this diagram only considers the messages that have arrived.
20 Chapter 3. Summary of results FIGURE 3.9: Two-Roofline Model for GIPS (Giga Instructions Per Second) vs. D I for the Snapdragon 610 S4 Pro. The diminution of maximum device GIPS is marked with down arrows. 2. If µcontinues with its expected reduction, these bounds will decrease close to a proportional rate. Therefore, future evolution for current technology is promoting offloading computation for embedded devices. 3. - When F→1or Nc,local = 1, the energy speedup is proportional to StxE = DI µ2. For simple devices or very parallel applications, energy efficiency of cloud migration is expected to be reached way earlier than that of timing speedup (quadratic order). In addition to this, this papers analyzes several example applications (DAXPY, matrix multiplication, and stereo vision), obtaining the following results: 1. For many applications, Fand DIgrow with the order of the problem. As a consequence, as new applications require more accurate solutions, using the cloud becomes a more viable solution. Moreover, future research should focus on trying to reduce NData. 2. When F= 1, the maximum achievable performance can be seen using an extension of the Roofline Model for GIPS (see figure 3.9). This helps to conclude that some applications, which have poor CPI and real GIPS are far from the maximum, may obtain benefits by moving its computation to the Cloud (as local device’s maximum theoretical GIPS cannot be achieved). Even though the real world is much more complex than a theoretical model, these Amdahl’s law extensions did help to encompass the main trends and have an idea of what the future holds for Cloud Offloading.
Chapter 4 Discussion Undoubtedly, Cloud Computing has become one of the top trending computing technologies in this decade[13], even though it is still at a relatively early stage. Cloud Computing is more than virtual web servers and storage (basically, this is for what it is currently known for). The Cloud still has an enormous potential to offer in the following decades, not only for humans, but also for embedded systems. Because of this, the rising interest of applying the Cloud in virtually every area is more than justified. Moreover, this is especially interesting in the area of robotics (Cloud Robotics), which is imagined like "offload compute-intensive tasks like image recognition and voice recognition and even download new skills instantly, Matrix-style" [14]. However, is it Matrix-style robotics far-fetched? Until what extent is feasible? As stated in section 1, this work aims to give answers to this question. But, has this thesis succeeded in bringing more light to the topic? In this chapter, this last question will be discussed. To begin with, this work has not been the first one in trying to demonstrate the validity of Cloud Computing for robotics. In this sense, several works can be found in the literature since approximately 2010 (even though the dream of Cloud Computing dates from decades ago[1]). In [15] an overall analysis of the Cloud Robotics area can be seen. Its general architecture, applications and technical challenges are described. About the architecture, it defines three cloud models: peer-based model (the one used in this thesis), proxy-based model and clone-based model. Regarding the technical challenges, the following are enumerated: high communication failure rates, virtual resource optimization, security and truth establishment and optimal energy consumption. One of the best known projects was the Roboearth project [4], which had as a main goal the creation of an "Internet for robots". Indeed, by having a cloud-based knowledge base where robots can share information, robots can not only perform collaborative tasks successfully, but also extend their capabilities by downloading new knowledge. Therefore, there are several areas where this cloud feature is being exploited[3], [16], such as human-robot interaction [17], healthcare [18] or world representation [19]. Moreover, this knowledge base helps the Cloud to become a global planner, as seen in [20] and [21]. These works, amongst others, show the great potential of knowledge sharing in different areas: healthcare, energy and transportation. Moreover, following the Roboearth approach, new global knowledge platforms are arising, like the Robo- Brain project, which will learn not only from robots, but also from computer simulations and Internet resources[22]. In this sense, this is simply a natural extension of the interconnected world mankind already enjoys. Nowadays, the necessity and effectiveness of interconnected embedded systems is so taken for granted that no thesis would be necessary to prove it. However, this is not that clear in the area of computation offloading. Indeed, its the main advantage is clearly seen: cheaper embedded devices could potentially perform complex tasks, thus saving money and energy. Nevertheless, as it 21
22 Chapter 4. Discussion can be read in [14]: "But Laumond and others note that the cloud is not the solution to all of robotics’ difficulties. In particular, controlling a robot’s motionwhich relies heavily on sensors and feedback - won’t benefit much from the cloud." The question is: is this statement axiomatic? will never Cloud offloading be beneficial when dealing with near to real time tasks? In this sense, together with this thesis, several works can be found striving to show for what cases this statement is not true: For instance, in [23] cloud offloading is applied to traffic light status detection based on image processing. Instead of robots, this work makes use of mobile phones which send camera frames to a Cloud server, responsible of detecting the status of the traffic light. Even though the task has time constraints, the Cloud is able to respond successfully in less than a second, especially by trying to reduce the amount of transferred data thanks to image compression. This relates to the necessity of reducing NData that was mentioned in section 3. Another example of image processing offloading can be seen in [24], where a cloudbased face detector is implemented. This system was implemented in a Pioneer P3- DX robot and wireless communication. Though their results are at an early stage (for instance, no performance figures are provided), offloading works sucessfully in this task. A widely used robotics application is that of Self Localization and Mapping (SLAM). Therefore, several works try to prove the viability of offloading this task. In [25], GPUs are combined with the virtual resources of a national datacenter, with everything connected using Gigabit Ethernet. Thanks to this, high resolution stereo footage (1224x1024) at 15 frames per second was successfully processed. Moreover, This paper points virtualization as one of the main sources of delays. In [26] the main difference resides in the communication technology used: wireless for the robot and fabric for the Cloud. This solution is based on landmark databases, which can be helpful for exploiting parallelism. This work states that using Cloud offloading increases the throughput compared with their previous on-board solution. This papers points as future research the necessity of examining the limits of network technologies, which is exactly what this thesis strives to analyze (see section 3). In the case of [27], a step further is taken, as a complete Platform-as-a-Service (PaaS) solution is here developed. This platform, Rapyuta, is general enough to be applied to any robotic task. On the other side, the dynamic scalability property is not exploited, as it is implemented using a Clone-based model[15], hence the parallelism is exploited inside a virtual machine. As a consequence, it would be necessary to shut down and respawn a bigger virtual machines in order to get more resources. A very interesting contribution in [27] is the combination of not only computation offloading, but also knowledge sharing, as a map is collaboratively built by two robots using 802.11n technology. In comparison with this thesis, Rapyuta also outlines the limitations of current 802.11n (802.11ac was not tested in this work) wireless devices in terms of throughput, proposing optimizations in NData such as keyframing and compression techniques. Apart from Rapyuta, other Cloud Robotics Platforms can be found in the literature. Continuing with the SLAM task, the C2TAM platform offers SLAM as a service [28]. They combine both computation offloading and collaborative work, as the framework allows fusing the information obtained from several robots. Thanks to the use of keyframes, NData is reduced, obtaining a data flow of 1MB/s with 640x480 RGBD cameras, perfectly assumable by the wireless technologies used in the paper. Another
Chapter 4. Discussion 23 robotics offloading platform is the DaVinci Platform[29]. Just like Rapyuta, it is meant to be used with any robotic algorithm, as long as it uses the Map-Reduce approach. In order to validate the platform, the offloading of the FastSLAM algorithm was tested using a dataset. Just like this thesis, the scalability of the cloud was demonstrated, obtaining considerable speedup when increasing the number of nodes. Compared with this thesis, their performance figures are better because FastSLAM is embarrasingly parallel. However, they did not consider the effects of network latencies or dynamic scalability. This can be put down to the fact that they were not dealing with task with real-time constraints. Another similar platform is that of REALcloud [30] which, compared to Da-Vinci, has security and user authentication as a major asset. In addition to these platforms, [31] presents the Robot-Cloud framework, which is also based in a Hadoop Cluster. It contains high level protocols and services that allow a robot to choose between several robotic algorithms. Just like Da-Vinci, it performs several scalability tests but using less compute nodes. In this sense, can be seen that the speedup results degrade when NData increases (in the case of three compute nodes, the speedup drops from 3x to 2x when doubling NData). Another example of robotic task with real-time constraints is that of object detection and tracking. In [32] this task is offloaded to the cloud using a decision based system. This is done by estimating both communication (802.11g is used) and computation times required to perform the task. This is related to the Amdahl’s law extension presented in this thesis. In this sense, the paper also considers bandwidth (denoted as β) and server speed (denoted as η) as important factors to take into account when offloading. Therefore, future work should try to apply this extension to their communication and computation estimations. In [33] high resolution SIFT-based object detection is speeded up by transmitting on-board preprocessed image information instead of raw image data to external servers (once again, this is a way of reducing NData). The configuration of these external servers is specific to this work, so some properties of the cloud computing paradigm are not exploited. In addition to this, authors of [34] present an object-tracking scenario for a 14-DOF industrial dual-arm robot using a UDP transport protocol for transmitting large-volume image over an Ethernet network. Thanks to the very low sending and cloud image processing times that are achieved, a stabilizing control law can be implemented, with time-varying feedback time delay. In addition to this, cloud offloading has been applied to grasp analysis and planning. Using a Hadoop Cluster in the Cloud, [35] offloads this task, obtaining successful results when increasing the number of nodes (they tested up to 500 processing nodes). Moreover, in order to increase performance, they propose using asynchronous parallelism, that is, to only wait for a subset of processing nodes to finish rather than waiting for all of them. Apart from new results to compare, this thesis does add new contributions to the area. To begin with, when reading most of the aforementioned works, a question inevitable arises: why calling it Cloud and not Cluster, Grid, or simply Server? There are already a vast amount of research works dealing with distributed systems, and most of the offloading tasks perfectly could be done in a simple server (actually, this is what several of the aforementioned works do). Is this simply a nomenclature change or really the Cloud has something else that previous distributed systems had not? This thesis defends that the Cloud does bring an added value, and properties like infinite resources or dynamic scalability should always be taken into account. In this sense, the platform here proposed was developed with this idea in mind: to be able to adapt itself to different computing needs at runtime. Hence, the classical distributed applications design pattern may not exploit the cloud’s full potential.
24 Chapter 4. Discussion However, having accepted that dynamic scalability is one of Cloud’s major assets, why would this be desirable in the case of embedded systems offloading? Why would a robot want the Cloud to scale back instead of having full processing power the whole execution? Reasonable question, if in the wrong era. Nowadays, having a vast computing system as the Cloud for just one robot sounds illogical. The idea would be to have tens, even hundreds of robots (or embedded systems) offloading tasks. Moreover, even though the Cloud is theoretically supposed to have infinite resources, the actual reality is quite different. Therefore, it is vital to transparently balance computing resources trying to maintain the best Quality of Service. As it can be seen, this differs little from what the Cloud is currently providing to enterprises and end-users, why would it be different for the case of robots? Hence, if we really aim for realistic scenarios, then talking about adaption and elasticity is simply mandatory. Following this idea, when dealing with a multiple-robot setup, it is vital to define proper scheduling and resource allocation strategies, in order to optimize both CPU and bandwidth usage. In this sense, [36] proposes a scheduling mechanism for multisensor data retrieval. It is based on market-based management strategies and it allows to set Quality-of-Service (QoS) criteria. Results show that time of response, reliability of response, bandwidth usage and CPU load are improved when using their proposed mechanism. This strategy could be extended for dealing with dynamic scalability, so the system is able to decide when to scale out and back. In this sense, there are other real-time scheduling strategies that could be used to extend the Stereo Vision Platform implemented in this thesis, for instance: QoS-aware scheduling [37] or scheming considering temporal overlapping [38]. Therefore, future work of this thesis should focus on studying, implementing and extending these different heuristics. Another contribution of the thesis is the application case: navigation assistance. Few of the aforementioned previous work has tried to study offloading in such a reactive and delicate task (where small errors do compromise the integrity of a robot). In [39] a theoretical cloud framework for navigation, but no implementation or real tests are provided. A more empirical approach is that of [30], where REALcloud is used by a robot to follow a line according to the images acquired from a single low resolution (320x240) camera that points to the floor. However, this thesis takes a step further and deals with a more complex approach, which has teleoperation and collision avoidance. After the experiments detailed in the thesis, we can assure that a robot has obtained better results using the Cloud than by processing on-board. However, it must be admitted that the developed solution still needs more robustness, as some collisions were unavoided. Nevertheless, this thesis did not intend to ditch on-board computing in favor of cloud offloading. This is not a matter of discarding, it is a matter of combinating. That is the main reason why this thesis also emphasizes the necessity of offloading configurations. Therefore, choosing carefully what to offload is the key to success in virtually any application case, even those with real time requirements. In this sense, in the area of mobile code offloading, there are several frameworks that try to analyze which parts of an application should be offloaded [40]. Most are based on code profiling, either automatic, like the COMET framework [41] or manual, like the ThinkAir platform [42]. However, this is not without issues and challenges [40] like inaccurate code profiling or integration complexity. In any case, extending these frameworks for robotic applications and, even more important, for real time constraints is a very interesting and challenging area of research. In addition to this, when it comes to offloading, the principles of multi-agent robotics systems (MARS) should applied [43]: modularity, concurrency, distributed architecture... amongst others. This would make the process of developing and offloading applications much easier thanks to these properties.
Chapter 4. Discussion 25 Closely related to this, we cannot detach computation offloading from another vital concept: communication. In this sense, this thesis offers a more in-depth analysis in both the key and state of current technologies, especially 802.11ac. If we really aim for successful offloading when having time constraints, delays in information must be thoroughly analyzed. Admittedly, the performance results shown for 802.11ac, even though its bandwidth is expected to be close to 1 Gbps [44], are still far from being "the Gigabit Ethernet equivalent of wireless networks". However, this thesis helped to turn the spotlight on future research works: •How can the variability of transfer times be reduced? Are the TCP and UDP layers enough for task offloading? As the TCP transport layer is not prepared for real time systems, it might be time to study and develop enhancements (or other alternatives alternative layers) especially focused in this kind of tasks. In this sense, further improvements in 802.11ac MAC layer like TDMA protocols, would reduce substantially this latency variance [8]. Moreover, Contention Free Period in the infrastructure mode with fixed size packets could guarantee a minimum bandwidth reservation, which may be suitable for many real time systems. If we really aim for successful offloading when having time constraints, some QoS mechanisms should be incorporated to allow differentiation between traffic types and guarantee allocation of resources to the offloaded applications with real time requirements. These QoS mechanisms can be classified into two main categories:"Traffic handling mechanisms” or ”bandwidth management mechanisms" [44] . Traffic handling mechanisms are designed to classify, handle, and monitor the traffic across the network, while bandwidth management mechanisms manage the network resource and coordinate the network devices. Typically, mechanisms from the two categories can be used together: for instance, packet classification may be used to distinguish between different kinds of traffics and then an admission control mechanism takes a decision of accepting or not the incoming flow according to its QoS requirements and the available network resources [44] . With IEEE 802.11ac, enhanced distributed channel access (EDCA) is the primarily adopted access control mechanism for multimedia traffic transmission, so it seems that it could also be used when offloading applications with real time requirements. However, its inefficient backoff procedure may introduce unpredictable delays [45]. There are still many open research issues with regard to this important question. •To what extent non real time middleware and variable data transfers affect a soft real time system? Not only current hardware must be enhanced, but also the available software and frameworks like ROS should have a focus on real time requirements. •What happens if suddenly the communication is broken? A robot that relies solely in the Cloud lacks enough robustness. Hence, offloading solutions with fallback mechanisms in case of network fault should be studied and analyzed. •Can the negative effect of delayed information be circumvented by using predictive time corrections[9]? If a predictive method is implemented, then robots may afford to use delayed information even with reactive applications. Apart from all this, computation offloading cannot avoid the following questions: is this just a short-term trend? will embedded hardware develop with such a pace that
26 Chapter 4. Discussion FIGURE 4.1: Concept of Peer to Peer Cloud applied to Robotics. The leftmost robot makes use of the computational resources in the Cloud but, instead, the second robot makes use of the resources of a third robot renders Cloud Offloading useless? In this sense, [46] stated in that Cloud Offloading can be beneficial for some applications. As a very interesting idea, it must be taken into account that if the data is already stored in the Cloud, no data transfer would be necessary, only a pointer to it. That implies considerable energy savings. Just like [46], this thesis did not hide and strived to provide answers, not only in the case of energy but also in the case of performance. That is the reason why another contribution was a deeper study in the concept of offloading, having as a result the extension of Amdahl’s Law for Cloud Computing. Thanks to this research, it could be seen that Cloud Offloading will have its place due to both current technology and software trends. Moreover, it helps developers and researchers to have an idea of whether a certain computation should be offloaded or not. In addition to this, this extension of Amdahl’s law shows a tendency: in the future, computation offloading will be more and more beneficial. Therefore, another question arises: what is the role of other computing platforms like embedded Graphical Processing Units (GPUs)? If, down the line, offloading will provide better performance and energy results, then maybe embedded GPUs could be the technology with an expiry date (obviously, GPUs could be of great use in the Cloud, but probably not in the embedded system). Furthermore, Field Programmable Gate Arrays (FGPAs), which offers extraordinary performance results (thanks to its hundreds of available functional units) are also increasingly becoming more energy efficient. Hence, it can be assured that, in the future, two computing choices will prevail: very simple devices that use computation offloading (this is very related to the rise of Internet of Things [47] and Cloud Computing, known as Cloud of Things [48]) and reconfigurable computing devices. Of course, in order to provide the Amdahl’s Law extension and its inherent predictions, it was necessary to make some simplifications and assumptions. Not to mention the fact that, for complex applications, obtaining the parallel fraction Fcan be extremely challenging. However, is not less true this was the necessary first step in order to develop a deeper and more ambitious theoretical framework. In this sense, future research could study and model issues like virtualization, middleware and OS overheads, task scheduling, amount of overlap between transfers, heterogeinity of hardware resources between cloud and the embedded system... amongst others. In addition to this, this thesis’ results point where future research and development
Chapter 4. Discussion 27 should focus on, for instance trying to increase DIand reduce NData of applications by developing new software and compressing techniques. Not only this is important for performance, but also for energy efficiency. As it was mentioned before, this effort to optimize these values can be seen in several works [23], [27], [28], [32], [33]. Moreover, in cases where the data to be sent are images (just like this thesis), there are other works that propose energy-efficient compression techniques which are worth applying in Cloud Offloading. For instance, [49] proposes a bandwidth aware compression method, obtaining a 20% energy reduction average. In addition to this, [50] proposes a method based in dynamic switching of compression level based on the available bandwidth, thus optimizing data transfer. Apart from this, it is important to study cross-layer transmission techniques to, once again, optimize communication and energy savings [51]. For all this reasons, it can be assured that this thesis, with its issues and limitations, not only provided experimental contributions to the scientific community, but also it is a first step in the development of a future Cloud Offloading theoretical framework. As a final discussion item, there is another element that should be taken into account: practically all the mentioned works, including this thesis, treat the cloud as a centralized platform that robots make use of. Hence, another question arises: is this enough? Should we go a step further and make robots "part of the Cloud"? This is especially related to the concept of Peer-to-peer Cloud [52]. Let us imagine a set of heterogeneous robots performing several tasks. If one of the robots has plenty of computational resources, these could be offered to the rest of robots for offloading (see figure 4.1). Thanks to this, robots would have more flexibility when choosing where to offload their tasks. In this sense, [53] proposes the Robot-as-a-Service framework, where thanks to the use of web 2.0 technologies and Service Oriented Architecture (SOA), a robot would be Cloud Computing Unit, just as Software, Platform or Infrastructure. This idea is extended in several works. For instance, [54] integrates the use of SOA and Map-Reduce algorithms in a Hadoop Cluster. In [55] an algorithm for providing robotic resources in order to satisfy a certain QoS is proposed. In addition to this, in [56] the RoboWeb architecture is created. This architecutre exposes both robot’s software and hardware and exposes them as services through the Web. Another related concept is the term "Robotic Cluster" introduced in [57]: "group of individual robots which are able to share their processing resources, therefore, the robots can solve difficult problems by using the processing units of other robots". In this sense, [58] applies this concept to the use case of SLAM, developing two archictectures (stateless and stateful) in order to cope with the limitations of bandwidth. The speedup results obtained are promising, hence the combination of robotic clusters, robots as a service and centralized approaches would extend Cloud Offloading capabilities. An example of this can be seen in [59], where an engine for collaboration between networked robots and public clouds is developed. This platform makes decisions of where each task should be executed (either in the robots or in the Cloud). At the moment only two policies have been implemented: minimum energy and minimum budget (as it is using a public cloud, using its resources cost money). However, it is a perfect starting point for future work in integrating both centralized cloud and cluster of robots. Therefore, as it can be seen, the definition of Cloud Computing keeps evolving through the years, and in this sense, the results of this thesis strived to take a step forward in this direction.
Chapter 5 Conclusions •Cloud Offloading can be beneficial even in applications with near to real time applications. It is here demonstrated that the teleoperation of a mobile robot using a cloud-based navigation assistant (using stereo-vision obstacle detection) provided better quality than its all-on-board counterpart. •Not all applications may benefit from Cloud Offloading. Several parameters must be taken into account: data size, bandwidth, local resources, potential energy savings, response time, characteristics of the application... amongst others. In this sense, the most important parameters are the density of instructions DI=NI NData and the technological factor µ, which depends on the execution power of the local embedded system and the available network bandwidth. •Current 802.11ac wireless devices are still unable to provide speeds close to Gigabit Ethernet. However, they perform better than 802.11n devices. If future developments of WiFi AC obtain throughputs close its theoretical 867 Mbps, substantial speedups could be obtained. •Benefits of offloading increase with DI/µ linearly in performance but quadratically in energy. •Researchers and software developers should target in increasing DIand reducing NData by compression and software techniques. •There is an inherent trade-off between computation and communication in Cloud Offloading. Therefore, when developing applications, all the different offloading configurations (that is, which modules must reside on board or be offloaded) must be analyzed, especially the implied transfers. Not every offloading configuration provides successful results. •Trends indicate that µwill decrease in the future. As DIand F(parallel fraction) grow with the order of the problem, Cloud Offloading will become more and more beneficial as years go by. Therefore, the full offload of computationally expensive applications will become preferable, even for tasks that nowadays provide better results when running on-board. Future work: •When offloading tasks with time constraints, a big issue is the delay in the processed information. In order to mitigate this effect, predictive time corrections should be studied and developed. •Current middleware and transport layer technologies introduce high variability in the information transfer. Research should focus on studying the performance given by alternative standard and non-standard technologies and platforms. 29
36 BIBLIOGRAPHY [56] Anis Koubaa. “A Service-Oriented Architecture for Virtualizing Robots in Robotas-a-Service Clouds”. en. In: Architecture of Computing Systems – ARCS 2014. Ed. by Erik Maehle, Kay Römer, Wolfgang Karl, and Eduardo Tovar. Lecture Notes in Computer Science 8350. DOI: 10.1007/978-3-319-04891-8_17. Springer International Publishing, Feb. 2014, pp. 196–208. ISBN: 978-3-319-04890-1 978-3-319- 04891-8. URL:http://link.springer.com/chapter/10.1007/978-3- 319-04891-8_17 (visited on 11/03/2015). [57] Ali Marjovi, Sarvenaz Choobdar, and Lino Marques. “Robotic clusters: Multirobot systems as computer clusters: A topological map merging demonstration”. In: Robotics and Autonomous Systems 60.9 (Sept. 2012), pp. 1191–1204. ISSN: 0921- 8890. URL:http://www.sciencedirect.com/science/article/pii/ S0921889012000632 (visited on 11/03/2015). [58] Bruno D. Gouveia, David Portugal, Daniel C. Silva, and Lino Marques. “Computation Sharing in Distributed Robotic Systems: a Case Study on SLAM”. In: IEEE Transactions on Automation Science and Engineering (T-ASE) 12.2 (Apr. 2015). [59] P. Pandey, D. Pompili, and Jingang Yi. “Dynamic Collaboration Between Networked Robots and Clouds in Resource-Constrained Environments”. In: IEEE Transactions on Automation Science and Engineering 12.2 (Apr. 2015), pp. 471–480. ISSN: 1545-5955. DOI:10.1109/TASE.2015.2406115.
Part II Set of papers 37
Appendix A Mobile robot motion planning based on Cloud Computing stereo vision processing Authors •Javier J. Salmerón García •Pablo Íñigo Blasco •Fernando Díaz del Río •Daniel Cagigas Muñiz Publication Title: Proceedings of 41st International Symposium on Robotics (ISR 2014). Type: Conference Paper. Conference Name: 41st International Symposium on Robotics (ISR 2014). Place: Munich, Germany. Date: June 2014. Publisher: VDE. Date: 2016. Pages: 1-6. ISBN: 978-3-8007-3601-0. 39
!"#$%&'($ )*+ - !"#$% ($ ./0 !"#$%%0($ / 1+0 !"#$% ($ 23!%343 !56%%% !76% %$83% 9 :! %%% $*3 !07%%% 7%%<7% $=!%7 >?4!5 7$ 23!767 %3%!%%$= 3637%% 6%& 6 @ $836!! !!6 $8 % 9 %% :4$$ 6 7!5 %%6 ! 3$ = %%97 !:%% 6 < ! !30 %3!! 0$*!!! 4% 3 6 5! %33 % ! $=% & % % %3!ABCA'C$-9: 3% %76 % !4'5$ =%!!6 03%%% !!36 $!3 $D7% "=14 0 5 4?! 536%!% AEC$ *39%% :% 6<E/7 % $)4E/)5 %% 6 % $ 7E/% !! 3 %$23 %$ *6% %3 !$*7% 336! %%%3647 E5$ * 7 6 %3 3?$8!! $*7? 3! %0%$* % % 3 % 63 %%%% $ /% % 4 %5 46& $5? $ % 36! !4$ $ Conference ISR ROBOTIK 2014 657 ISBN 978-3-8007-3601-0 © VDE VERLAG GMBH · Berlin · Offenbach
35%3 3%%3!$ '036 !% E 4 3!5$ D7 3 F ?%! %% %%%%! 0G$ *%3!36& 63? ABCHAEC$1% %%% 663 $*! 37 $ 83 %%% %%%6% $. %$*AFC *.&! % %3 7$8% %!7 % %7 %36$ %I%% ! AGC$% %6% &6 0 7 4 5$!6 %% % & % %% 3 6 70$ *AJC&6 %BF/I. $#/) % D36$6!3 0 3$/ ! D! $ .!36AKC63% %%% 63 7 $ L 7 %4%3 3 %5 % %!% %$ . B36 % !$*36 $ !336 %% %4 AMC5$N %3 $= %%% %$% % 4 3 % 5% %!%%3! % 64B5$ L%7% % &3$ 6 !6%7 % 4E/)5% 3% !4 B5$ %% 45$*36* $ / ! % % ! ! !$*%%3%36 !36)$ %%!$ E/) % * 3!7% ! " #$ %&' ' #$ %&' #$ %&' #$ %&' #$ %&' #$ %&' %$#&'(% !" )#$ %&'* $#& Conference ISR ROBOTIK 2014 658 ISBN 978-3-8007-3601-0 © VDE VERLAG GMBH · Berlin · Offenbach
"=1 4 3 5$ !" * ! %36%)" ! 4)" <OO333$$ 5 IN "!4333$$ 5$ &%'/OE/ !I4I !5 !$ 1!I6 %%3 6%!0%% %! 3E/ %$*I 4 I53 $.! % 4! 5$! %% 4%! 5$L%% !4! 5$. !3%% E/4E/) 5$6 %7% 3$/!%% %%% %37% 4!! 3% 3 5$ *3% 3%7 3 %!$=%6 %E/)7 %%%% !! % 3?4%7 3 %?!5$L 3 . '< $ D%3%% %$ %%% 3% 3!! 3 $* 3 % %%! %%3!$ !3 % %% $ #$# ) %% 36 ! %3.36 IAPC$. E3% % 4 %3 ! 3 5$ 3 ! ! 3%% < %% % !$ 64 ! 35$8 ! $I 7 3$ )%%!% I%%?!$ %$D% %4% ! % !5$ 7 E/) $37 E/)6$*%3 &47 E$B5 ! %33 $%3 %4. E54%5 %436 . E57 $ I% ! %% 4. E5 % %%4 . E5$ % 3! 43 % 5$ !"#!$%! !!& !'!$!$$ !#!$'!" " '+ %", %"- %". %"/ Conference ISR ROBOTIK 2014 659 ISBN 978-3-8007-3601-0 © VDE VERLAG GMBH · Berlin · Offenbach
=!! 0%%%%$. 7 < 73 $*%) %% Q$QE 3! 3 % 4F53!Q$' $I%!03 ! /1=!% 7!%$ % &' %7% %% 43 5$%% %G!4B%F 5$D()*!+,-./ )# 43 7 5 M - % =1$! 0 1! 3 !23! 3 4 3 63 83336 3 !5$ % !$ %% !%36 !$3 4BP'Q7BQMQ 75 E/) $*7 %! % 3%% 4! 56/6-7'383BJ-% =1$1%)3640' 5!$= %%3 E/)6 $ =01! % 7%% %7E/)% $ 2!%3 E/) %%!%%? % ! %!# # #! #$ !$&$ %3 B ?% !%3*797 %$ = % 4 3%B%5 %?! F %43 % %5$*!6 % 3%% %?!?! $ :;$! #$.!!# !$")# !$# #!!!! $!< !## $$$$" )* " '+ .&01 0 2" 1 &"" 1 .&0" 0" .&" ) 334* ; ; !$!! #$#!# #!!$" #! +7.797 5 .- 6/ ,-7 -86 8,- ,9-/ -9/7 , 8.3:; :63;6 ,;. .., 6.- ,-,. -/:/ - .-38 /73/; :,3;, ,;7 .,7 6-: ,-,7 / -83.7 ..37/ 8839: ,96 ,76 /.; :9/ 6 -;39; .6366 8,3/7 7;39- ,;,3. .8, 6.8 Conference ISR ROBOTIK 2014 660 ISBN 978-3-8007-3601-0 © VDE VERLAG GMBH · Berlin · Offenbach
% $ " I!% 7 3%% %% $=%0' 1!% %43%3 !!56 3$ L333 < 411197"!=411197"=$ ?7 3%0$*7 !4ND !""5$% RJ $ '3%?!%!%%% %%%$3% %$.%% %7 E/)%% %%3 7% 3 ! $3%<D 3% 4%% % %!%5 363 34% *%BQD 5$ /3?!%% 3$% !%%% % $ *3 3 %4%5%? %01! %%% F$'$*% 3% )#=1F %$D %%! %%%3%% !4 % %% E/) 3 5$ #%!% 3 %! % % 4!%% E/)5$ 3 % 3%! %3!6$=7 %3%! $= % %3 < %7 3 !4%%30%!5$ 1 4 % % E/)65 3!% 463 5O! 3$23 !36!36 %? ! E/) %%4! % E/)53 !$ %333 !! 3 !$ % #$ % !! %$ 6 7 E$'7 E/)% %$D!% %3! E/)$ * !!% % ! 3 ?$. 6 % 3 $ D%4 !5 !7 %% !$=? %3!7 $L%E3 4 BQ'FSKJM %5 % %% $ 33%D 34365$ %3! % $ *! 6 %% 7E$'4 5 %!$ ! % $* % %%3 %%3 %%4% B%5$ 3 3?!% 3 ! $ =! %%$= !% ; !#$!#' !!! " Conference ISR ROBOTIK 2014 661 ISBN 978-3-8007-3601-0 © VDE VERLAG GMBH · Berlin · Offenbach
!7$ %%<B5I3'5 7!%E/)%E5)F5% 6&36%%1= !$*363! $-%3! 36 % $13 % 97"1=!6 /1=3!! $=/1=% .)% 3%706$ !%/1= 33! %!!$ ( 363%% %! 646 5$33<& !!33 !!%!3? !6$I! 3%%% 3 ! ?&%!% %$& 6%%% $*% %?3 36$L77 %33633 7%3!$ I ! < 3 %)3 ! $.36 36 ! 6% 3 36$ ) 36! 43 %D /.5 -*ID2D 4D'QB'EKMJMQFQ'OQB5 ! = D7 )& 43%D / .51*2DN=4)B'*BEQQ5$L36 )%$/$% $ * " ABC D$0093: 4111#$FM$E$BJHBM1$ 'QBB$ A'C $= N$$D"$- L$T& U$-6.$.$U =$$UU$/$1 $L$U9/=<= % 36%:7741114!!!' 5!!!!$(#!%45(& 'QBQ$EQMFHEQMP$ AEC D9LD V:AIC$ =< <OO$ O7$ WE.RB'K'$$A=<QG.'QBFC$ AFC 8$-!$X 9= 76 !: 774111>4!!! 5!! ! 4! ! !$ %4&'QBQ$EBPGHE'QQ$ AGC Y$2 U$UY$8$"$$$ "9 & 6 %% : 77 4111> 4!!! 5!! !4! ! !$%4&'QBQ$'FFPH'FGG$ AJC 8$L"$"$$$8U$ U0 9- 236 N : 4111 ;!! ! 4!$# 1 ' !$JQ$'$GGFHGJJ.$'QBE$ AKC "$= "$I$..$)/$ D$0D$9= D% 236 =: 74111?!4!' !! 5!!!*!$ <(#!!$ #5#!%*(5&'QBB$BBBQHBBBJ$ AMC )$*+ -.$/0$N/0 /$ 1+09/! L3 = % 28 = : FG * ! 4* 'QBF5 4)51'QBF$ APC 1$Z !U$!-$6!$.$. $"$L=$2 9I< I !:'QQP$$ ; :($ #01' !!7/.6,9 #!" Conference ISR ROBOTIK 2014 662 ISBN 978-3-8007-3601-0 © VDE VERLAG GMBH · Berlin · Offenbach
Study of Communication Issues in Dynamically Scalable Cloud-Based Vision Systems for Mobile Robots Javier Salmerón-García, Pablo Iñigo-Blasco, Fernando Díaz-del-Río and Daniel Cagigas-Muñiz Abstract Thanks to the advent of technologies like Cloud Computing, the idea of computation offloading of robotic tasks is more than feasible. Therefore, it is possible to use legacy embedded systems for computationally heavy tasks like navigation or artificial vision, hence extending its lifespan. In this chapter we apply Cloud Computing for building a Cloud-Based 3D Point Cloud extractor for stereo images. The objective is to have a dynamically scalable solution (one of Cloud Computing’s most important features) and applicable to near real-time scenarios. This last feature brings several challenges that must be addressed: meeting of deadlines, stability, limitation of communication technologies. All those elements will be thoroughly analyzed in this chapter, providing experimental results that prove the efficacy of the solution. At the end of the chapter, a successful use case of the platform is explained: navigation assistance. Keywords Cloud computing ·Computation offloading ·Robotics ·Dynamic scalability 1 Introduction Nowadays, new computationally expensive tasks are expected to be performed with relative fluency by robotic platforms. A well-known example is that of artificial vision and higher level tasks arisen from it, such as object detection, recognition and tracking; surveillance, gesture recognition, etc. However, these tasks are so computationally heavy that they may take several seconds in current embedded robot computers. Hence the advantages of using computation offloading (i.e. moving this computing task to an external computer system) are becoming evident in terms of time to finish the task, mobile robot energy saving, amongst others. J. Salmerón-García (B )·P. Iñigo-Blasco ·F. Díaz-del-Río ·D. Cagigas-Muñiz Escuela Técnica Superior de Ingeniería Informática, University of Seville, Av. Reina Mercedes S/n, 41012 Sevilla, Spain e-mail: [email protected] © Springer International Publishing Switzerland 2016 A. Koubaa and E. Shakshuki (eds.), Robots and Sensor Clouds, Studies in Systems, Decision and Control 36, DOI 10.1007/978-3-319-22168-7_2 33 [email protected]
34 J. Salmerón-García et al. An interesting candidate for the aforementioned external computer system is that of a Cloud infrastructure, thanks to its inherent characteristics [7]: high reliability, larger storage capacity, stable electric power, reutilization of hardware, dynamic scalability and better resource utilization. In particular, the dynamic scalability property is very useful in robotics, as it allows the adaptation of the computing power at runtime (that is, scaling out and back, depending on the needs), and therefore it permits the robot to rapidly adapt in a changing environment. Moreover, another advantage of the Cloud is the instant incorporation of more computation demanding algorithms as they are being implemented. Apart from computationally heavy tasks, the cloud is being used as a centralized powerful infrastructure for multi-robot cooperative systems that usually works at intermediate levels. This area is intensively studied as new cooperative algorithms are being developed. Examples of these solutions are multi-robot SLAM (simultaneous localization and mapping), map merging (acquired by several robots), networked information repository for robots [23], etc. As a result, an important number of research papers and projects addressing the use of cloud infrastructures in robotics have been published during the last few years (see Sect.3). Besides, the term Cloud Robotics has emerged to include this area, which promises a fast development of complex distributed robotics tasks in the forthcoming years. This chapter addresses the “computation offloading” of an intermediate robot level task: 3-D point cloud (3DPC) extraction from stereo image pairs. In order to do so, a Cloud-based 3DPC extraction platform will be developed. This platform has innumerable applications, such as AI, artificial vision and navigation. The latter is especially interesting, as 3DPCs are one of the most used representation for several navigation tasks, including those of motion planning and obstacle avoidance. Because of that, at the end of the chapter (Sect.6.5) a navigation use case of our platform will be briefly explained. In this respect, current embedded computers are able to extract a 3D point cloud and to build a map of the surrounding obstacles in a natural and dynamically changing environment in less than a second, providing that low resolution frames are used. Nevertheless, when an accurate vision is needed, frame resolution must be increased. In addition to this, should the robot be in a fast changing environment, then higher frame rates would be necessary. As a consequence, the limitations of robot embedded hardware will likely arise, and thus sending the stereo image pairs to the cloud can compensate the inherent trade-offs of network communications (explained in Sect.5.2 in more detail). In order to exploit the cloud capabilities, the implemented platform must be able to scale out and back, so the robot gets the results faster when more computation power is required. Hence, a dynamically parallel algorithm has been implemented. In this context, the quotient between computation and communication times mainly indicates if the parallelization is to be successful. The developed platform is expected to be applied to near real-time systems as well, which is not without several challenges in terms of meeting deadlines. In this respect, the ratio between local-to-cloud transfer [email protected]
Study of Communication Issues in Dynamically Scalable Cloud-Based Vision … 35 time (especially in the case of large amounts of data) and computation time in a single node must be taken into account as well, as it indicates the usefulness of cloud offloading. Section3summarizes several related works. Before presenting the developed platform, a thorough analysis of which robotics tasks (especially those that need some soft real time requirements) are candidate for computation offloading is done in Sect.4. An overall analysis of the implemented solution is depicted in Sect.5(together with a time analysis). Experimental results are shown in Sect.6to quantify the benefits of the cloud approach for different scenarios. In this last section, we summarize an example application case of the presented platform: a navigation assistant for mobile robots [19]. Finally, conclusions are summarized in Sect. 7. 2 Background This book chapter covers several areas. The first (and most important) is that of Cloud Computing. In this sense, books like [20] can be helpful for understanding its inherent characteristics. More specifically, this chapter focuses on the idea of computation offloading of High Performance Computing applications. Therefore, so some basic concepts this kind of applications, together with basic concepts on parallelism applied to cloud computing, are crucial to understand this chapter. These concepts are clearly explained in [4]. In addition to this, the developed platform is used for stereo vision, and more specifically in 3D Point Cloud extraction. The readers can find several works in the literature regarding this specific topic, for instance [22]. However, it is not necessary to know how a 3D Point Cloud is obtained from stereo frame pairs (that is, debayering, rectification, amongst others) to understand the contents of this chapter. Moreover, The presented software solution was developed using the ROS Platform. Basic information about this software, together with beginner tutorials, can be found in their wiki (http://wiki.ros.org/). In [12] there is a thorough outline of current Robotics Software Frameworks (RSF). Finally, communication issues are covered in this chapter. Therefore, readers can read [21] to get basic knowledge about basic networking concepts and technologies. 3 Related Work In the last few years works and projects that accomplish high level vision tasks without real time requirements are more and more common [2,9,23]. Most of them use the cloud robotics paradigm to offload the robot from high level tasks like those related with visual processing or multirobot cooperation. In our opinion this is a tendency that will burst in the next decade, due to the previous cloud computing advantages. [email protected]
36 J. Salmerón-García et al. However, a small group of papers proposes offloading the processing of several parts of the sensor feedback information that are near to real-time. For those operations, a fast and reliable response is needed. In [3] a high resolution SIFT-based object detection is speeded up by transmitting on-board preprocessed image information instead of raw image data to external servers. Here, properties of the cloud computing paradigm are not fully exploited, because the configuration of these external servers is specific to this work. The idea of Computation Offloading is studied in [16]. These authors present an estimation of the computation and communication times needed for the tasks of recognition and object tracking in order to minimize the total execution time (approaching the real-time constraints). Their analysis permits making offloading decisions for object recognition for different bandwidths, background complexities, and database sizes. In this sense, the method for identifying the optimal balance between a cloud system overhead and performance presented in [8] can be useful. Executing SLAM in the cloud is also studied in [18], where they develop a cloud mapping framework (C2TAM). They combine both computation offloading and collaborative work, as the framework allows fusing the information obtained from several robots. They work with a 640 ×480 pixel RGBD camera and an average data flow of 1 MB/s, below 3MB/s, which is the usual wireless bandwidth and hence the mapping is successfully done (moreover, they work with keyframes, reducing the amount of images to send). In [24] an object-tracking scenario for a 14-DOF industrial dual-arm robot is presented. Standard UDP transport protocol for transmitting large-volume images over an Ethernet network is used. Thanks to the very low sending and cloud image processing times that are achieved, a stabilizing control law can be implemented. Due to the inherent time-varying Ethernet protocol delays, actuation signals incorporate an ingenious hold action. Finally, the work [1] also asks whether the performance of distributed offloading tasks can be compared with those executed on-board. While the experiment performed here is simple (a visual line follower that guides the robot using a single low resolution camera that points to the floor), this demonstrator gives an idea of the possible scenario for many cloud-based robots of the upcoming future. Contributions of the chapter: Compared with the described literature, the work presented in this chapter is the first that tries implement a stereo vision platform with focus on both dynamic scalability and near real-time applications. Moreover, a general offloading architecture (applicable to any case) is proposed, used to implement the presented platform. In addition to this, a thorough explanation of the the role of communication technologies, the problems of multi-robot and WiFi AC adds more novelty to our work. [email protected]
Study of Communication Issues in Dynamically Scalable Cloud-Based Vision … 37 4 Cloud Offloading for Robotics Applications Figure1shows a block diagram of a Cloud-based computation offloading robotics applications. The robot’s controller will collect any necessary environment information (using both internal and external sensors) to send the most convenient action to the actuators. Usually internal sensors (e.g. odometric) and simple sensor (e.g. sonars) are easy to be processed on-board, so they provide a fast and reactive feedback to the robot. On the contrary, the robot can include some others more complex or high level sensors (e.g. cameras), whose processing algorithms are more demanding both in computing time and energy. Because of this, the Cloud-based approach aims that the robot’s controller will be freed from heavy computations by offloading. In order to do so, it must send to the Cloud all the sensor information. While the size of high level sensoring is usually big, the rest of sensors suppose a few additional bits; hence all the information can be sent to the Cloud. This will even allow the Cloud to do more involved sensor fusion algorithms without demanding real time constraints (like SLAM). While the Cloud is performing all those high demanding computations, the robot can dedicate its computing power for other (real-time) tasks. Once the Cloud has the processed information ready and tailored to each robot, the robot will receive it and make use of it for whatever operation the robot may require (e.g. vision, AI, trajectory modification, etc.). Cloud offloading provides additional benefits due to the inherent centralization that the Cloud supposes for a distributed robotic team. For example, team collaborative tasks can be more easily and fluently handled in the Cloud as it can manage complete information from all the robots. Even though its advantages are evident, there are several communication bounds and development issues when offloading robotics tasks. The software architecture (and its components) of a complex robotic system must cater for a variety of characteristics, which distinguish it from other system. The most relevant characteristics of are [12]: Concurrent and distributed architecture, Modularity (several components of high cohesion but low coupling), Robustness and fault tolerance; and real time Fig. 1 Block Diagram of a Cloud-based computation offloading system [email protected]
38 J. Salmerón-García et al. efficiency. The first two characteristics are primarily benefited by cloud offloading, while the third introduces new challenges (network robustness and fault tolerance appear as a new aspect to considerate). Nevertheless, due that the platform described in this chapter must cope with timing efficiency, communication delays are analyzed in the rest of this section. As explained in Fig.1the robot has to send sensoring information packets to the cloud and wait until it receives the Cloud answer. The communication delays suppose an obligatory inferior bound in the loop controller period. Let BW be the network bandwidth rate and D, the total amount of transmitted and received data. Therefore D/BW must be inferior to the controller deadline. This minimum bound does not suppose for current network technologies a limit, except for the very reactive tasks. For example a WiFi AC networks can deliver until almost 1Gbps [5]. Even for a demanding control loop of 50Hz (higher than most mobile robot control loops), this bound would not be exceeded if the transmitted data were less than 0.02 Gbits, because the loop period is 0.02s. If images are to be transmitted, an amount of 20Mbits of data represents 8 raw B/W images of 640 ×480 pixels (or 32 images for a lower resolution of 320 ×240 pixels). This suppose that the robot is sending 4 (16 for the lower resolution) stereo frame pairs at each period (without any compression). This is not the common case for a current robot, which is equipped usually with only one stereo camera. Moreover, currently the steady incremental ratio of WiFi networks is more than 40% per year, which means that only in two years the bandwidth is predicted to duplicate. Hence it can be assured that theoretical bandwidth does not impose a limit in computation offloading. Nevertheless, this may not be the case for latency variability, as our results in Sect.6.4 demonstrates. Going further, a quantitative comparison of the times involved in local versus remote computing points out new outcomes. Let IPS the rate of instructions per second that the robot computer can execute [11]. Let us assume that the cloud can speedup an application Stimes more than the robot, that is, it gets an IPS of S·IPS. A high Sis expected because of several reasons. Firstly, the cloud is expected to have far more computational resources than a local (usually low power consuming) computer. Likewise, there are big amounts of data parallelism to be exploited when using many sensoring information (image processing, object, voice or face recognition, etc.). Finally these tasks are usually very repetitive. For instance, in image recognition, a pattern has to be compared with thousands of stored patterns. Hence, it can be supposed that Sis very big for most sensoring applications. Therefore, for NIcomputer instructions local and remote execution times are: tlocal =NI IPS;tremote =NI (IPS ·S)+D BW; And we can obtain this formula for timing comparison: tlocal >tremote if NI D>IPS BW [email protected]
Study of Communication Issues in Dynamically Scalable Cloud-Based Vision … 39 which indicates whether computation offloading is faster than local computation, and gives us a prospect of which applications are prone to be offloaded. For example, let us compute an estimation of the two members of previous inequality for the Erratic Robot, which CPU runs at a frequency f =1.4 GHz and has a CPI (Clocks per Instruction) around 2.0 [14]. Hence, if a frame pair is computed by this robot in texec =0.96s (see Sect.6), the number of instructions that are executed [11] results: NI=(texec ·f) CPI =6.72 ·108instructions Besides, transmitted data of this experiment (see Sect.6) consists mainly in a color 1024 ×768 frame pair, that is: D=1024 ·768 ·3·2·8=3.77 ·107bits. Hence: NI D=17.8instr/bit Let us remark that the first term of the inequality is application dependent, which means that high intensive computing tasks will be benefited by cloud computing. On the contrary, the second member is mainly technology dependent. Being IPS = f/CPI [11], the Erratic CPU IPS =7.0·108instr/s, but others platforms can achieve a higher IPS. Moreover, a 400 Mbps data rate transmission can be easily reached with WiFi IEEE 802.11ac. With these values, offloading is not bounded by time latency, as the second term has a very much lower value (1.75 for actual case) than the first one. As a conclusion, networking bandwidth is crucial for a successful offloading. Let us finally make some predictions about the tendency of these two terms. If the last decade trend continues, uniprocessor IPS will have an annual growth rate much inferior to that of network technology [11]. This means that cloud offloading is promised to take even more advantage for the next years. With respect to the software development, it seems that the only possibility to speedup embedded CPU IPS is by means of more parallelism (and by more efficient tools to develop it). But this, indeed, would be beneficial for the advancement on cloud programming. To sum up, it can be concluded that those applications with ratio NI/Dbigger than a few units, are currently candidates to be remotely executed. Those where this ratio would be inferior may be successfully offloaded in a few years. This includes many tasks from the top, middle, and even lowest, level of a common layered robot architecture (see Sect.1). Moreover, independently of this ratio value, there are applications where the size of required (stored) data is huge (see Sect.1). For them, maintaining local massive storage (in terms of power, failure immunity, backup, weight, etc.) is a hard problem and it is obvious that external offloading is the best solution. [email protected]
40 J. Salmerón-García et al. 5 3D Point Cloud (3DPC) Extraction Platform Using the architecture shown in Fig. 1, the offloading of stereo vision tasks has been implemented. As stereo cameras are the high level external sensors, the robot will send a stereo video stream (“Sensor Information” in Fig.1). The Cloud will extract all the necessary 3D information, sending that processed data (see Fig.1) back to the robot in the form of 3D Point Clouds (3DPC). The resulting architecture can be seen in Fig.2. These 3DPCs can be used by the robot to execute, for instance, a navigation algorithm (as explained in Sect.6.5) or a SLAM algorithm (together with the internal sensing). As mentioned in Sect.1, with respect to the precision of the extracted information, the bigger the image resolution is, the more accurate the reconstruction of the surrounding objects will be (extensively demonstrated in the literature [10,15]). The reason for choosing stereo cameras instead of other simpler sensors (such as those with infrared or ultrasonic technologies) is the completeness of the information they can offer, as well as they can serve for other high level visual tasks (like object detection and recognition, gesture recognition, etc.). 5.1 Software Implementation In order to convert the image stream sent by the robot to a set of point clouds, the best option is the Point Cloud Library (PCL, http://www.pointclouds.org) combined with the OpenCV Library (www.opencv.org). These large-scale, open source projects for 2D/3D point cloud processing and computer vision, are used by a ROS (Robotics Operating System) library called stereo_image_proc. This package offers a node that converts two stereo frames to a 3D Point Cloud. In order to do so, the node has an inner pipeline (using ROS nodelets) with several stages. Firstly, a monochrome version of the image is produced (debayer stage). Fig. 2 Block diagram of the 3DPC extraction platform [email protected]
Study of Communication Issues in Dynamically Scalable Cloud-Based Vision … 41 Secondly, using the stereo camera intrinsic matrices, a rectified version of the image is produced (rectify stage). With the rectified frames, the image matching occurs, obtaining a disparity map (disparity stage). Finally, with this information, the fourth and last step is the 3D point cloud construction (3DPC stage). Due to the very different processing times of the four steps, the minimum time for processing a frame pair will be the maximum of all step times (usually the disparity stage, which lasts most of the whole processing time). As it can be seen, the aforementioned process cannot be parallelized, as the steps need to be done in order. However, one of the objectives outlined in Sect.1is to have a dynamically scalable platform. In order to do so we have exploited the frame pair-level parallelism. Figure3depicts the parallel solution. The 3DPC extraction pipeline (stereo_image_proc) is replicated in several virtual instances in the cloud. Therefore, each stereo frame pair will be sent to a different virtual machine in a roundrobin fashion. This solution requires an intermediate front-end node, responsible of scattering the stereo stream between the available 3DPC extraction nodes. This way, should the need faster 3DPC extraction times, then more virtual instances could be spun up. However, some extra considerations must be taken into account in order to exploit the parallelism successfully. These considerations are thoroughly explained in Sect.6.3. Nevertheless, if we want our system to be dynamically scalable, then it must be able to adapt itself at runtime. Therefore, the buffer node must be able to know how many virtual instances are alive at any moment. This feature is implemented thanks Fig. 3 Stereo frame pipeline process. Four nodes process (in a pipeline fashion) the frame pairs that the front-end node delivers in a round-robin form. Tfis the robot’s stereo camera frequency, to is the time required to send the frame and tpis the time required to obtain the 3DPC (see Sect.5.2 for more information on the involved times). The time required to forward the frame from the buffer node to the 3DPC extractors, thanks to the Gigabit Ethernet connection, is negligible [email protected]
42 J. Salmerón-García et al. Fig. 4 Dynamic adaptation of the platform when the number of 3DPC extractors changes to ROS bond library. This library helps to establish a link between the intermediate buffer node and a 3DPC extractor. So, if one of the nodes of the link disappears, the other would be automatically notified. Figure4shows the different cases: •A new 3DPC Extractor is added at runtime: as soon as a 3DPC Extractor node is spun up, it will automatically contact the buffer node and establish a bond between them. The buffer node, with this new link added, will add this new node to the round-robin list. •One existing 3DPC Extractor is shut down: if this occurs, then the bond would be broken, and the buffer node would be immediately informed. Therefore, the round-robin list would be updated. When dealing with dynamically scalable solutions, another question arises: When should the platform launch more 3DPC extractors or shut down virtual instances? For vision processing applications a simple Quality-of-Service (QoS) magnitude can serve to determine these actions (with a previous agreement between the robot and the platform). For instance: if the robot has agreed a 3DPC reception frequency of 5Hz and the cloud is under-providing, then it can scale out to satisfy its demands. The same could be applied for over-providing. The user could change this QoS agreement at any time, and the platform would have to apply it accordingly. For more technical details of the platform, the code is available with GPL license in GitHub.1In addition to this, there are cloud images ready for deployment using the newest cloud technologies: Amazon EC2 virtual machines 2and Docker containers.3 1https://github.com/javsalgar/cloud_3dpc_extractor. 2The EC2 AMI is ami-893b11b9. 3https://registry.hub.docker.com/u/javsalgar/cloud_3dpc_extractor/. [email protected]
Study of Communication Issues in Dynamically Scalable Cloud-Based Vision … 49 Fig. 6 Empirical cumulative distribution frequency of delays with 5 and 10Hz to avoid collisions. Numerous questions arise, as in any real experiment: are really high quality stereo frames necessary to assist in the navigation?, are cloud solution more effective than the on-board one?, do packet latency variability suppose a problem when navigating? If on-board navigation were successful enough for 320 ×240 stereo frames (which have an adequate 3DPC frequency rate, see Table2), then Cloud offloading would not be necessary at all. In order to answer these questions, a testing circuit was prepared (see Fig.7). The Erratic robot was equipped with a stereo camera built from two PSEye cameras and the circuit was completed several times. The ratio of collisions by maneuvers was used as a success magnitude. The results obtained in Sects.6.3 show that most of the delays come from tc, that is, the time required to transfer the 3DPC back to the robot. Thus, we got rid of this communication overhead by moving the navigation assistant to the Cloud as well. Figure8shows the diagram of the resulting architecture. [email protected]
50 J. Salmerón-García et al. Fig. 7 Testing circuit used in the experiments Fig. 8 Overview of the platform applied to the navigation use case Thanks to this change in the offloading model, we obtained the following results, which solve most of previous questions. First of all, collisions were very frequent (about 50%) when using 320 ×240 images (for any computing option). Secondly, the number of collisions were considerably reduced (less than 10%) with higher resolutions (640 ×480 pixels) and using the Cloud. As a conclusion, for the stereo vision algorithm used here, low resolution images are not enough to detect the obstacle information properly, and hence using higher resolution images is justified. Moreover, images with more than 320 ×240 are more difficult for the Erratic robot to process on-board. A demonstration video can be found in [6] and all the details of the experiments and the navigation assistant can be seen in [19]. 7 Conclusions and Lessons Learned The implemented platform (and its experimental results) shows that the cloud-based offloading of heavy visual processing tasks is possible. Several conclusions can be extracted from the experience. [email protected]
Study of Communication Issues in Dynamically Scalable Cloud-Based Vision … 51 Firstly, the main bottleneck of cloud offloading is due to communication overheads. It is extremely important to mitigate this effect by choosing the correct network technology. Moreover, the non-real time middleware and the inherent non-deterministic of the TCP protocol (available in most Robotics Software Frameworks) introduce a high variability in timing latency. Thus, this drawback should be mitigated by using some kind of predictive correction terms in the loop controller and more deterministic middleware and networks. However, the results obtained by WiFi 11ac are promising, and in future years it may be able to provide bandwidths close to its theoretical 768 Mbps, which may reduce the collision problem that currently appears even for a reduced number of robots (as it has been outlined in Sect.6.4). Secondly, there is an inherent trade-off between computation offloading and communication overhead times. Therefore, the platform should be used finding the best balance between those two. In that sense, depending on the use case, it may be worth considering offloading not only the 3DPC extraction, but also other robotics tasks (just like the case shown in Sect.6.5). In addition to all this, it has also been demonstrated that if a Cloud Solution is not scalable, it is highly unlikely that good performance results can be achieved, and therefore impossible to meet real-time requirements. As it has been shown in Sect.6.1, this is an indispensable element to exploit the Cloud’s true potential. As a final conclusion, it can be assured that, despite there are challenges that need to be addressed, the main question has been answered: using the Cloud for offloading can imply better performance results in a robot than using on-board computation (at least for a typical robot, whose hardware is much limited). Acknowledgments The work shown in this chapter has been supported by the Spanish grant (with support from the European Regional Development Fund) BIOSENSE (TEC2012-37868- C04-02/01) and by Andalusian Regional Excellence Research Project grant (with support from the European Regional Development Fund) MINERVA (P12-TIC-1300). We wish to thank also Prof. D. Cascado for his interesting comments. References 1. Agostinho, L., Olivi, L., Feliciano, G., Paolieri, F., Rodrigues, D., Cardozo, E., Guimaraes, E.: A cloud computing environment for supporting networked robotics applications. In: 2011 IEEE Ninth International Conference on Dependable, Autonomic and Secure Computing (DASC), pp. 1110–1116 (2011). doi:10.1109/DASC.2011.181 2. Arumugam, R., Enti, V., Bingbing, L., Xiaojun, W., Baskaran, K., Kong, F.F., Kumar, A., Meng, K.D., Kit, G.W.: DAvinCi: a cloud computing framework for service robots. In: 2010 IEEE International Conference on Robotics and Automation (ICRA), pp. 3084–3089 (2010). doi:10. 1109/ROBOT.2010.5509469 3. Bistry, H., Zhang, J.: A cloud computing approach to complex robot vision tasks using smart camera systems. In: 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3195–3200 (2010). doi:10.1109/IROS.2010.5653660 4. Buyya, R., Vecchiola, C., Selvi, S.T.: Mastering Cloud Computing Foundations and Applications Programming. Morgan Kaufmann/Elsevier, Amsterdam (2013) [email protected]
52 J. Salmerón-García et al. 5. Charfi, E., Chaari, L., Kamoun, L.: PHY/MAC enhancements and QoS mechanisms for very high throughput WLANs: a survey. IEEE Commun. Surv. Tutor. 15(4), 1714–1735 (2013). doi:10.1109/SURV.2013.013013.00084 6. Cloud-based robot navigation assistant using stereo image processing. http://www.rtc.us.es/ cloud-based-robot-navigation-assistant-using-stereo-image-processing/ (2014). Accessed 12 Nov 2014 7. Furht, B., Escalante, A. (eds.): Handbook of Cloud Computing. Springer, New York (2010) 8. Gouveia, B.D., Portugal, D., Silva, D.C., Marques, L.: Computation sharing in distributed robotic systems: a case study on SLAM. IEEE Trans. Autom. Sci. Eng. (T-ASE) 12(2), 410– 422 (2015) 9. Guizzo, E.: Robots with their heads in the clouds. IEEE Spectr. 48(3), 16–18 (2011). doi:10. 1109/MSPEC.2011.5719709 10. Handa, A., Newcombe, R.A., Angeli, A., Davison, A.J.: Real-time camera tracking: when is high frame-rate best? In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds.) Computer Vision ECCV 2012. Lecture Notes in Computer Science, vol. 7578, pp. 222–235. Springer, Berlin (2012) 11. Hennessy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach. Morgan Kaufmann, Waltham (2012) 12. Iñigo-Blasco, P., Diaz-del Rio, F., Romero-Ternero, M.C., Cagigas-Muñiz, D., Vicente-Diaz, S.: Robotics software frameworks for multi-agent robotic systems development. Robot. Auton. Syst. 60(6), 803–821 (2012). doi:10.1016/j.robot.2012.02.004.http://www.sciencedirect.com/ science/article/pii/S0921889012000322 13. Iñigo-Blasco, P., Diaz-del Rio, F., Vicente-Diaz, S., Cagigas-Muñiz, D.: The shared control dynamic window approach for non-holonomic semi-autonomous robots. In: Proceedings of 41st International Symposium on Robotics. ISR/Robotik 2014. Munich (2014) 14. John, B.P.: Effectiveness of SPEC CPU2006 and Multimedia Applications on Intel’s Single. Dual and Quad Core Processors. ProQuest (2009) 15. Kytö, M., Nuutinen, M., Pirkko, O.: Method for measuring stereo camera depth accuracy based on stereoscopic vision. In: Proceedings of SPIE/IS&T Electronic Imaging 2011 (2011) 16. Nimmagadda, Y., Kumar, K., Lu, Y.H., Lee, C.S.G.: Real-time moving object recognition and tracking using computation offloading. In: 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2449–2455 (2010). doi:10.1109/IROBlS.2010. 5650303 17. Quigley, M., Conley, K., Gerkey, B., Faust, J., Foote, T., Leibs, J., Wheeler, R., Ng, A.: ROS: an open-source robot operating system (2009) 18. Riazuelo, L., Civera, J., Montiel, J.M.M.: C2tam: a cloud framework for cooperative tracking and mapping. Robot. Auton. Syst. 62(4), 401–413 (2014). doi:10.1016/j.robot.2013.11.007 19. Salmeron-Garcia, J., Iñigo Blasco, P., Diaz-del Rio, F., Cagigas-Muniz, D.: A trade-off analysis of a cloud-based robot navigation assistant using stereo image processing. IEEE Trans. Autom. Sci. Eng. (T-ASE) 12(2), 444–454 (2015) 20. Srinivasan, S.: Cloud Computing Basics. Springer Briefs in Electrical and Computer Engineering. Springer, New York (2014) 21. Stallings, W.: Data and Computer Communications. Always Learning, 10th edn. Pearson, Boston (2014) 22. Szeliski, R.: Computer Vision Algorithms and Applications. Texts in Computer Science. Springer, London (2011) 23. Waibel, M., Beetz, M., Civera, J., D’Andrea, R., Elfring, J., Galvez-Lopez, D., Haussermann, K., Janssen, R., Montiel, J.M.M., Perzylo, A., Schiessle, B., Tenorth, M., Zweigle, O., van de Molengraft, R.: RoboEarth. IEEE Robot. Autom. Mag. 18(2), 69–82 (2011). doi:10.1109/ MRA.2011.941632 24. Wu, H., Lou, L., Chen, C.C., Hirche, S., Kuhnlenz, K.: Cloud-based networked visual servo control. IEEE Trans. Ind. Electron. 60(2), 554–566 (2013). doi:10.1109/TIE.2012.2186775 [email protected]
Appendix C A Tradeoff Analysis of a Cloud-Based Robot Navigation Assistant Using Stereo Image Processing Authors •Javier J. Salmerón García •Pablo Íñigo Blasco •Fernando Díaz del Río •Daniel Cagigas Muñiz Publication Title: IEEE Transactions on Automation Science and Engineering. Type: Journal Article. Issue: 99 Publisher: IEEE. Date: 2015. Pages: 1-11. ISSN: 1545-5955. 73
APRIL 2015 VOLUME 12 NUMBER 2 ITASC7 (ISSN 1545-5955) SPECIAL SECTION ON CLOUD ROBOTICS AND AUTOMATION Editorial: Multiplicity Has More Potential Than Singularity ..................................................... K.Goldberg 395 Guest Editorial: Cloud Robotics and Automation .......... J. Civera, M. Ciocarlie, A. Aydemir, K. Bekris, and S. Sarma 396 SPECIAL SECTION PAPERS A Survey of Research on Cloud Robotics and Automation ................ B.Kehoe,S.Patil,P.Abbeel,andK.Goldberg 398 Computation Sharing in Distributed Robotic Systems: A Case Study on SLAM ............................................. .................................................................... B.D. Gouveia,D. Portugal, D. C. Silva, and L. Marques 410 Cloud-Based Collaborative 3D Mapping in Real-Time With Low-Cost Robots .............................................. ........................................................G.Mohanarajah,V.Usenko,M. Singh,R.D’Andrea, andM.Waibel 423 RoboEarth Semantic Mapping: A Cloud Enabled Knowledge-Based Approach .............................................. ..........................................................................................L. Riazuelo,M.Tenorth,D.Di Marco, M. Salas, D. Gálvez-López, L. Mösenlechner, L. Kunze, M. Beetz, J. D. Tardós, L. Montano, and J. M. M. Montiel 432 A Tradeoff Analysis of a Cloud-Based Robot Navigation Assistant Using Stereo Image Processing ....................... ............................................. J.Salmerón-Garc´ıa, P. Íñigo-Blasco, F. D´ıaz-del-R´ıo, and D. Cagigas-Muñiz 444 Cloud-Based Grasp Analysis and Planning for Toleranced Parts Using Parallelized Monte Carlo Sampling ............... ............................................................................... B.Kehoe, D.Warrier, S. Patil, and K. Goldberg 455 Dynamic Collaboration Between Networked Robots and Clouds in Resource-Constrained Environments ................. ................................................................................................. P. Pandey,D. Pompili,andJ.Yi 471 Rapyuta: A Cloud Robotics Platform......................... G. Mohanarajah, D. Hunziker, R. D’Andrea, and M. Waibel 481 Inside the Virtual Robotics Challenge: Simulating Real-Time Robotic Disaster Response................................... ............................................................................................... C. E.Agüero, N.Koenig,I.Chen, H. Boyer, S. Peters, J. Hsu, B. Gerkey, S. Paepcke, J. L. Rivero, J. Manzo, E. Krotkov, and G. Pratt 494 Real-Time Multisensor Data Retrieval for Cloud Robotic Systems ................. L.Wang,M.Liu,and M.Q.-H.Meng 507 On Distributed Knowledge Bases for Robotized Small-Batch Assembly ...................................................... ........................................................................ M. Stenmark, J. Malec, K. Nilsson, and A. Robertsson 519 (Contents Continued on Page 393)
(Contents Continued from Front Cover) REGULAR ISSUE PAPERS On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages .... ..................................................................................... O. Salzman,M. Hemmer,andD. Halperin 529 Estimating Clearing Functions for Production Resources Using Simulation Optimization ...... N. B. Kacar and R. Uzsoy 539 Automatic Bird Species Filtering Using a Multimodel Approach .........................................W.LiandD.Song 553 Model Predictive Control of Central Chiller Plant With Thermal Energy Storage Via Dynamic Programming and Mixed-Integer Linear Programming ............................................................................................ .................................. K.Deng,Y.Sun,S.Li,Y.Lu, J.Brouwer,P.G.Mehta,M.C.Zhou,andA.Chakraborty 565 Stochastic Cost-Profit Tradeoff Model for Locating an Automotive Service Enterprise ...................................... .............................................................................G.Tian, M. C.Zhou,J. Chu,T. Qiang,andH. Hu 580 Towards Occlusion-Free Surgical Instrument Tracking: A Modular Monocular Approach and an Agile Calibration Method .................................................................................. J. Wang, M. Q.-H.Meng, andH.Ren 588 Automatic Color Inspection for Colored Wires in Electric Cables .............. S. Ghidoni, M. Finotto, and E. Menegatti 596 Using Manipulation Primitives for Object Sorting in Cluttered Environments ................................................ ....................................................................................... M.Gupta, J.Müller, andG.S. Sukhatme 608 The Influence of Motion Paths and Assembly Sequences on the Stability of Assemblies ........ S. Rakshit and S. Akella 615 A Dynamic Algorithm for Distributed Feedback Control for Manufacturing Production, Capacity, and Maintenance .... .......................................................................................................... S. Leeand V. V.Prabhu 628 Controlled Wafer Release in Clustered Photolithography Tools: Flexible Flow Line Job Release Scheduling and an LMOLP Heuristic ................................................................................ K.Park andJ. R. Morrison 642 Supply Demand Coordination for Building Energy Saving: Explore the Soft Comfort ...... Z. Xu, Q.-S. Jia, and X. Guan 656 Simultaneous Identification of Bidirectional Path Models Based on Process Data ............................................ ..................................................................................... B.Jiang,F.Yang,W.Wang,andD.Huang 666 Automatic Composition of Semantic Web Services Based on Fuzzy Predicate Petri Nets ................................... .....................................................................J.Cheng,C.Liu,M. C Zhou, Q.Zeng,andA. Ylä-Jääski 680 Noncyclic Scheduling of Cluster Tools With a Branch and Bound Algorithm ........ H.-J.Kim,J.-H.Lee,andT.-E.Lee 690 Real-Time Production Scheduler for Digital-Print-Service Providers Based on a Dynamic Incremental Evolutionary Algorithm .............................................................. Q.Duan,J.Zeng, K. Chakrabarty, andG.Dispoto 701 Approximate Life Cycle Assessment via Case-Based Reasoning for Eco-Design ............................................ ................................................................................... M.-G. Jeong, J.R. Morrison, andH.-W. Suh 716 Topological Indoor Localization and Navigation for Autonomous Mobile Robot ......... H. Cheng, H. Chen, and Y. Liu 729 Robot Guided Crowd Evacuation ............................E. Boukas,I.Kostavelis,A.Gasteratos,and G. Ch.Sirakoulis 739 REGULAR ISSUE SHORT PAPERS Backstepping Control for Gear Transmission Servo Systems With Backlash Nonlinearity ...............Z. Shi andZ.Zuo 752 A Minimal POE-Based Model for Robotic Kinematic Calibration With Only Position Measurements ..................... ........................................................................................... L.Wu,X.Yang,K. Chen,and H.Ren 758 Cellular Production Lines With Asymptotically Reliable Bernoulli Machines: Lead Time Analysis and Control ......... .................................................................................................... S.M. MeerkovandC.-B.Yan764 Toward Welding Robot With Human Knowledge: A Remotely-Controlled Approach ................ Y.Liu andY.Zhang 769 Robotic Handling of Surgical Instruments in a Cluttered Tray .................................................................. ................................................ Y. Xu,Y.Mao,X.Tong,H.Tan,W.B.Griffin, B. Kannan, and L. A. DeRose 775
444 IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, VOL. 12, NO. 2, APRIL 2015 A Tradeoff Analysis of a Cloud-Based Robot Navigation Assistant Using Stereo Image Processing Javier Salmerón-Garc´ ıa, Pablo Íñigo-Blasco, Fernando D´ ıaz-del-R´ ıo, and Daniel Cagigas-Muñiz Abstract—The use of Cloud Computing for computation offloading in the robotics area has become a field of interest today. The aim of this work is to demonstrate the viability of cloud offloading in a low level and intensive computing task: a vision-based navigation assistance of a service mobile robot. In order to do so, a prototype, running over a ROS-based mobile robot (Erratic by Videre Design LLC) is presented. The information extracted from on-board stereo cameras will be used by a private cloud platform consisting of five bare-metal nodes with AMD Phenom 965 4 CPU, with the cloud middleware Openstack Havana. The actual task is the shared control of the robot teleoperation, that is, the smooth filtering of the teleoperated commands with the detected obstacles to prevent collisions. All the possible offloading models for this case are presented and analyzed. Several performance results using different communication technologies and offloading models are explained as well. In addition to this, a real navigation case in a domestic circuit was done. The tests demonstrate that offloading computation to the Cloud improves the performance and navigation results with respect to the case where all processing is done by the robot. Note to Practitioners—Cloud computing for robotics is very promising for several reasons, like robot's energy saving, larger storage capacity, stable electric power, better resource utilization and the difficulty of upgrading the robots' embedded hardware. The presented application extracts 3D point clouds from the stereo image pairs of a camera situated on the robot. Using these 3D points, a shared control is implemented to help the remote teleoperation of a robot. That is, the commands sent by a joystick are attenuated when a possible collision is detected (by checking the future commanded trajectory against the 3D points). All of these computationally heavy tasks (difficult to perform by a mobile robot) are done in the cloud. The offloading models proposed in this paper are generic enough to be used in other applications. Obtained results show that further improvement in communication technologies will suppose a significant performance boost for offloading computation. Index Terms—Cloud offloading, cloud robotics, image point cloud, mobile robots, navigation assistance, shared control. Manuscript received November 12, 2014; accepted January 21, 2015. Date of publication March 02, 2015; date of current version April 03, 2015. This paper was recommended for publication by Associate Editor J. Civera and Editor S. Sarma upon evaluation of the reviewers' comments. This work was supported by the European Regional Development Fund under Spanish Grant BIOSENSE TEC2012-37868-C04-02/01. J. Salmerón-Garca, P. Iñigo-Blasco, and F. D´ ıaz-del-R´ ıo are with the Robotics and Computer Technology Laboratory, University of Seville, Seville 41012, Spain (e-mail: [email protected]; pabloin[email protected]; fd[email protected]s). D. Cagigas-Muñoz is with the Department of Computer Architecture and Technology, University of Seville, Seville 41012, Spain (e-mail: dcagigas@us. es). Digital Object Identifier 10.1109/TASE.2015.2403593 I. INTRODUCTION CLOUD computing is an emerging technology for robotics, especially for mobile service robots. The needs come from the huge amount of information that a service robot has to process in order to interact and interpret the environment correctly. For this reason, during the last few years, an important number of research papers and projects are addressing the use of cloud infrastructures in robotics [1]–[4]. Research fields where clouds are of interest are those where computation is very intensive. But, where and how can high computing tasks be identified in mobile robots? According to [5], a robot usually has a layered architecture. Layers in the top level of the hierarchy can contain processes that, for example, perform cognitive tasks similar to humans. In the middle layers, tasks also involve complex processes like path planning, object handling, speech recognition, etc. Finally, in the lowest levels reactive and real-time control operations are performed (e.g., obstacle avoidance, guidance, beacon detection, signal communications processing, etc). The amount of computation is not necessarily proportional to the level. For instance, in [6], it is pointed out that an intelligent mobile robot in an office-like environment can be modeled by the Soar cognitive architecture with only a few milliseconds of computational cost. However, other middle and low-level tasks that feed higher layers in a robot architecture, can be very computing demanding. The main example is that of artificial vision and higher level tasks arising from it, such as object detection, recognition and tracking, surveillance, gesture recognition, etc. Another very promising field is that related to multi-robot cooperation at different levels, where new cooperative algorithms are being developed like multirobot simultaneous localization and mapping (SLAM) [7], map merging (acquired by several robots), networked information repository for robots [8], amongst others. The main properties that make cloud infrastructures compelling are the following: high reliability, larger storage capacity, stable electric power, reutilization of hardware, dynamic scalability and better resource utilization. In particular, the dynamic scalability property (adaptation of the computing power at runtime) is extremely useful in Robotics, because it allows the almost instant incorporation of new computation demanding algorithms as soon as they are implemented. Besides, the term “Cloud Robotics” has emerged to include this area, which promises fast development of complex distributed robotics tasks in the forthcoming years. Consequently, the use of cloud computing is expected to be widespread in the next few years in the service and rehabilitation robotics field. Its use can offer them additional advantages, 1545-5955 © 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
SALMERÓN-GARC´ IA et al.: TRADEOFF ANALYSIS OF A CLOUD-BASED ROBOT NAVIGATION ASSISTANT 445 such as: supplementing local information collected by the robot with that coming from Intelligent Environments, Ambient Assisted Living applications like monitoring user's health and daily activities, multirobot cooperation and so on. In this respect, it must be noticed that images captured by on-board cameras are to be required by higher robotics levels (like object detection and recognition, gesture recognition, etc., which must run in the cloud), or by a human teleoperator that must make a decision over the robotics system or simply teleoperate the robot itself. Therefore, these images will be transmitted to the cloud in any case, and these transfers would not be a burden for the whole system. Navigation assistance and human-computer shared control, are common application cases for intelligent wheelchairs. Many wheelchairs incorporate high-ended sensors, like stereo cameras, laser rangers, and Ambient Intelligence aids [9] to address this question. However, despite great advancements in power wheelchair technology, research shows that wheelchair related accidents occur frequently, especially for users with considerable handicaps [10]. Daily wheelchair maneuvers could be challenging due to the users' pathologies, poor maneuvering skills, user's fatigue, and unknown or adverse environments. Therefore, a safe maneuverability of a wheelchair using on-board or external high-ended sensors has great importance in this kind of situations. Moreover, remote teleoperation of the wheelchair by an external caregiver could be sometimes necessary. In addition to this, the results obtained in our Lab research in advanced wheelchairs control [11], [12] support the necessity of navigation assistance in certain situations. Because of the probable omnipresence of cloud infrastructures for service robots, in this work a prototype is implemented as a first step to analyze and demonstrate the viability of carrying out in a cloud the lower (but intensive computing) levels of a mobile robot navigation assistant. The presented prototype is running over a Robotic Operating System (ROS)-based mobile robot (Erratic by Videre Design LLC) due to its software deploying and debugging ease. However, this idea will be applied to other devices like intelligent wheelchairs or other mobile service robots, extending our previous research. More precisely, the task consists of the teleoperation by a local or remote (which has little influence because the inherent distributed architecture of the developed system) user, who is helped by using the sensing information extracted from an on-board (but processed in a cloud infrastructure) stereo camera. In order to exploit the cloud capabilities, a dynamic parallel algorithm has been implemented, so the solution is able to scale out and back. Hence, the robot gets the results faster when more computation power is required. The Computation offloading of a robotics task includes several tradeoffs. The software architecture (and its components) of a complex robotic system must cater for a variety of characteristics, distinguish it from other systems. The most relevant are [13]: concurrent and distributed architecture, modularity (several components of high cohesion but low coupling), robustness and fault tolerance, and real-time efficiency. The first two characteristics primarily benefit from cloud offloading, while the third introduces new challenges (network robustness and fault tolerance appear as a new aspect to considerate). Nevertheless, the main issue that offloading must address for a navigation task is the fourth of them. In this respect, a short quantitative comparison of times involved in local versus remote computing follows. This demonstrates the theoretical real-time viability of cloud offloading and it points out new considerations. The first mandatory bound is the time spent in data transmission to the cloud. If the bandwidth rate of communication technology is , and data size to be transmitted and received is , it is concluded that must be inferior to the deadline of the task. Nowadays, there are wireless networks whose bandwidths [14] are approaching to 1 Gbps, with a steady incremental ratio of more than 40% per year, or two times every two years (see http://www.wi-fi.org/). For a typical navigation control loop, frequencies around 20 Hz (period s) are usually enough. This gives us a limit of 0.05 Gbits, or equivalently, a 3 Mpixel raw stereo image, per period. Therefore, offloading computing is feasible, which, indeed, has the aforementioned benefits. A secondary aim is that cloud accelerates timing execution. Let us suppose that the robot computer can execute at a rate of instructions per second (millions of or is a common magnitude in computer architecture [15]), and that the cloud can speedup an application times more that this . Therefore, local and remote execution times for computer instructions could be expressed as For stereo vision applications, is very big because the cloud is supposed to have far more computational resources than the local computer, and many operations are performed in parallel. Being that the case, timing comparison gets to a short formula, which indicates whether computation offloading is faster than local execution, that is, ,if The first term of this inequality is entirely dependent on each application. This means that high intensive computing tasks benefit from cloud computing. With respect to image processing, many of the filters that extract features used in point cloud processing have computational complexity orders higher than ,being thenumberofpixels.Forexample, in our experiments, a frame pair is computed by the Erratic in s (see Section V). As the Erratic CPU (Intel Celeron-M) runs at a frequency of GHz and has a Clocks per Instruction (CPI) around 2.0 [16], then, the number of instructions is [15] Besides, transmitted data in this experiment (see Section V) mainly consists of a color 1024 768 frame pair, that is: bits. Hence On the contrary, the second member of the inequality is mainly technology dependent. Nowadays, is [15], so for the Erratic CPU, it rounds instr/s. Therefore, networking bandwidth is crucial to have success in the offloading. Using WiFi IEEE 802.11ac, 400 Mbps data rate
452 IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, VOL. 12, NO. 2, APRIL 2015 TABLE IV AVERAGE DELAYS OF THE SYSTEM FOR 1024 768 FRAMES AND DIFFERENT OFFLOADING MODELS USING 802.11AC WIFI Fig. 7. Histogram of 1024 768 frames using option 1 and 802.11ac WiFi. communication overheads in exchange of higher frequency of the whole system. The second test measures the latencies of the whole application, that is, the difference between the time the stereo frame pair was taken and the time was calculated for them. Table IV shows that the main cause of delays in the system are again the communication overheads. Thus, an offloading model that minimizes them is benefited. The robot on its own is unable to get acceptable latencies; this time due to the heavy computation. With these two tests, it is certain that option 1 is the best offloading model for this case, obtaining decent results even with wireless technologies. Finally, as communication latencies cannot be constant, it is interesting to show a histogram for (inFig.7,1024 768 stereo frame pairs were used for option 1 and Wifi AC). Although variance is not very big, some messages (only a 2%) present a high variability of the latency. This is due to four main factors: 1) the ROS middleware used; 2) complexity of 3DPC filters; 3) TCP protocols; and 4) interferences, and packet rejection with backoff periods in MAC layer. As percentage of late packet is very low, a simple predictive timing correction algorithm (see Section III) mitigates possible oscillations in the control loop. Besides, further improvements in 802.11ac MAC layer like time-division multiple-access (TDMA) protocols, would reduce substantially this latency variance. An alternative to TDMA protocols is the use of the Contention Free Period in the infrastructure mode with fixed size packets. This could not reduce the variability as much as the use of TDMA, but it guarantees a minimum bandwidth reservation, which may be suitable for many real-time systems. C. Analysis of a Real Navigation Case Two final tests show that cloud-based robot navigation (option 1) is possible and even can improve its on-board counterpart. The vehicle has been configured with: m/s, rad/s, maximum linear acceleration Fig. 8. Example of (in meters). Fig. 9. Response of the navigation assistant to joystick commands. TABLE V NAVIGATION RESULTS FOR TEST 2USING OPTIONS 1, 4, AND TWO FRAME RESOLUTIONS.THE RATIO ISCALCULATED OVER 70 MANEUVERS , maximum linear brake m/s .Circuitof the first test contains obstacle free areas (where the robot is able to move at maximum speed) and four walls, where the robot should stop to prevent a collision. Figs. 8 and 9 demonstrate the viability of option 1. Fig. 8 shows when approaching one of these walls. Fig. 9 shows the difference between the joystick linear velocity and the final computed linear speed command when completing a turn of the circuit. The second test compares the navigation of the robot in an office environment for options 1 and 4, and for low and medium resolutions (320 240 and 640 480 pixels) at 10 fps. The circuit is completed ten times per case. The number of collisions are measured as a quality magnitude, because, due to the delay variances in the navigation assistant computation, some collisions are difficult to avoid. For each obstacle approaching maneuver, the joystick is pushed to its extreme positions (desired commands are always those of maximum speeds), in order to test the shared control in the worst conditions. As there are seven of these maneuvers for each turn of the circuit, we have a total of 70 possible collisions. Table V shows the number and ratio of collisions for the four tested alternatives. The first conclusion is that for the stereo algorithm used here, low resolutions are not enough to detect properly some of the walls (when the robot is in movement), and collisions are very frequent for any computing option. The second important conclusion is obtained
SALMERÓN-GARC´ IA et al.: TRADEOFF ANALYSIS OF A CLOUD-BASED ROBOT NAVIGATION ASSISTANT 453 for the 640 480 pixel resolution. Collision rate is very much reduced when the cloud is working, which is mainly explained because frame processing frequencies are more than double for option 1 than for 4 (see Table III). In this case, the only collisions are produced against an metallic furniture which texture is very much homogeneous. Another additional trouble is the limited FOV of the camera. This means that unavoidable collisions are produced when robot makes brusque turns (this must be solved by the inclusion of more cameras in the future). A demonstration video can be found in [34]. VI. CONCLUSION This work analyzes and shows that running a vision based navigation assistant completely on an external cloud is feasible. Two main evidences allow this: a) cloud scalability is pretty well achieved and b) processing times run in parallel tothetransmission ones, being the latter the bottleneck of the cloud offloading. In fact, the mean processing frequencies are almost proportional to bandwidth network. It is expected that the extension and natural evolution of wireless networks would improve their bandwidth in the next few years. Experiments demonstrate that the proper computation offloading model must be carefully chosen. In that sense, the computation versus communication tradeoff has to be analyzed. Moreover, the key to success in computation offloading is the scalability of the developed solutions. Finally, the implemented prototype (a teleoperated mobile robot using shared control) can be useful for the teleoperation of wheelchairs of other service robots, which can be done by the user or by an external caregiver. As a better navigation is obtained when using higher resolution images, the necessity of the cloud has been empirically demonstrated. It is also shown that the navigation assistant must contemplate a predictive temporal correction that should prevent a possible collision, caused by the sensoring delay, mainly due to the transmission latencies. ACKNOWLEDGMENT The authors wish to thank Prof. D. Cascado for his interesting comments. In addition to this, they really wish to thank the reviewers for all the feedback of our work, together with all the recommendations for future work. REFERENCES [1] D. Hunziker, M. Gajamohan, M. Waibel, and R. D'Andrea, “Rapyuta: The RoboEarth cloud engine,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), May 2013, pp. 438–444. [2] E. Guizzo, “Robots with their heads in the clouds,” IEEE Spectrum, vol. 48, no. 3, pp. 16–18, Mar. 2011. [3] R. Arumugam, V. Enti, L. Bingbing, W. Xiaojun, K. Baskaran, F. F. Kong,A.Kumar,K.D.Meng,andG.W.Kit,“DAvinCi:Acloudcomputing framework for service robots,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), May 2010, pp. 3084–3089. [4] B. Kehoe, S. Patil, P. Abbeel, and K. Goldberg, “A survey of research on cloud robotics and automation,” IEEE Trans. Autom. Sci. Eng. (T-ASE), vol. 12, no. 2, pp. 398–409, Apr. 2015. [5] Springer Handbook of Robotics, B. Siciliano and O. Khatib, Eds. Berlin, Germany: Springer-Verlag, 2008. [6] J. Laird, The Soar Cognitive Architecture. Cambridge, MA, USA: MIT Press, 2012. [7] B. D. Gouveia, D. Portugal, D. C. Silva, and L. Marques, “Computation sharing in distributed robotic systems: A case study on SLAM,” IEEE Trans. Autom. Sci. Eng. (T-ASE), vol. 12, no. 2, pp. 410–422, Apr. 2015. [8] M. Waibel, M. Beetz, J. Civera, R. D'Andrea, J. Elfring, D. Galvez-Lopez, K. Haussermann, R. Janssen, J. M. M. Montiel, A. Perzylo, B. Schiessle, M. Tenorth, O. Zweigle, and R. van de Molengraft, “RoboEarth,” IEEE Robot. Autom. Mag., vol. 18, no. 2, pp. 69–82, Jun. 2011. [9] J. Sevillano, D. Cascado, D. Cagigas, S. Vicente, C. Lujan, and F. del Rio, “A real-time wireless sensor network for wheelchair navigation,” in Proc. IEEE/ACS Int. Conf. Comput. Syst. Appl. (AICCSA), May 2009, pp. 103–108. [10] J.Fu,W.Hao,T.White,Y.Yan,M.Jones,andY.-K.Jan,“Capturing and analyzing wheelchair maneuvering patterns with mobile cloud computing,” in Proc. 35th Annu. Int. Conf. IEEE Eng. Med. Bio. Soc. (EMBC), Jul. 2013, pp. 2419–2422. [11] A. Civit-Balcells, F. Diaz Del Rio, G. Jimenez, J. Sevillano, C. Amaya, and S. Vicente, “SIRIUS: Improving the maneuverability of powered wheelchairs,” in Proc. Int. Conf. Control Appl., 2002, vol. 2, pp. 790–795. [12] S. V. Diaz, C. A. Rodriguez, F. Diaz del Rio, A. C. Balcells, and D. C. Muniz, “TetraNauta: A intelligent wheelchair for users with very severe mobility restrictions,” in Proc. Int. Conf. Control Appl., 2002, vol. 2, pp. 778–783. [13] P. I. Blasco, F. Diaz-del Rio, M. C. Romero-Ternero, D. Cagigas-Muiz, and S. Vicente-Diaz, “Robotics software frameworks for multi-agent robotic systems development,” Robot. Auton. Syst., vol. 60, no. 6, pp. 803–821, Jun. 2012. [14] E. Charfi, L. Chaari, and L. Kamoun, “PHY/MAC enhancements and QoS mechanisms for very high throughput WLANs: A survey,” IEEE Commun. Surveys Tutorials, vol. 15, no. 4, pp. 1714–1735, 2013. [15] J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach. Waltham, MA, USA: Morgan Kaufmann, 2012. [16] B. P. John, Effectiveness of SPEC CPU2006 and Multimedia Applications on Intel's Single, Dual and Quad Core Processors. Ann Arbor, MI, USA: ProQuest, 2009. [17] M. Tenorth, A. Perzylo, R. Lafrenz, and M. Beetz, “The RoboEarth language: Representing and exchanging knowledge about actions, objects, and environments,” in Proc. IEEE Int. Conf. Robot. Autom. (ICRA), May 2012, pp. 1284–1289. [18] M. Tenorth, A. Perzylo, R. Lafrenz, and M. Beetz, “Representation and exchange of knowledge about actions, objects, and environments in the RoboEarth framework,” IEEE Trans. Autom. Sci. Eng., vol. 10, no. 3, pp. 643–651, Jul. 2013. [19] M. Tenorth, K. Kamei, S. Satake, T. Miyashita, and N. Hagita, “Building knowledge-enabled cloud robotics applications using the ubiquitous network robot platform,” in Proc. IEEE/RSJ Int. Conf. Intell. Robot. Syst. (IROS), Nov. 2013, pp. 5716–5721. [20] L. Wang, M. Liu, and M. Meng, “Real-time multi-sensor data retrieval for cloud robotic systems,” IEEE Trans. Autom. Sci. Eng. (T-ASE), vol. 12, no. 2, pp. 507–518, Apr. 2015. [21] H. M. Do, C. J. Mouser, Y. Gu, W. Sheng, S. Honarvar, and T. Chen, “An open platform telepresence robot with natural human interface,” in Proc. IEEE 3rd Annu. Int. Conf. Cyber Technol. Autom., Control, Intell. Syst. (CYBER), Nanjing, China, May 2013, pp. 81–86. [22] K. Ayush and N. K. Agarwal, “Real time visual SLAM using cloud computing,” in Proc. 4th Int. Conf. Comput., Commun. Netw. Technol. (ICCCNT), Tiruchengode, India, Jul. 2013, pp. 1–7. [23] L. Riazuelo, J. Civera, and J. M. M. Montiel, “C2tam: A cloud framework for cooperative tracking and mapping,” Robot. Auton. Syst., vol. 62, no. 4, pp. 401–413, Apr. 2014. [24] H. Bistry and J. Zhang, “A cloud computing approach to complex robot vision tasks using smart camera systems,” in Proc. IEEE/RSJ Int. Conf. Intell. Robot. Syst. (IROS), Oct. 2010, pp. 3195–3200. [25] Y. Nimmagadda, K. Kumar, Y.-H. Lu, and C. S. G. Lee, “Real-time moving object recognition and tracking using computation offloading,” in Proc. EEE/RSJ Int. Conf. Intell. Robot. Syst. (IROS), Oct. 2010, pp. 2449–2455. [26] H.Wu,L.Lou,C.-C.Chen,S.Hirche, and K. Kuhnlenz, “Cloud-based networked visual servo control,” IEEE Trans. Ind. Electron., vol. 60, no. 2, pp. 554–566, Feb. 2013. [27] L. Agostinho, L. Olivi, G. Feliciano, F. Paolieri, D. Rodrigues, E. Cardozo, and E. Guimaraes, “A cloud computing environment for supporting networked robotics applications,” in Proc. IEEE 9th Int. Conf. Dependable, Auton. Secure Comput. (DASC), Dec. 2011, pp. 1110–1116. [28] J. Salmerón-Garc´ ıa, P. I. Blasco, F. Diaz-del Rio, and D. Cagigas- Muñiz, “Mobile robot motion planning based on cloud computing stereo vision processing,” in Proc. 41st Int. Symp. Robot. (ISR/Robotik), Jun. 2014, pp. 1–6.
454 IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, VOL. 12, NO. 2, APRIL 2015 [29] P. I. Blasco, F. Diaz-del Rio, S. Vicente-Diaz, and D. Cagigas-Muńiz, “The shared control dynamic window approach for non-holo- nomic semi-autonomous robots,” in Proc. 41st Int. Symp. Robot. (ISR/Robotik), Munich, Germany, Jun. 2014, pp. 1–6. [30] P. Nisbet, “Who's intelligent? Wheelchair, driver or both?,” in Proc. Int. Conf. Control Appl., Sep. 2002, vol. 2, pp. 760–765. [31] A.To,G.Paul,andD.Liu,“Surface-type classification using RGB-d,” IEEE Trans. Autom. Sci. Eng., to be published. [32] M. Kytö;, M. Nuutinen, and O. Pirkko, “Method for measuring stereo camera depth accuracy based on stereoscopic vision,” in Proc. SPIE/ IS&T Electron. Imag., 2011, pp. 1–9. [33] A. Handa, R. A. Newcombe, A. Angeli, and A. J. Davison, “Real-time camera tracking: When is high frame-rate best?,” in Computer Vision ECCV 2012, ser. Lecture Notes in Computer Science, A. Fitzgibbon, S. Lazebnik, P. Perona, Y. Sato, and C. Schmid, Eds. Berlin, Germany: Springer-Verlag, Jan. 2012, pp. 222–235, no. 7578. [34] “Cloud-based robot navigation assistant using stereo image processing,” (accessed Nov. 12, 2014.) [Online]. Available: http://www.rtc.us.es/cloud-based-robot-navigation-assistant-using- stereo-image-processing/ Javier Salmerón-Garc´ıa received the B.Sc. degree in computer engineering and the M.Sc. degree in computer engineering and networks from the University of Seville, Seville, Spain, in 2011 and 2012, respectively, and the M.Sc. degree in software engineering for technical computing from Cranfield University, Cranfield, U.K., in 2011. Currently, he is working towards the Ph.D. degree focusingoncloud robotics at the University of Seville. His main area of expertise is cloud computing appliedtobothHPCandrobotics.Moreo ver, he works as a part-time Lecturer at the University of Seville. Pablo Iñigo Blasco received the Degree in computer engineering degree and the M.S. degree in software engineering and technology from the University of Seville, Seville, Spain, in 2008 and 2010, respectively. Currently, he is working towards the Ph.D. degree at the University of Seville, where his research work is focused on parallel computing on mobile robots navigation and obstacle avoidance andalsoonroboticsof tware architectures. Forfouryearsheworke d for the Spanish Research Council (CSIC) as a Software Architect. In 2010, he joined the Department of Computer Architecture and Technology as a Lecturer. He also became a member of the Robotics and Computer Technology for Rehabilitation Laboratory, where he participated in a couple of national research projects related to mobile robot navigation. Fernando D´ıaz-del-R´ıo received the M.S. degree in physics (electronics) and the Ph.D. degree from the University of Seville, Seville, Spain, in 1990 and 1997, respectively. After working for Abengoa-Control-Data and for the University of Huelva for some time, he joined the Department of Computer Architecture, University of Seville, and has been an Associate Professor since 2000. He has served as Vice-Dean of the Computer Engineering School (2007–2010). He is author/coauthor of more than 40 papers in refereed international journals and conferences, most of them in the field of mobile robot navigation. Mobile robot navigation, bioinspired systems and distributed computing systems are his main research topics. He has participated in more than 20 research projects and contracts (between them, in EU projects FLEX and CAVIAR). Daniel Cagigas received the Degree in computer science and the Ph.D. degree from the University of the Bask Country, Bilbao, Spain, in 1997 and 2001, respectively. Since 2001, he has been working full-time as a Lecturer in the Department of Computer Architecture and Technology, and a Researcher with the Robotics and Computer Technology for Rehabilitation Lab, University of Seville (Spain). His main research interests include robotics, embedded systems and artificial intelligence applied to rehabilitation technologies. He has participated in more than ten national and international research projects and contracts, including EU projects CAVIAR and CARDIAC. He is author of over 20 publications in international journals and conferences in the field of mobile robot navigation and user interface design.
Appendix D Extending Amdahl’s Law For the Cloud Computing Era Authors •Fernando Díaz del Río •Javier J. Salmerón García •José Luis Sevillano Ramos Publication Title: IEEE Computer. Type: Journal Article. Publisher: IEEE. Date: Not published yet. ISSN: 0018-9162. 87
Page 1 Extending Amdahl's Law For the Cloud Computing Era A BSTRACT This is the era of Cloud Computing. A gradual change from centralized to distributed execution is taking place, but not without some practical issues related to process migrations (transparent middleware, efficient and secure data transmissions, …). Extending Amdahl’s law to Cloud Computing will provide a better understanding of the involved factors related to the offloading process such as the time and energy speedups, together with some hints about the future of this era. Keywords: cloud computing, energy savings, computation offloading I NTRODUCTION Cloud computing is here to stay. According to Gartner's Hype cycle 1 , Cloud computing is mature enough to be in a productive phase. Nowadays, Cloud computing services can be exploited at several levels: Infrastructure-as-a-Service (IaaS), if customers are provided with a virtual machine that can be used in a customized way (e.g., Amazon EC2); Platform-as-a-service (PaaS), when providers offer a framework where customers can develop applications (Google App Engine, Windows Azure); and Software-as-a-Service (SaaS), if users only have access to specific applications (like Microsoft Office Web or Dropbox). The cloud offers considerable advantages over computing on local devices: automatic scaling; no need to purchase, upgrade or maintain bare-metal hardware; amongst others 2 . Even more of them can be listed in the case of mobile devices: energy savings, together with scarcity of local resources (which is largely tied to energy consumption). Indeed, the potential use of cloud offloading opens new doors to researchers (new programming paradigms, mobile agent software, security and privacy topics, balancing and deploying tools, etc.). However, when applications require some kind of real-time constraint, whether remote execution is faster than local execution would inevitably be called into question. Hence, not only energy consumption but also performance is crucial for these devices. But why moving certain applications to the Cloud yield extraordinary results whereas offloading others is simply out of the question? Consider for instance applications based on some type of searching in huge information databases stored in servers. Ranging from the
Page 2 simple Internet search of a term to a feature-based image searching using Google Goggles app, all of them perform a search over a gigantic amount of possible matching terms. Hence, the offloading overhead time is way lower than the time to obtain the search results. Obviously these apps are done on the server side for two reasons: the stored information and the high amount of computation that is required. Similarly, if user information to be processed was already stored in the cloud, almost no data transfer 5 would be required (only a pointer to the data), so cloud computing would be preferred. But what about those apps where information is captured online from the local device? Can they benefit by offloading today? And tomorrow? Software developers may want to weigh the pros and cons prior to moving their applications to the Cloud. In order to do so, a simple extension of Amdahl's Law is here presented. Moreover, this will help us to foresee what the future holds for Cloud Computing, together with its forthcoming research challenges. E XTENDING A MDAHL ' S L AW While originally stated for uniprocessor vs. multiprocessor execution time comparisons, the famous Gene Amdahl's law can be widely applied to any system. Let speedup S be the original execution time divided by an enhanced execution time 3 . If a fraction F (of the original time) is enhanced by a speedup S fraction , the overall speedup is: S= 1 (1 − F)+F/Sfraction Note that Amdahl assumed the extreme case: fraction F was infinitely parallelizable (no overhead times were included), and the remaining fraction, 1–F, was totally sequential. To extend Amdahl’s law for cloud computing, let us remember the application centralized execution model. Figure 1 depicts the main architectural pieces involved in centralized computation (red square). Next, we will extend it to describe the process involved in remote computation offloading.
Page 3 A. Centralized Computation Performance Classical centralized architectures consist of a Central Processing Unit (CPU) responsible for doing the following: capturing code instructions and operand data from its local hierarchic memory, executing them, and finally storing the result back in memory. Inside each core, instructions are executed in a sequential fashion according to the Von Neumann model. As a result, execution time for a uniprocessor can be expressed as N I CPI T (see sidebar 1), where N I is the Number of program instructions, CPI, the mean number of cycles per instruction, and T, the clock period. Nowadays, a CPU is composed of a number N c,local of “cores”, so according to Amdahl's model, the N c,local cores execute in parallel the fraction F of the program, while the rest is executed by a single core. Namely, F N I instructions are executed in parallel whereas (1-F)N I are not. For the sake of simplicity, let us suppose that CPU is a symmetric multicore chip (all cores are identical, currently the most widespread type). Likewise, the interaction with the outer world (input/output subsystem) is commonly assumed to be irrelevant in terms of execution time. Only the connection with the Internet, usually called NIC (Network Interface Controller), is to spend a significant time in our model. With the previous model, local program execution time is: t local =(1 − F)N I CPI local T local + F N I N c ,local CPI local T local =[(1 − F)+ F N c ,local ]N I CPI local T local Local Memory Local CPUsAux CPU NIC World User Other networks CLOUD (Virtual CPUs) Internet 2 3 1 N D,input N D,output Sending data Remote computing Receiving results 2 1 3 time Figure 1 . Centralized (red square) and Offloading computation (right and bottom) models.
Page 4 B. Cloud performance If an application is offloaded onto a cloud, the local device must first send its data and code through the Internet (green arrow, step 1, Figure 1). Secondly, the transferred application is executed on the cloud, and finally results are sent back to the local device (green arrow, step 3, Figure 1). From a time-based point of view, the bottom of Figure 1 schematizes the involved times in steps 1, 2, 3, where N Data =N D,intput + N D,output is the total amount in bits of data exchanged with the Cloud. Some extra simplifications will be assumed as well to calculate cloud execution time: • The program's code size can be neglected: either it is much smaller than the data size (this is evident when images, videos, big data, etc., are processed) or it already resided in the cloud in its major part (e.g. libraries). • Data transfer is done at a constant rate BW (communication bandwidth), while its startup latency is negligible (or done in parallel with transmissions). • Internal Cloud overhead times are not considered, as most of them should occur in parallel with other times. Indeed, some overlapping can exist between communication and computation times, being the two extreme overlapping cases: 1) If no overlapping existed, cloud execution time would be the sum of communication and computation times: ( ) ( ) cloudcloudI Data cloudcloudI cloudc, Data cloud TCPINF+ BW N =TCPIN N F +F+ BW N =t − −11 As cloud resources can be dynamically scaled up, the number of virtual processors is supposed to be large enough so as F/N c,cloud → 0. 2) Conversely, if overlapping were complete, communication times would be completely hidden, and hence: t cloud , overlapping =( 1 − F ) N I CPI cloud T cloud C. Comparing Cloud and local performance For the sake of simplicity, local and cloud CPU technologies are supposed to be similar, that is, CPI cloud ≈ CPI local ; T cloud ≈ T local . In fact, the cloud should be composed of cutting-edge technology, which means that cloud cores may well be probably faster than local cores. Hence, this simplification works in favor of local machines. With complete communication-computation overlapping, local execution time will be longer than cloud execution time. This is because communication penalties are not paid while cloud resources are far bigger than local ones. To ponder the worst Cloud case scenario, we will refer
Page 5 to the aforementioned “no overlapping” model. Dividing numerator and denominator by N I CPI T and reordering, we get the following speedup for this worst case: S t (F ,N c, local ,µ,D I )= F N c ,local +(1 − F) µ D I +(1 − F) For purposes of description, we have defined two parameters. Technological factors are comprised in μ = (CPI T BW) -1 , which can be seen as the ratio between the local machine's capacity of executing instructions per second and core (CPI T) -1 , by its capacity of sending data bits per second (BW). That is, it is reciprocal to the “offloading capabilities” that a machine has. The other parameter D I = N I /N data is the “computing density” of an application, that is, the mean number of instructions that are executed for any data bit to be exchanged with the cloud. Figure 2a shows the speedups S t as a function of D I for different F, supposing a modest local device (N c,local =1). Note that scales are logarithmic, because S t rises to high values for large D I . For high values of F, remote execution is clearly very advantageous when D I is moderate. But for F<0.5, offloading is faster even for low values of D I (bigger than 2). To sum up: for simple devices cloud computing can be beneficial in a huge range of applications. This situation is less favorable when the local device is more powerful (N c,local =4, Figure 2b). Nevertheless, a new effect then appears: for moderate values of D I >8, offloading is advantageous for any F≥0.5. This effect is similar for an extremely powerful device (N c,local =16, Figure 2c): from D I >20, the high consuming local device would not be beneficial. 10 0 10 1 10 2 10 3 10 -1 10 0 10 1 10 2 N clocal =1 D I Timing Speedup (a) F=0.99 F=0.95 F=0.90 F=0.80 F=0.50 10 0 10 1 10 2 10 3 10 -1 10 0 10 1 10 2 N clocal =4 D I Timing Speedup (b) F=0.99 F=0.95 F=0.90 F=0.80 F=0.50
Page 6 10 0 10 1 10 2 10 3 10 -2 10 -1 10 0 10 1 N clocal =16 D I Timing Speedup (c) F=0.99 F=0.95 F=0.90 F=0.80 F=0.50 Figure 2. Speedups of remote versus local execution (N c,local =1, 4, 16) as a function of D I for different F and µ=1. Result 1. Total cloud execution time depends strongly on the amount of communication and computation times that can be overlapped. Implication 1. This overlap should be thoroughly analyzed by the middleware that manages the task offloading (Sidebar 2 depicts an application case for mobile robots). Result 2. I D μ plays a critical role in speedup. Nowadays, μ is estimated by a few units ( CPI rounds 1.0 for most programs, and the orders of T and network BW are 1 ns and 1 Gbps respectively). However, in the near future μ is expected to progressively decrease, as the bandwidth will presumably continue increasing at a geometric rate, and CPI T has reached a fixed value (difficult to surpass with present technology, see Sidebar 1). D I is application dependent and will be analyzed in section 'Characterizing applications'. Implication 2. As I D μ is expected to decrease considering current technology trends, using the cloud will be more and more beneficial as years go by. Result 3. When using uniprocessors in the local device ( N c,local = 1), ( ) F+ D μ =S I t −1 1; thus offloading would be convenient for applications with low D I (even if F is less than 0.5). Implication 3. As long as I D μ decreases in the future, simplifying device hardware may set a trend. This has the additional benefits of saving energy and reducing its software complexity. Note that in IoT (Internet of Things) or “bare” thin client devices, local CPUs (see Figure 1)
Page 13 S IDEBAR 1: C OMPONENTS OF THE E XECUTION T IME Almost any computer machine works like a finite state machine (FSM). It can be considered that almost everything is synchronous with a clock which period is T, being the Central Processing Unit (CPU) the heart of this FSM. Therefore, the execution time t exec of any program must be multiple of N clocks clock periods:, that is, t exec = N clocks T . Likewise, Von Neumann model, settled 60 years ago, is the current model of the vast majority of modern computers. Von Neumann postulated that a program would consist of a number, namely N I , of instructions that would be executed in sequential order. e sequential execution is not an efficient (fast) way to make a computation, it is the common form that humans have to express the solution of problems, and hence most computing languages stick to this representation. N clocks can be split like: N clocks =N I N clocks N I =N I CPI , and therefore: t exec = N I CPI T . This is the fundamental formula of computer architects, and each of the 3 factors that contains (N I , CPI, T) do play a role in the design of a microprocessor. CPI (Clocks Per Instruction) comprises the “ability” that a CPU has to execute many instructions per clock. During the first stages of computer era, CPI was relatively high (several clocks per instruction), but with the advent of RISC (Reduced Instruction Set Machines) machines from 1985, architects could design efficient CPU pipelines that execute several instructions in just one clock cycle (CPI<1). Thus execution times could be reduced progressively due to CPI diminution and period contraction. But at the end of last century architectural innovations come to a limit. Today ideal CPI is given by the width of processor issue stage, which has been stuck around 5 for the last 15 years, although CPU stall cycles makes this quantity to be more than one (for a representative set of benchmarks). To make matters worse, around 2005 CPU period comes to a limit as well. These constraints had promoted the advent of the so-called “multicore Era”.
Page 14 S IDEBAR 2: S TEREO V ISION O FFLOADING FOR M OBILE R OBOTS Mobile robots have reached an elevated degree of maturity during the last decade. As an example, the time where fully autonomous cars are commercially available is now approaching. One of the points that has motivated this is the advancements on sensoring information processing, like stereo vision. This was allowed mainly due to the advent of more powerful parallel architectures, and to the availability of distributed operating systems, like the so-called RSF (Robotics Software Frameworks). RSFs have recently allowed to improve aspects such as scalability, reusability, deployment, and debugging 1 , and to deploy tasks either on board or on a cloud computing system, depending on their constraints 2 . Stereo vision is currently a very active field of research. When processing stereo frame pairs, the step with a higher degree of time complexity is the analysis of their differences, that is, the difference between what left and right eyes see. The so-called disparity map permits to calculate the distance of the objects to the cameras, more or less accurately in function of the used algorithm and the image features. Most representative algorithms have time complexities ranging from O(N 2 ) to O(N 11 ), where N is the horizontal image size 3 . One of the most extended algorithm is that included in OpenCV 4 , which has a complexity of O(N 3 ) -the usual for most of them-. The key problem is that real time requirements can become very difficult to meet when more accurate reconstruction of the environment is demanded. The frequency of stereo frame processing must be sufficiently high, whereas its latency small enough. For example, when the robot is moving, the distance to the nearest obstacle must be computed soon enough to avoid a crash or an emergency stop. Hence, this heavy task must be processed in a powerful computing system, or -as it is usual nowadayscarried out with low resolution images. Thus, cloud-based stereo vision is a possibility that is gaining more place. The offloading processing must be designed, not only to be parallel, but also to exploit the dynamic scalability of the cloud system. Concretely, if multiple CPU cores were available, processing times can run in parallel to the transfer ones, being the latter the bottleneck of the cloud offloading 2 . As a result, the mean processing frequencies result almost proportional to bandwidth network. R EFERENCES (S IDEBAR 2) 1. P. Iñigo-Blasco et al., “Robotics software frameworks for multi-agent robotic systems development,” Robot. Auton. Syst., vol. 60, no. 6, pp. 803–821, Jun. 2012. 2. J. Salmeron-Garcia et al. “A trade-off analysis of a cloud-based robot navigation assistant using stereo image processing,” IEEE TASE, vol. 12, no. 2, pp. 444–454, April 2015. 3. M. Sizintsev and R. P. Wildes, “Coarse-to-fine stereo vision with accurate 3D boundaries,” Image Vis. Comput., vol. 28, no. 3, pp. 352–366, Mar. 2010. 4. “OpenCV.org: About.” [Online]. Available: http://opencv.org/about.html. [Accessed: 07-
Page 15 Aug-2014]. A CKNOWLEDGEMENTS This work has been supported by the Spanish grant (with support from the European Regional Development Fund) BIOSENSE (TEC2012-37868-C04-02/01). R EFERENCES 1. “Hype Cycle for Application Architecture, 2013.” [Online]. Available: https://www.gartner.com/doc/2569522/hype-cycle-application-architecture-. [Accessed: 31- Jul-2014]. 2. M. Armbrust et al. Above the Clouds: A Berkeley View of Cloud Computing. EECS Department, University of California, Berkeley, February 2009. http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.html. 3. J. L. Hennessy, D.A. Patterson, Computer Architecture, Fifth Edition: A Quantitative Approach, 5 edition. Morgan Kaufmann, 2011. 4. R. Friedman, A. Kogan, and Y. Krivolapov, “On Power and Throughput Tradeoffs of WiFi and Bluetooth in Smartphones,” IEEE Trans. Mob. Comput., vol. 12, no. 7, pp. 1363–1376, Jul. 2013. 5. K. Kumar and Y.-H. Lu, “Cloud Computing for Mobile Users: Can Offloading Computation Save Energy?,” Computer, vol. 43, no. 4, pp. 51–56, Apr. 2010. 6. D. H. Woo and H.-H. S. Lee, “Extending Amdahl’s Law for Energy-Efficient Computing in the Many-Core Era,” Computer, vol. 41, no. 12, pp. 24–31, Dec. 2008. 7. E. Tilevich and Y.-W. Kwon, “Cloud-Based Execution to Improve Mobile Application Energy Efficiency,” Computer, vol. 47, no. 1, pp. 75–77, Jan. 2014. 8. S. Williams, A. Waterman, and D. Patterson, “Roofline: An Insightful Visual Performance Model for Multicore Architectures,” Commun. ACM, vol. 52, no. 4, pp. 65–76, Apr. 2009. 9. M. D. Hill and M. R. Marty, “Amdahl’s Law in the Multicore Era,” Computer, vol. 41, no. 7, pp. 33–38, Jul. 2008. 10. W. Wayt Gibbs, “Taking Computers To Task,” Sci. Am., Jul. 1997. 11. M. S. Gordon et al. “COMET: Code Offload by Migrating Execution Transparently.” Proc. 10th USENIX Conf. (OSDI’12), 2012, pp. 93–106.
Page 16 B IOGRAPHIES Fernando Díaz-del-Río received his Master in Physics (Electronics) and his Ph.D. from the University of Seville (Spain) in 1997, and currently is an Associate Professor at this University. Mobile robot navigation, bioinspired systems and distributed computing systems are his main research topics. He has participated in more than 20 research projects and contracts. Contact him at [email protected] Javier Salmerón-García received his BsC in Computer Engineering (2011) and MSc in Computer Engineering and Networks (2012) from the University of Seville. He also received an MSc in Software Engineering for Technical Computing from Cranfield University (UK, 2011). He is now doing a PhD focused on Cloud Robotics in the University of Seville. Moreover, he works as a part-time lecturer at the same University. Contact him at jsalmer[email protected]. José Luis Sevillano is an Associate Professor at the University of Seville, Spain. He served as VP Membership of SCS (2009-11), and currently serves as Associate Editor of Simulation (Sage) and of the International Journal of Communication Systems (Wiley). He is an IEEE Senior Member, has co-authored 80+ papers and has participated in 20+ research projects. His research interests include real-time communications and architectures, Mobile Robots and eHealth and Rehabilitation Systems. Contact him at [email protected]