Tham khảo tài liệu 'advances in robot navigation part 5', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Application of Streaming Algorithms and DFA Learning for Approximating Solutions to Problems in Robot Navigation 69 that we proposed in Lucatero et al. 2004 to pose the robot tracking problem as a repeated game. The main motivation of this proposal was that in many recent articles on the robot tracking problem La Valle Latombe 1997 La Valle Motwani 1997 and Murrieta-Cid Tovar 2002 they make the assumption that the strategy of the target robot is to evade the observer robot and based on that they propose geometrical and probabilistic solutions of the tracking problem which consists on trying to maximize by the observer the minimal distance of escape of the target. We feel that this solution is limited at least in two aspects. First the target don t interact with the observer so there is no evidence that the strategy of the target will be to try to escape if it doesn t knows what are the actions taken by the observer. The second aspect is that even if it take place some sort of interaction between the target and the observer the target is not necessarily following an evasion strategy so this may produce a failure on the tracking task. Because of that we proposed a DFA learning algorithm followed by each robot and obtained some performance improvements with respect to the results obtained by the methods used in Murrieta-Cid Tovar 2002 . In the last few years many research efforts have been done in the design and construction of efficient algorithms for reconstructing unknown robotic environments Angluin Zhu 1996 Rivest Schapire 1993 Blum Schieber 1991 Lumelsky Stepanov 1987 and apply learning algorithms for this end Angluin Zhu 1996 Rivest Schapire 1993 . One computational complexity obstacle for obtaining efficient learning algorithms is related with the fact of being a passive or an active learner. In the first case it has been shown that it is impossible to obtain an efficient algorithm in the worst case Kearns Valiant 1989 Pitt Warmuth 1993 . In the second case if
