Environmental Complexity Measurement Using Shannon Entropy

This paper presents a novel approach to measure the complexity of environments for complete coverage path planning (CCPP) approaches. For this measurement, the main challenge is to take various environmental factors together to measure the complexity of a complicated environment. The size of environments and the numbers of corners on maps are commonly taken into consideration. However, the size of robots to conduct CCPP navigation, the number of obstacles and the location of obstacles on maps are factors that cannot be ignored. To overcome the aforementioned challenge, we propose a method guided by the Shannon Entropy formula. Four environmental factors, that include area size, robot size, obstacle number, and obstacle locations, are all considered as inputs in our environmental complexity measurement. The experimental results show that our quantitative metric is consistent with visual observation, and therefore provides a new algorithmic approach to measuring spatial complexity of a 2-D map.