Mobile agents path planning based on an extension of Bug-Algorithms and applied to the pursuit-evasion game

Abstract

Pursuit-evasion game is a known problem in Multi-agent systems. This problem is approached through the elaboration of different task coordination and path planning mechanisms. This paper proposes a new sensor-based obstacle avoidance method extended from Bug-Algorithms with the aim of providing an efficient path planning to the pursuers during the targets’ capture. Noting that, the environment is decomposed on a grid of cells, in which Markov Decision Process (MDP) principles are implemented to lead the motion of the agents. In relation to Bug-Algorithms, this method increases the utilization of the sensors data to improve the decision making regarding the obstacle’s leaving point. This fact makes this method goal-oriented and decreases the pursuers’ path to the goal. Moreover, we showcase the performance of this method through a comparative study with our previous works in which Bug-2 algorithm was used to avoid the obstacles encountered.

Keywords

Obstacle avoidance path planning pursuit-evasion mobile agents

Get full access to this article

View all access options for this article.

References

Al Tair,

Taha,

Al-Qutayri and

Dias, Decentralized multi-agent POMDPs framework for humans-robots teamwork coordination in search and rescue, in: 2015 International Conference of Information and Communication Technology Research (ICTRC), IEEE, New York, 2015, pp. 210–213. doi:10.1109/ICTRC.2015.7156459.

Aleksy,

Korthaus and

Schader, Design considerations for a CORBA-based architecture for lightweight agents (CARLA), International Journal of Web Intelligence and Agent Systems. 1 (2003), 259–271.

Aoun and

El Afia, Application of multi-agent Markov decision processes to gate assignment problem, in: 2014 Third IEEE International Colloquium in Information Science and Technology (CIST), IEEE, New York, 2014, pp. 196–201. doi:10.1109/CIST.2014.7016618.

Borie,

Tovey and

Koenig, Algorithms and complexity results for graph-based pursuit evasion, Autonomous Robots 31 (2011), 317–332. doi:10.1007/s10514-011-9255-y.

Chi, Lee and

M.F.R.

Obstacle, Avoidance in mobile robot using neural network, in: 2011 IEEE International Conference on Consumer Electronics, Communications and Networks (CECNet), IEEE, New York, 2011, pp. 5082–5085. doi:10.1109/CECNET.2011.5768815.

Ehsan and

Kunwar, Probabilistic search and pursuit evasion on a graph, Transactions on Machine Learning and Artificial Intelligence 3 (2015), 57–65.

Ferber,

Gutknecht and

Michel, From agents to organizations, an organizational view of multi-agent systems, in: Agent-Oriented Software Engineering IV (AOSE 2003),

Giorgini,

J.P.

Müller and

Odell, eds, Lecture Notes in Computer Science, Vol. 2935, Springer, Berlin, 2004, pp. 214–230. doi:10.1007/978-3-540-24620-6_15.

Goudon,

Nkonga,

Rascle and

Ribot, Self-organized populations interacting under pursuit-evasion dynamics, Physica D: Nonlinear Phenomena 304–305 (2015), 1–22. doi:10.1016/j.physd.2015.03.012.

Jia,

Wang and

Shen, A continuous-time Markov decision process-based method with application in a pursuit evasion example, IEEE Transactions on Systems, Man, and Cybernetics: Systems 46(9) (2016), 1215–1225. doi:10.1109/TSMC.2015.2478875.

10.

Kamon and

Rivlin, Sensory based motion planning with global proofs, IEEE Transactions on Robotics and Automation 13 (1997), 435–440.

11.

Krishnamoorthy,

Darbha,

P.P.

Khargonekar,

Casbeer,

Chandler and

Pachter, Optimal minimax pursuit evasion on a Manhattan grid, in: 2013 American Control Conference (ACC), IEEE, New York, 2013, pp. 3421–3428. doi:10.1109/ACC.2013.6580360.

12.

Mouaddib and

