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.
H.Al Tair, T.Taha, M.Al-Qutayri and J.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.
2.
M.Aleksy, A.Korthaus and M.Schader, Design considerations for a CORBA-based architecture for lightweight agents (CARLA), International Journal of Web Intelligence and Agent Systems.1 (2003), 259–271.
3.
O.Aoun and A.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.
4.
R.Borie, C.Tovey and S.Koenig, Algorithms and complexity results for graph-based pursuit evasion, Autonomous Robots31 (2011), 317–332. doi:10.1007/s10514-011-9255-y.
5.
K.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.
6.
E.Ehsan and F.Kunwar, Probabilistic search and pursuit evasion on a graph, Transactions on Machine Learning and Artificial Intelligence3 (2015), 57–65.
7.
J.Ferber, O.Gutknecht and F.Michel, From agents to organizations, an organizational view of multi-agent systems, in: Agent-Oriented Software Engineering IV (AOSE 2003), P.Giorgini, J.P.Müller and J.Odell, eds, Lecture Notes in Computer Science, Vol. 2935, Springer, Berlin, 2004, pp. 214–230. doi:10.1007/978-3-540-24620-6_15.
8.
T.Goudon, B.Nkonga, M.Rascle and M.Ribot, Self-organized populations interacting under pursuit-evasion dynamics, Physica D: Nonlinear Phenomena304–305 (2015), 1–22. doi:10.1016/j.physd.2015.03.012.
9.
S.Jia, X.Wang and L.Shen, A continuous-time Markov decision process-based method with application in a pursuit evasion example, IEEE Transactions on Systems, Man, and Cybernetics: Systems46(9) (2016), 1215–1225. doi:10.1109/TSMC.2015.2478875.
10.
I.Kamon and E.Rivlin, Sensory based motion planning with global proofs, IEEE Transactions on Robotics and Automation13 (1997), 435–440.
11.
K.Krishnamoorthy, S.Darbha, P.P.Khargonekar, D.Casbeer, P.Chandler and M.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 A.Vector-Value, Markov decision process for multi-objective stochastic path planning, International Journal of Hybrid Intelligent Systems9 (2012), 45–60. doi:10.3233/HIS-2012-0146.
13.
J.Qiao, Z.Hou and X.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.
L.Rech, C.Montez and R.S.De Oliveira, Itinerary determination of imprecise mobile agents with firm deadline, International Journal of Web Intelligence and Agent Systems6 (2008), 421–439.
15.
V.Sezer and M.Gokasan, A novel obstacle avoidance algorithm: Follow the gap method, Robotics and Autonomous Systems60(9) (2012), 1123–1134. doi:10.1016/j.robot.2012.05.021.
16.
M.Souidi and S.Piao, A new decentralized approach of multi-agent cooperative pursuit based on the iterated elimination of dominated strategies model, Mathematical Problems in Engineering2016 (2016), Article ID 5192423. doi:10.1155/2016/5192423.
17.
M.Souidi, S.Piao, G.Li and L.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.
M.Souidi, S.Piao, G.Li and L.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.
A.Suna and A.El Fallah Seghrouchni, Programming mobile intelligent agents: An operational semantics, International Journal of Web Intelligence and Agent Systems5 (2007), 47–67.
20.
J.Thunberg, P.Ogren and X.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.
C.Undeger and F.Polat, Multi-agent real-time pursuit, Autonomous Agents and Multi-Agent Systems21 (2010), 69–107. doi:10.1007/s10458-009-9102-0.
22.
S.Wena, X.Chena, C.Maa, H.K.Lama and S.Huaa, The Q-learning obstacle avoidance algorithm based on EKF-SLAM for NAO autonomous walking under unknown environments, Robotics and Autonomous Systems72 (2015), 29–36. doi:10.1016/j.robot.2015.04.003.
23.
B.Yongqiang, X.Wenzhi, F.Hao and L.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.
A.Yufka and O.Parlaktuna, Performance comparison of bug algorithms for mobile robots, in: Proceedings of the 5th International Advanced Technologies Symposium, Karabuk, Turkey, 2009.
25.
C.Ze-Su, S.Li-Ning, G.Hai-Boet al., Multi-robot cooperative pursuit based on task bundle auction. Intelligent robotics and applications, Lecture Notes in Computer Science5314 (2008), 235–244. doi:10.1007/978-3-540-88513-9_26.
26.
M.Zohaib, S.M.Pasha, N.Javaid and J.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, S.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.
