Robotic applications are becoming ubiquitous. They are widely used in several areas (e.g., healthcare, disaster management, and manufacturing). However, their provisioning still faces several challenges such as cost and resource usage efficiency. Cloud computing is an emerging paradigm that may aid in tackling these challenges. It has three main facets: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) and Software as a Service (SaaS). This paper focuses on the IaaS aspects of robotic applications as cloud computing services. It proposes an architecture that enables cost efficiency through virtualization and dynamic task delegation to robots, including robots that might belong to other clouds. Overlays and RESTful Web services are used as cornerstones. A prototype is built using LEGO Mindstorms NXT as the robotic platform, and JXTA as the overlay middleware. Related work is reviewed, the functional entities and interfaces of the architecture are described, and the prototype architecture is presented along with the implemented scenario. © 2014 IEEE.