Vector-Value, Markov decision process for multi-objective stochastic path planning, International Journal of Hybrid Intelligent Systems 9 (2012), 45–60. doi:10.3233/HIS-2012-0146.

13.

Qiao,

Hou and

Ruan, Q-learning based on neural network in learning action selection of mobile robot, in: 2007 IEEE International Conference on Automation and Logistics, IEEE, New York, 2007, pp. 263–267. doi:10.1109/ICAL.2007.4338568.

14.

Rech,

Montez and

R.S.

De Oliveira, Itinerary determination of imprecise mobile agents with firm deadline, International Journal of Web Intelligence and Agent Systems 6 (2008), 421–439.

15.

Sezer and

Gokasan, A novel obstacle avoidance algorithm: Follow the gap method, Robotics and Autonomous Systems 60(9) (2012), 1123–1134. doi:10.1016/j.robot.2012.05.021.

16.

Souidi and

Piao, A new decentralized approach of multi-agent cooperative pursuit based on the iterated elimination of dominated strategies model, Mathematical Problems in Engineering 2016 (2016), Article ID 5192423. doi:10.1155/2016/5192423.

17.

Souidi,

Piao,

Li and

Chang, Coalition formation algorithm based on organization and Markov decision process for multi-player pursuit evasion, International Journal of Multiagent and Grid Systems (MGS) 11 (2015), 1–13. doi:10.3233/MGS-150226.

18.

Souidi,

Piao,

Li and

Chang, Multi-agent cooperation pursuit based on an extension of AALAADIN organisational model, Journal of Experimental and Theoretical Artificial Intelligence (JETAI) 28(6) (2015), 1075–1088. doi:10.1080/0952813X.2015.1056241.

19.

Suna and

El Fallah Seghrouchni, Programming mobile intelligent agents: An operational semantics, International Journal of Web Intelligence and Agent Systems 5 (2007), 47–67.

20.

Thunberg,

Ogren and

Hu, A Boolean control network approach to pursuit evasion problems in polygonal environments, in: 2011 IEEE International Conference on Robotics and Automation (ICRA), IEEE, New York, 2011, pp. 4506–4511. doi:10.1109/ICRA.2011.5979948.

21.

Undeger and

Polat, Multi-agent real-time pursuit, Autonomous Agents and Multi-Agent Systems 21 (2010), 69–107. doi:10.1007/s10458-009-9102-0.

22.

Wena,

Chena,

Maa,

H.K.

Lama and

Huaa, The Q-learning obstacle avoidance algorithm based on EKF-SLAM for NAO autonomous walking under unknown environments, Robotics and Autonomous Systems 72 (2015), 29–36. doi:10.1016/j.robot.2015.04.003.

23.

Yongqiang,

Wenzhi,

Hao and

Jixiang, Obstacle avoidance for multi-agent systems based on stream function and hierarchical associations, in: 2012 31st Chinese IEEE Control Conference (CCC), IEEE, New York, 2012, pp. 6363–6367.

24.

Yufka and

Parlaktuna, Performance comparison of bug algorithms for mobile robots, in: Proceedings of the 5th International Advanced Technologies Symposium, Karabuk, Turkey, 2009.

25.

Ze-Su,

Li-Ning,

Hai-Bo et al., Multi-robot cooperative pursuit based on task bundle auction. Intelligent robotics and applications, Lecture Notes in Computer Science 5314 (2008), 235–244. doi:10.1007/978-3-540-88513-9_26.

26.

Zohaib,

S.M.

Pasha,

Javaid and

Iqbal, IBA: Intelligent bug algorithm – A novel strategy to navigate mobile robots autonomously, in: Communication Technologies, Information Security and Sustainable Development,

F.K.

Shaikh,

B.S.

Chowdhry,

Zeadally,

D.M.A.

Hussain,

A.A.

Memon and

M.A.

Uqaili, eds, Communications in Computer and Information Science (CCIS), Vol. 414, Springer, Berlin, 2014, pp. 291–299. doi:10.1007/978-3-319-10987-9_27.