Show simple item record

dc.contributor.advisor Shalan, Mohamed AlShawi, Maha 2017-10-09T08:37:08Z Fall 2017 en_US 2017-10-09
dc.description.abstract The current trends in the robotics field have led to the development of large-scale swarm robot systems, which are deployed for complex missions. The robots in these systems must communicate and interact with each other and with their environment for complex task processing. A major problem for this trend is the poor task planning mechanism, which includes both task decomposition and task allocation. Task allocation means to distribute and schedule a set of tasks to be accomplished by a group of robots to minimize the cost while satisfying operational constraints. Task allocation mechanism must be run by each robot, which integrates the swarm whenever it senses a change in the environment to make sure the robot is assigned to the most appropriate task, if not, the robot should reassign itself to its nearest task. The main contribution in this thesis is to maximize the overall efficiency of the system by minimizing the total time needed to accomplish the dynamic task allocation problem. The near-optimal allocation schemes are found using a novel hybrid decentralized algorithm for a dynamic task allocation in a swarm of homogeneous robots, where the number of the tasks is more than the robots present in the system. This hybrid approach is based on both the Simulated Annealing (SA) optimization technique combined with the Discrete Particle Swarm Optimization (DPSO) technique. Also, another major contribution in this thesis is the formulation of the dynamic task allocation equations for the homogeneous swarm robotics using integer linear programming and the cost function and constraints are introduced for the given problem. Then, the DPSO and SA algorithms are developed to accomplish the task in a minimal time. Simulation is implemented using only two test cases via MATLAB. Simulation results show that PSO exhibits a smaller and more stable convergence characteristics and SA technique owns a better quality solution. Then, after developing the hybrid algorithm, which combines SA with PSO, simulation instances are extended to include fifteen more test cases with different swarm dimensions to ensure the robustness and scalability of the proposed algorithm over the traditional PSO and SA optimization techniques. Based on the simulation results, the hybrid DPSO/SA approach proves to have a higher efficiency in both small and large swarm sizes than the other traditional algorithms such as Particle Swarm Optimization technique and Simulated Annealing technique. The simulation results also demonstrate that the proposed approach can dislodge a state from a local minimum and guide it to the global minimum. Thus, the contributions of the proposed hybrid DPSO/SA algorithm involve possessing both the pros of high quality solution in SA and the fast convergence time capability in PSO. Also, a parameters' selection process for the hybrid algorithm is proposed as a further contribution in an attempt to enhance the algorithm efficiency because the heuristic optimization techniques are very sensitive to any parameter changes. In addition, Verification is performed to ensure the effectiveness of the proposed algorithm by comparing it with results of an exact solver in terms of computational time, number of iterations and quality of solution. The exact solver that is used in this research is the Hungarian algorithm. This comparison shows that the proposed algorithm gives a superior performance in almost all swarm sizes with both stable and small execution time. However, it also shows that the proposed hybrid algorithm's cost values which is the distance traveled by the robots to perform the tasks are larger than the cost values of the Hungarian algorithm but the execution time of the hybrid algorithm is much better. Finally, one last contribution in this thesis is that the proposed algorithm is implemented and extensively tested in a real experiment using a swarm of 4 robots. The robots that are used in the real experiment called Elisa-III robots. en_US
dc.description.sponsorship First, I thank God for providing me with the power to be able to finish my thesis and manage to cross all the obstacles that I have been through during my study time. Then, I would like to thank my supervisor Dr. Mohamed Shalan for his dedication to get many ideas implemented, through the digestion and redirection of the crazy ideas I came up with. I do appreciate a lot his support when I first proposed the hybrid DPSO/SA approach. I have my first experience in providing a complete research and publication under his supervision. Thanks for his continuous technical support and comments, during various design phases. My deepest gratitude goes to Prof. Amal Esawi; the associate dean of graduate studies at AUC who made my master life easier by just being there. Due to her loyalty, sincerity, her generous support, encouragement and guidance, I have continued this work till the end. Thanks for her inspiration. I would like to extend thanks to many colleagues who generously supported me a lot in the past few years. My appreciation goes to Rana, Heba, Amr Morsy, Abdullah, Mahmoud Elfar, Mohamed Shalaby, Amr Elhenawy, Ahmed Samir, Ahmed Zahran, and Louis. I do really wish them all the best in their career and life. Also, I have to mention all those close friends, who have been always there when I needed them most, or those who interacted with me almost on daily basis, I mean: Nada, Wessam, Alaa, Omnia, and Sahar. Eman Helal; my mother has been a steady, silent soldier in my background lousy life. Without her dedication and perfection, I would never be able to do those many things I have done during the past few years. I have also to show gratitude to my father, sister Nada and my brothers who always believe in me. My extended family, Fatma, Sara, Ahmed, Abdullah, Areej, Morooj, and Basma, I hope they excuse me for being away when they needed me most. Second, beyond the call of duty, I have to appreciate my luck to gain two grants, research grant and conference grant throughout my study time, which are supported by Yousef Jameel Science and Technology Research Center. Thanks to Dr. Florin and Dr. Yousra, for providing me with a greater insight on the big picture, results, and analysis. I have to acknowledge that I have learned from them both a lot in my proposal defense. en_US
dc.format.extent 177 p. en_US
dc.format.medium theses en_US
dc.language.iso en en_US
dc.rights Author retains all rights with regard to copyright. en
dc.subject Swarm robotics en_US
dc.subject Dynamic tasks allocations en_US
dc.subject hybrid algorithms en_US
dc.subject.lcsh Thesis (M.S.)--American University in Cairo en_US
dc.title Decentralized algorithm of dynamic task allocation for a swarm of homogeneous robots en_US
dc.type Text en_US
dc.subject.discipline Robotics, Control and Smart Systems en_US
dc.rights.access This item is restricted for 2 years from the date issued en_US
dc.contributor.department American University in Cairo. Rare Books and Special Collections Library en_US
dc.embargo.lift 2019-10-09T08:37:08Z
dc.description.irb American University in Cairo Institutional Review Board approval is not necessary for this item, since the research is not concerned with living human beings or bodily tissue samples. en_US
dc.contributor.committeeMember Hammad, Sherif
dc.contributor.committeeMember ElKasas, Sherif

Files in this item


This item appears in the following Collection(s)

  • Theses and Dissertations [1360]
    This collection includes theses and dissertations authored by American University in Cairo graduate students.

Show simple item record