Note: This is my research survey report which was written for my MS Computer Science degree.
Dedication:I dedicated this work to my parents, teachers and mentors who educated me and helped me in achieving my goals.
Acknowledgements
I would like to express my appreciation to Dr. Sajjad Haider for his guidance during the term of my candidature. Without his valuable assistance, this work would have not been completed.
Abstract
Developing software for robots requires to combine artificial intelligence (AI) concerns with motion driving aspects. From AI perspective, robot has to perform automated reasoning or planning and make rules and strategies. From motion driving perspective, the software needs to control the actual hardware of the robot. AI part of the software is usually done with logic or functional languages, such as Prolog or LISP; on the other hand, motion driving is a matter of imperative approaches, like C/C++ or assembly, or even Java.
The Erlang language, due to the syntax and programming model, exhibit some characteristics that fit well both of the aspects discussed above: Erlang is functional and somewhat imperative. In literature study, it was found that most of the time Erlang was used in robot applications to remove the need of programming in two languages: one for AI logic and other for motion driving.
Problem Statement
By nature, a robot agent is intrinsically a concurrent system. A robot agent, in any environment at specific time, has to perform many computations which, by nature, can be done concurrently. A single agent, for example, has to perceive the environment by processing the data from perception devices, do some processing on environment data to convert it into meaningful information, devise a strategy or plan, exhibit a certain behaviour, control the motion of hardware and change the state. Furthermore, it has to keep some history and update it during its journey to adapt to changes in the environment.
A Robocup agent needs to do several tasks which can easily done concurrently. The agent, on the field, has to compute its own location, location of ball, mutual distance with the ball, position of other players on the field, maintain the communication with other fellow players in team, devise strategy and learn from the rules and finally walk towards the goal. It can be easily concluded that the agent does following three main tasks at a given time.
- Perceive the environment
- Make the plans and strategy
- Perform certain actions on the environment
These high level tasks can be modelled as separate and independent processes running concurrently and sharing data with each other. If there is a major change in the environment then process to handle plans will change plan and strategy. Similarly, if there is command from planning process to change the current state or apply some action, only then the process which perform actions will update its state. At granularity, we can have several concurrent processes running independently and communicating with each other. These processes will update the state only when required else they would continue running with the same state.
Traditionally, these agents have been programmed using imperative programming languages like C#, C++ or Java. Mostly, the agents are programmed sequentially: they receive the environment state from server, perform some computations and send the action commands back to server. Even if some agents are programmed with concurrency, they have used these imperative programming languages. All these languages provide concurrency by using shared-memory state model which is not natural to programmers and is prone to errors.
With advent of most robust hardware, it has become necessary that Robocup agent should not be a sequential application but it should exploit the hardware’s capabilities to become a highly concurrent application. Even the Robocup Soccer Simulation server should be a concurrent application (the work on this is in initial stages by Simspark). In this paper, the author would focus only on design of Robocup agent application using concurrent programming model.
This requirement introduces a question as which concurrency model should be used in order to design our agent. The traditional shared memory state concurrency model can be a competent candidate but it has its own limitations which are discussed in next sections. Using this model has some benefits that it has been acquired by many prominent programming languages as a way to provide concurrency.
However, these programming languages were not designed for concurrent environments and thus lack the true nature of concurrency. This paper provides an alternate approach to handle concurrency requirements of Robocup agent application. It recommends the use of Actor concurrency model which was designed for concurrent systems and distributed environments. The paper provides the results of literature review done on the topic of using Erlang in Robotics and further offers methodology on how to design concurrent robot agent using Erlang.
Introduction to Actor Model
With advent of multicore computers, there has been a growing need for programmers to write concurrent programs. The current dominant model for concurrent programming is a shared memory model: multiple threads working with a shared memory of a process. This model has its own limitations and is unnatural to developers, leading to programs that are error-prone. Due to this, there is often a need to have better concurrency model which can be used to write concurrent programs. Thus, the research has resulted into development of many new programming languages with new concurrency models.
Among such concurrency models, Actor Concurrency Model, introduced by Carl Hewitt and refined by Gul Agha, has received an increasing interest in recent years. The Actor model was designed for concurrent and distributed environment and thus it is inherently concurrent model. In Actor model, systems comprise of concurrent, autonomous light-weight processes, called actors, and messages.
Actors do not share any state and each actor has its own mutable local state; each actor is responsible for updating its own local state. In order to share data, actors communicate by sending asynchronous messages to other actors. Actors need to know the address of other actors in order to communicate to them.
Unlike threads, actors never share state and thus never need to compete for locks to get access to shared data. They share data by sending messages that are immutable. Immutable data cannot be modified, so access does not require locks and if there are no locks then actor doesn’t have to wait to access the data.
Actor model successfully overcomes the drawbacks of shared state memory model of concurrency. We do not use threads and thus we do not need access locks and starvations. Programs written with actor model languages are a set of simple light weight processes (actors) and thus are not error prone as compared to threads which share same state.
Introduction to Erlang
Erlang, an actor concurrency model based programming language, was created in 1986 at Ericsson Telecom AB to write better telephony applications and was designed for writing concurrent programs that ‘run forever’.
Erlang is a dynamically typed, functional language with garbage collector. It is influenced by logical and imperative languages. Erlang implements language-level lightweight processes (actors) in a shared- nothing architecture. It follows the Actor Model strategy and these processes communicate exclusively using messages. Erlang easily integrates with programs and libraries written in other languages.
It has the following main characteristics:
- Functional Notation. Erlang is entirely a functional language and these functions can have several clauses (like Prolog). Other main feature of Erlang is that functions can also have “guards”, i.e. boolean conditions which must be met in order to activate any particular clause of a function. This model allows easy implementation of FSM-based computation and rule production systems.
- Portability. Erlang programs are platform independent and can be run on any OS. Just like Java, Erlang programs are compiled into bytecoded executables.
- Concurrency. Erlang has the capability of spawning lightweight processes and making them communicate with each other by means of tuples (flexible language construct). This capability of Erlang is in conformation with Actor model of concurrency.
- Fault-tolerance. Erlang is highly fault-tolerant language and has mechanism of restarting the processes when they crash. A supervisor process monitors all the running processes and is in charge of restarting them if any of them crashes. This supervision is natively provided by Erlang.
Distribution. Erlang is intrinsically distributed, i.e. it allows a transparent communication among processes belonging to different network nodes.
RoboCup Soccer Simulator
The RoboCup Soccer Simulator, the soccer server, is a research and educational tool for multi-agent systems and artificial intelligence. It enables two teams of eleven simulated autonomous players to play a game of football. A match is carried out in client/server style: the server provides a virtual field and simulates all the movements of a ball and the players, and each client controls the movements of one player. Communication is done via UDP/IP sockets, enabling players to be written in any programming language that supports UDP communication.
Using Erlang in Robotics and Literature Review
Developing software for robots requires to combine artificial intelligence (AI) concerns with motion driving aspects. From AI perspective, robot has to perform automated reasoning or planning and make rules and strategies. From motion driving perspective, the software needs to control the actual hardware of the robot. AI part of the software is usually done with logic or functional languages, such as Prolog or LISP; on the other hand, motion driving is a matter of imperative approaches, like C/C++ or assembly, or even Java.
The Erlang language, due to the syntax and programming model, exhibit some characteristics that fit well both of the aspects above: Erlang is functional and somewhat imperative. In literature study, it was found that most of the time Erlang was used in robot applications to remove the need of programming in two languages: one for AI logic and other for motion driving.
Some research papers indicate that Erlang overcame the problems of concurrency. As robot agent is intrinsically concurrent, therefore a pure concurrent programming language proved to be efficient in programming robot applications.
Other focused on the fault-tolerance feature of Erlang as well. Often in traditionally programmed robotics application, failure in one part of the code would result in crash of entire application. Applications written in Erlang, thanks to its process supervision, did not experience such issues. If any process was crashed then supervisor process restarted that process. Due to fault-tolerance of Erlang, one paper solely applied this language on hardware level of robot application to make the system more resistant to hardware failures.
The separation of concerns and layered application architecture also remained feature of robot applications programmed in Erlang. In this way, the code of hardware or low level components was written in separate layer in separate modules and code of intelligence or high level components was written in separate layer. This also allows to reuse parts of previously designed application or change the hardware with small modification to code of low level modules while higher level modules remain untouched.
Not much work has been done on using Erlang in Robocup Soccer Teams. However, IT University in Gothenburg has been developing such teams which use Erlang in Robocup soccer agents and exploit the Actor concurrent model in their system. Each of Robocup football player is composed of four Erlang processes (actors): a communicator process, a planner process, an executor process and a timer process. Communication between these processes is done using Erlang’s built-in message passing mechanism. In each cycle, player receives messages from soccer server containing sensor information. The messages are parsed and sent to a process which updates and stores contextual knowledge of agent. These messages are also sent to planner process which elaborates a plan and sends it to executor process. Finally, the executor process sends the action commands to the server. (Earle, Fredlund and Iglesias)The following table shows the description of some of most important research papers referred during literature survey:
Click here to open the table in Google Sheets
Methodology and Strategy
The Robocup soccer player application can be easily broken down into independent running processes. Each process will have its own dedicated task and state and communicates with other process by means of message passing. The following main processes can be created for a single agent application:
- Communicator
- Perceptor
- Thinker
- Effector
- Messenger
Communicator process would be responsible to receive UDP/IP messages from the server and send commands to it. It would transform the data provided by server into meaningful information and then send it to preceptor process. Communicator process may spawn two other processes and supervise them: one to process receive data and other to send data to server in required format.
Perceptor process would carry on further computations on processed data received by Communicator process. It would extract more information from this data such as doing localization, identifying the position of ball and position of teammates etc. It will also spawn child processes to do these tasks e.g. a separate process for localization.
Thinker process would communicate to Perceptor process and would make strategies and plan based on information received from Perceptor. With this, Thinker process will maintain its state and form rules and exhibit behaviors. Finally, it would talk to Effector process to give it commands as part of action plan to be executed.
Effector process would be responsible to obtain actions from Thinker and calculate the exact angles for joints and sends them to communicator process. Communicator process would then send the data to server. Effector process may spawn child processes for several calculations i.e. to calculate different types of walk or dribble.Messenger process would be responsible to communicate to other fellow agents. It would encode and decode the messages during the match. This way the agents would be able to collaborate with each other. This process would work individually and would only be executed when there is a message to send or process.
Conclusion
Author has discussed the detailed literature survey done on use of Erlang, an actor based programming language, in robot agent applications. Furthermore, author has offered a methodology to make concurrent Robocup Soccer Agent application. The devised methodology can be used to create agents which are concurrent and fault-tolerant. From literature study, it is prominent that Erlang can give best results when used in multi-agent system.
References
Earle, Clara Benac, Lars-Åke Fredlund, José Antonio Iglesias, and Agapito Ledezma. "Verifying robocup teams." In International Workshop on Model Checking and Artificial Intelligence, pp. 34-48. Springer Berlin Heidelberg, 2008.
Grüner, Sten, and Thomas Lorentsen. "Teaching Erlang using robotics and player/stage." In Proceedings of the 8th ACM SIGPLAN workshop on ERLANG, pp. 33-40. ACM, 2009.
Karmani, Rajesh K., Amin Shali, and Gul Agha. "Actor frameworks for the JVM platform: a comparative analysis." In Proceedings of the 7th International Conference on Principles and Practice of Programming in Java, pp. 11-20. ACM, 2009.
Santoro, Corrado. "An erlang framework for autonomous mobile robots." In Proceedings of the 2007 SIGPLAN workshop on ERLANG Workshop, pp. 85-92. ACM, 2007.
Di Stefano, Antonella, and Corrado Santoro. "eXAT: an Experimental Tool for Programming Multi-Agent Systems in Erlang." In WOA, vol. 12, pp. 1-127. 2003.
Di Stefano, Antonella, and Corrado Santoro. "Using the Erlang language for multi-agent systems implementation." In IEEE/WIC/ACM International Conference on Intelligent Agent Technology, pp. 679-685. IEEE, 2005.
Szomiński, Szymon, Konrad Gądek, Michal Konarski, Bogna Błaszczyk, Piotr Anielski, and Wojciech Turek. "Development of a cyber-physical system for mobile robot control using erlang." In Computer Science and Information Systems (FedCSIS), 2013 Federated Conference on, pp. 1441-1448. IEEE, 2013.
Varela, Carlos, Carlos Abalde, Laura Castro, and José Gulias. "On modelling agent systems with Erlang." In Proceedings of the 2004 ACM SIGPLAN workshop on Erlang, pp. 65-70. ACM, 2004.
Note: The research is still going on and I am writing erlang code for Robocup Soccer Agent. I would include results in my next research paper which I will self-publish here. Soon, I would also make the code open source.