Dynamic Task Allocation for Mobile Robots

P.V.Aswin; D.Prasanna Vadana

Dynamic Task Allocation for Mobile Robots

P.V.Aswin¹ and D.Prasanna Vadana²

PG Student [Embedded Systems], Dept. of EEE, Amrita School of Engineering, Coimbatore ,Tamilnadu, India
Assistant Professor, Dept. of EEE, Amrita School of Engineering, Coimbatore, Tamilnadu, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Abstract

Multi robotic missions requires extensive efforts by human programmer to program each robotic vehicle according to the changing situations.Un manned vehicles are mostly programmed at vehicle level that is, each vehicle is programmed individually before deploying them. This paper proposes an approach to program un-manned robotic vehicles at unit level and use them for a surveillance application. A variation of popular Contract Net protocol is used. As soon as a task is injected by the user, the master controller broadcasts the tasks to all robots, on receiving the task notification, each robot forms a bid containing its present parameters like position, battery voltage level etc and sends it to the master controller, the master controller extracts the parameters from the bids, apply an optimization function and would award the task to any of the robots.

Keywords

Multi robots, Dynamic task allocation, Contract Net protocol, Pair wise comparison, Intruder detection.

INTRODUCTION

Presently there is a huge demand for electronic security systems, most of the systems are based on static sensors, which just trigger an Alarm, when an intruder enters or Video cameras which are employed in different parts of the area under coverage for monitoring the situation. These techniques require expensive hardware and high speed network connectivity, if they have to be accessed by a user at a remote location. Mobile robots capable of tracking human beings can be of great use in infrastructure-surveillance applications. Instead of deploying static sensors in every nook and corner, mobile robots can be used which can traverse the whole region and track the motion of the intruders. Most of the presently available multi-robot surveillance systems make use of vision based techniques, where each of the mobile robots is equipped with a camera and image processing is done on-board itself [9][11]. These systems require high-end cameras capable of night vision features and advanced controllers capable of image and video processing. These also can significantly increase the total cost. In the proposed system, a sensor called IR compound eye is used for motion tracking. A particular robot from the team of robots would be tracking the intruder and a dynamic map showing the movement of robot and the intruder would be available to the user present at a remote location.Multi-robots can be used to perform a wide variety of tasks in a collaborative manner like military applications [2]; surveillance etc, a great amount of effort is required by the human programmer to individually program each robot according to the changing situation. In the proposed approach, all the vehicles are programmed at unit level and requires minimum amount of human intervention.

LITERATURE SURVEY

Automatic tasking and re-tasking can be used to produce a stable, robust and tightly integrated unit, where by manpower requirements are reduced. In tightly constrained operations like military operations, there will be many unfavourable conditions like communication failures, unexpected loss of vehicles by enemy attacks etc, so a static task allocation scheme cannot be employed. Task allocation has to change according to the changing scenario. Douglas C Mackenzie developed a variant of standard Contract Net protocol [1] called as Collaborative tasking protocol aimed at dynamic task allocation of unmanned vehicles [3]. Brian P Gerkey and Maja J Mataric developed another variant of Contract Net protocol [1] called as MURDOCH and used to for a box pushing application by multiple robots [2] . This protocol was based on a publish and subscribe communication model. A MANET [4] was set for localization of mobile robots used in disaster relief operations. E. Gil Jones M.,Bernardine Dias and Anthony Stentz developed an approach to program a group of fire fighting vehicles to tackle a large scale fire spread throughout the city in case of a large scale disaster [6] . Here the vehicles coordinate among themselves to perform the task successfully. Song Hiang Chia1, Jr Hung Guo1, Bo Yi Li1, Kuo Lan Su2 developed a team of robots for an intelligent security system [5]. All the robots were equipped with same kind of sensors and could detect the same event. The event was confirmed using Dempster- Shafter evidence theory.David Anhalt and John Spofford developed an approach to assign roles to specialised multirobots on the basis of sensors mounted on them [7]. These sensors can be added or removed at any time. Jennifer M. Riley and Mica R. Endsley developed a strategy where a UAV (Unmanned Aerial Vehicle) was used to locate mines and a team of UGVs (Unmanned Grounded Vehicles) were used to mark the spot of mines to aid the soldiers in exploring enemy areas [8]. Punarjay Chakravarty and Ray Jarvis developed an indoor surveillance system making use of overhead cameras and a mobile robot for intruder detection [10].

ALGORITHM FOR TASK ALLOCATION

This paper proposes to develop a task allocation algorithm for dynamically allocating a task to a team of multi robots for a Surveillance application. The system consists of a master controller and three mobile robots. The mobile robots will be moving in a closed space initially. Whenever an intruder enters the space, the master controller receives the information. As soon as the master controller receives the information; it broadcasts this information to all the mobile robots. The mobile robots would send back a bid containing information about their current position, their power level and whether they are involved in doing some tasks, based on this information, the master controller would calculate a cost function and would award the task to the robot which is most appropriate to perform this task. The task involves tracking the position of the moving intruder. While performing the task, the robot periodically sends a message to the master controller, when these messages are missed for a certain period of time, it is assumed that the robot is not able to carry out the task and the task is awarded to another robot using the same method.

The main considerations for awarding the task to the robot is that the distance between the intruder and the robot must be minimum and the power level of the robot must be maximum. The base of this approach is the contract net protocol [1]. The difference from standard contract-net protocol is that an approach called pair-wise comparison is used to select the appropriate robot for carrying out the task.

