Article Preview
TopIntroduction
Problems of watching and guarding have been investigated for many years. The problem of how many static guards must be used to watch the whole art gallery built of n vertices (“The Art Gallery Problem”) was the first one. It was stated in 1973 and solved analytically in 1975 (Chvátal). Then, many different variants of the problem were formulated. Firstly, different requirements for guards, concerning their placement and behavior were taken into account. Next, new shapes of areas watched by guards were assumed. Finally, both static and mobile guards were used. With time this has become more and more complex. Nevertheless, for polygon areas without holes analytical solutions were usually found. Detailed classification of the variants and the solutions is presented in the next section of the paper.
“Watchman Route Problem” (WRP) aiming to find the shortest route in a polygon with holes (obstructions) such that all points of the polygon are visible from that route is the most complicated of the variants. It is NP-hard even if the holes are convex which was proved by Chin and Ntafos (1991). Therefore, it has usually been ignored. Nowadays, the progress in technology of mobile robots stimulates searching for a solution of WRP.
To give people comfort and security, robots steadily replace human beings in heavy, arduous or dangerous works. In the area of security and surveillance there are many applications where mobile robots (mobots) are involved (Robotics Trends, 2010). Mobots can be used in buildings to search for bombs that were planted by terrorists. They can also be used for searching victims after disasters, guarding dangerous areas, watching buildings or mines which are likely to collapse, and in many similar situations. The shorter path mobots chose to watch the area the greater chance of survival (for both, victims and constructions). Even if human life is not in danger, shortening a path of guarding could minimize the cost of energy or time of exploration of the area.
Recently, mobots have become more and more independent. They can move from one place to another without human assistance. This depends only on data coming from mobot’s camera or any device investigating environment. They may be endowed with strategies of operation or even artificial intelligence (Ali, Ghaffari, Liao, & Hall, 2006). However, when a mobot should select the shortest route between two places in an area with many different obstructions, then the task becomes much more complicated. Operators may remotely control mobots or programmers may put the route in mobot’s memory. Nevertheless, the route must be found.
In the real world, areas of operation of mobots are much more complicated than simple rooms with small number of polygons. Even if obstructions could be approximated with the help of polygons, their number and configurations might be unlimited. Hence, the WRP, generalized for mobots (MRP) is a real challenge for researchers.
In the paper a new approach to solve the MRP is presented. It is based on Ant Colony Optimization (ACO) (Dorigo & Stützle, 2004). The paper is organized as follows: related work is presented, the problem is stated, adaptation of the ant algorithm for solving the problem is presented, and experimental results are discussed. The paper ends with conclusions.