Gazihan Alankus, Nuzhet Atay, Chenyang Lu, O. Burchan Bayazit

Autonomous mobile agent navigation is crucial to many mission-critical applications (eg, search and rescue missions in a disaster area). In this research, we present how sensor networks may assist probabilistic roadmap methods (PRMs), a class of efficient navigation algorithms particularly suitable for dynamic environments. A key challenge of applying PRM algorithms in dynamic environment is that they require the spatiotemporal sensing of the environment to solve a given navigation problem. To facilitate navigation, we propose a set of query strategies that allow a mobile agent to periodically collect real-time information (eg, fire conditions) about the environment through a sensor network. Such strategies include local spatiotemporal query (query of spatial neighborhood), global spatiotemporal query (query of all sensors), and border query (query of the border of danger fields). We investigate the impact of different query strategies through simulations under a set of realistic fire conditions. Our results demonstrate that (1) spatiotemporal queries from a sensor network result in significantly better navigation performance than traditional approaches based on on-board sensors of a robot, (2) the area of local queries represent a tradeoff between communication cost and navigation performance, (3) through in-network processing our border query strategy achieves the best navigation performance at a small fraction of communication cost compared to global spatiotemporal queries.

Our goal is to navigate safely in a danger field, i.e., reach a goal while avoiding the dynamic dangerous regions. In our approach, temperature data collected by sensors are forwarded to the robot and using a variation of PRM, robot finds a safe path from start to goal, constantly updating the path as the temperature readings change.

Figure 1: Temperature data obtained from FDS

In order to validate our approach, we have tested our system both on a real sensor network with real robot and a simulated robot with a simulated network. Our sensor network simulator is built on top of NIST Fire Dynamics Simulator. Using our software, we can simulate a sensor network which can relay real-time temperature information from a spreading fire(Fig. 1). Combining our sensor network simulator with a robot simulator, Player/Stage, we found that when they are supplied with real-time temperature data by a sensor network, PRMs can successfully navigate a robot in a fire. We also found that using a border query strategy, we can capture the spatiotemporal information at the reduced cost. Our experiments with the real robot showed that we can use our algorithm on a real scenario as well.

We address the power consumption and network congestion using different query strategies. We have classified our queries in two types: spatiotemporal(Fig. 2 and Fig. 3) and border-response(Fig. 4). We further classified the queries into two types based on their ranges (i.e., vicinity of the robot or entire network): global(Fig. 2) and local(Fig. 3).

Figure 2: Global Query	Figure 3: Local Query	Figure 4: Border-response

We conducted our experiments bot in the simulation environment and on real sensor network and robot hardware. In simulation experiments we used previously computed spreading fire data from FDS. In the experiments with real data, we used previously set constant temperature values representing a static fire(Fig 5).

Figure 5: Experiment

INFOCOM'06 Submission Video: Static Danger :

INFOCOM'06 Submission Video: Dynamic Danger :

Simulation video:

Motion planning using sensor readings video:

Motion planning without using sensor readings video:

Gazihan Alankus, Nuzhet Atay, Chenyang Lu, O. Burchan Bayazit

Our second approach relies on an embedded roadmap in the sensor network that always contains safe paths. The roadmap is adaptive, i.e., it adapts its topology to changing dangers. Mobile robots in the environment use the roadmap to reach their destinations. We evaluated the performance of embedded roadmap both in simulations using realistic conditions and with real hardware. Our results show that the proposed navigation algorithm is better suited for sensor networks than traditional navigation field based algorithms. Our observations suggest that there are two drawbacks of traditional navigation field based algorithms, (i) increased power consumption, (ii) message congestion that can prevent important danger avoidance messages to be received by the robots. In contrast, our approach significantly reduces the number of messages on the network (up to 160 times in some scenarios) while increasing the navigation performance.

In order to assist the robot navigation, the sensor network must have some abstract mechanisms. For example, there must be some mechanisms for node generation and node connection to build an embedded roadmap. After it is built, the sensor network also needs a maintenance mechanism to keep the embedded roadmap up-to-date. Finally, when a robot asks for a path, the sensor network needs to find an optimal route to the goal through Goal Potential mechanism. Figure 5 summarizes the interaction within the network and with the robots. After node generation, connection builds the roadmap. Maintenance may revoke connection to disconnect some edges that are in danger, or find alternative edges. When the robot arrives, it finds a path to the embedded roadmap through connection mechanism. Goal Potential mechanism is responsible for finding the best path to the goal. The embedded roadmap then directs the robot towards the goal. While following the path, if the robot discovers an obstacle that is invisible to sensor network’s sensors, it informs the embedded roadmap and an alternative route is found.

Figure 5: System overview for Adaptive Embedded Roadmap

After the initial deployment of the sensor network, the embedded roadmap is built in a distributed fashion. Node generation is handled by turning some motes to milestone motes (i.e., motes that contain a roadmap node). The connection phase is a local planning operation where the milestones broadcast connection request to their vicinity. This request is further propagated by receiving motes. The propagation continues until requests from two milestones intersect. In which case, the mote at the intersection sends connection messages to both originators. Among several possible connections between two milestones, the best path is selected.

Once the roadmap is built, a robot can utilize it to navigate. Since the robot is not aware of the topology of the roadmap, the sensor network must find the best path. For this purpose, we use an NF2-like wavefront expansion on the roadmap. First, through geographic routing, the robot asks the mote closest to its goal (i.e., goal mote) to connect itself to the roadmap. Once the goal mote is connected to the embedded roadmap, it originates a potential wave on the roadmap where the potential value represents the goodness of the path. When the wave reaches a milestone mote, the milestone sets the best direction towards the goal. At the same time, the robot requests a connection to the roadmap. After receiving several responses from the nearby milestone motes, then the robot selects the best route and follows it. When the robot reaches a milestone mote, the mote directs it towards the next mote in the path. This process is repeated until the robot reaches its goal. Our embedded roadmap is adaptive and changes based on the spatio-temporal information. The topology and the edge weights are altered if the danger spreads towards the roadmap, hence the roadmap always contains safe paths. If the robot on its path recognizes an obstacle unknown to the sensors, it informs the embedded roadmap to remove edges on the obstacle.

(a)	(b)	(c)
(d)	(e)	(f)
Figure 6: Building embedded roadmap. (a) Milestones motes, (A, B,C), start neighbor discovery. (b) NEIGHBOR-DISCOVER is propagated by the receiving motes. (c) Neighbors are found and propagated back to the milestones. (d) According to the goodness metric, the best routes to the neighbors become the edges. (e) Goal connects to the roadmap and the best routes through a navigation field on the roadmap are set. (f) An edge on danger disconnects then re-connects and a roadmap node migrates (dashed