Most of the existing techniques use complicated optimization techniques which are difficult to implement on controllers. The proposed technique can be coded easily in C language and can be implemented on any controller. As soon as the master controller receives the bid, it extracts the individual parameters of each robot. The distance of each mobile robot from the intruder is calculated using the distance formula. If (x1,y1) are the coordinates of location of one robot and (x2,y2) are coordinates of location of second robot and (x,y) are the coordinates of the location of the intruder, then the distances of each robot from the intruder is calculated using the distance formula

Based on the pair-wise comparison algorithm, scores are assigned to each robot and the task is allotted to that particular robot which has the maximum value of score.

The distance and the power level of each robot is compared with the distance and power level of all the remaining robots, if the distance of one robot is less than the distance of other robot, then it’s score is incremented by one, likewise if the power level of one robot is greater than the power level of other robot, then it’s score is incremented by one. After this process has been completed for all the robots, the task is granted to that particular robot which has the maximum value of score, if two robots are having the same value for maximum score, the task is allocated to that robot which has the maximum value of power. In case of real-time implementation, an extra condition that whether the selected robot is involved in performing some other task is also checked.

SIMULATION RESULTS

The Algorithm is coded in C++ language and compiled using DEV-C++ IDE. The user can enter the x, y positions and power level (in volts) of three mobile robots and also the x-y coordinates of the intruder. After executing the Algorithm, the individual scores of each robots and the winner is displayed .Two case are analyzed, first case where two of the robots are having same top score and the second case where all the three robots are having different scores.

In the first case, Robot 1 and Robot 3 are having same value of top score i.e. 3, so the task is allocated to Robot 3,which has the maximum value for power, in the second case all the three robots are having different scores, hence the task is allocated to Robot 3,which has the top score. The distances of all the three robots from the intruder are also displayed in both the cases

HARDWARE IMPLEMENTATION

A hardware setup consisting of one master node and two slave nodes (all three LPC-2148 microcontrollers) is setup and tested. Data transmission is done wirelessly with the help of XBEE modules. Here static nodes are used instead of mobile robots for demonstration purpose. The master controller is connected to a Desktop PC where the user has the provision to inject a task into the system by typing a particular keyword. On receiving the task, the master controller broadcasts the information to both the slave nodes wirelessly. Immediately after receiving the notification, the slave nodes form their bids. Here the voltage across the potentiometer present in LPC -2148 board is used to mimic the battery voltage of nodes. This voltage can be varied easily by varying the potentiometer (Shown in Fig 10) with the help of a screw driver. The frame format of bid is as shown in Fig 5. Hard coded values are used for x and y positions of the robot. The total size of bid is 14 bytes.

Embedded-C codes for both the master and slave nodes are written in Kiel uVision 4 IDE and loaded into different controllers. After receiving bids from individual nodes, the parameters are extracted and scores are calculated for each robot. The ADC voltage extracted from each node is displayed on the LCD display of the master controller as shown in Fig 7 and 8.The Algorithm is applied and the winner of the process is displayed on the master node’s LCD Display as shown in Fig 9.

CONCLUSION

Contract-Net Protocol is modified by using pair-wise comparison for calculating the scores of robots. The task is allocated to that robot which is having maximum value of score. Distance of the robot from the intruder and the power level of the robots are taken as the parameters for computing cost function. The Algorithm is implemented and verified in Dev-C++ IDE. Hardware implementation is done using LPC-2148 controllers for a master node and two slave nodes. This protocol can be implemented on any finite number of mobile robots for any tightly constrained application.

References

Reid G. Smith, “The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver”, IEEE Transactions on Computers, Vol. C-29, No. 12, December, 1980
Brian P. Gerkey and Maja J. Mataric, “Sold!: Auction Methods for Multirobot Coordination” IEEE Transactions on Robotics And Automation, Vol. 18, No. 5, October 2002.
Douglas C. MacKenzie, “Collaborative Tasking Of Tightly Constrained Multi-Robot Missions” Second International Workshop on Multi-Robot Systems, 2003.
Ulf Witkowski, Jacques Penders, Veysel Gazi, “Ad-hoc network communication infrastructure for multirobot systems in disaster scenarios”, GUARDIANS Project, 6th Framework program of European Union
Song Hiang Chia, Jr Hung Guo, Bo Yi Li1, Kuo Lan Su, “Team Mobile Robots Based Intelligent Security System” ,Applied Mathematics & Information Sciences Journal, No. 2L, 435-440 (2013).
E. Gil Jones M. Bernardine Dias Anthony Stentz,” Time-extended Multi-robot Coordination for Domains with Intra-path Constraints, Proceedings of the 26th Army Science Conference, December 2008.
David Anhalt, John Spofford, “Use of Mission Roles as a Robotic Tasking Device”, Mobile Robots XIV, SPIE Proceedings Vol. 3838, Boston MA, September 1999.
Jennifer M. Riley, Mica R. Endsley ,“Situation Awareness In HRI With Collaborating Remotely Piloted Vehicles”, Proceedings Of The Human Factors And Ergonomics Society 49th Annual Meeting—2005.
Donato Di Paola, Annalisa Milella, Grazia Cicirelli and Arcangelo Distante ,“An Autonomous Mobile Robotic System for Surveillance of Indoor Environments”, International Journal of Advanced Robotic Systems, Vol. 7, No. 1 (2010).
Punarjay Chakravarty and Ray Jarvis, “External Cameras & A Mobile Robot: A Collaborative Surveillance System”, Australasian Conference on Robotics and Automation (ACRA), December 2-4, 2009, Sydney, Australia.
Nelson Gonc¸alves, Jo˜ao Sequeira, M.Isabel Ribeiro,Madhavan Shanmugavel, AntoniosTsourdos, Brian White , “Indoor active surveillance”, 13th IEEE International Conference Methods and Models in Automation and Robotics, August 2007.