Collision-Free Motion Algorithms for Sensors Automated Deployment to Enable a Smart Environmental Sensing-Net

Ting Yu Lin, Kun Ru Wu, You Shuo Chen, Yan Syun Shen

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


As natural habitats protection has become a global priority, smart sensing-nets are ever-increasingly needed for effective environmental observation. In a practical monitoring network, it is critical to deploy sensors with sufficient automated intelligence and motion flexibility. Recent advances in robotics and sensors technology have enabled automated mobile sensors deployment in a smart sensing-net. Existing deployment algorithms can be employed to calculate adequate destinations (goals) for sensors to perform respective monitoring tasks. However, given the calculated goal positions, the problem of how to actually coordinate a fleet of robots and schedule moving paths from random initials to reach their goals safely, without collisions, remains largely unaddressed in the wireless sensor networking (WSN) literature. In this paper, we investigate this problem and propose polynomial-time collision-free motion algorithms based on batched movements to ensure all the mobile sensors reach their goals successfully without incurring collisions. We observe that the grouping (batching) strategy is similar to the coloring procedure in graph theory. By constructing a conflict graph, we model the collision-free path scheduling as the well-known k-coloring problem, from which we reduce to our k-batching problem (determining the minimum number of required batches for a successful deployment) and prove its NP completeness. Since the k-batching problem is intractable, we develop CFMA (collision-free motion algorithm), a simple yet effective batching (coloring) heuristic mechanism, to approximate the optimal solution. Performance results show that our motion algorithms outperform other existing path-scheduling mechanisms by producing 100% sensors reachability (success probability of goals reaching), time-bounded deployment latency with low computation complexity, and reduced energy consumption.

Original languageEnglish
JournalIEEE Transactions on Automation Science and Engineering
StateAccepted/In press - 2022


  • autonomous sensors deployment
  • Collision avoidance
  • collision-free motion algorithm
  • Environmental observation and monitoring
  • graph theory
  • Intelligent sensors
  • Robot kinematics
  • Robot sensing systems
  • Sensors
  • smart sensing network automation
  • System recovery
  • vertex coloring.
  • Wireless sensor networks


Dive into the research topics of 'Collision-Free Motion Algorithms for Sensors Automated Deployment to Enable a Smart Environmental Sensing-Net'. Together they form a unique fingerprint.

Cite this