search

TypingCat / spatial-topology-teleoperation

Teleoperation for Mobile Robot using Semantics
GNU General Public License v3.0
4 stars 0 forks source link

How to merge graphs #11

Closed TypingCat closed 3 years ago

TypingCat commented 3 years ago

The robot should be able to create the topology from the observations to guide users in real time. No building plans or maps are given. Therefore graph merging is an essential function for topology construction. Issue #7 mentioned a valid approach to this problem. I have to embody this approach to code level.

extract_topology_thought_1

TypingCat commented 3 years ago

The overall process of merging is as follows:

def lidar_callback(observation):
    global topology

    t = extract(observation)
    t_sample = resample(t)
    topology.estimate(set(t_sample & topology))
    topology.add(set(t_sample - topology))

The function extract was verified in issue #6. Next, I need to implement the function resample.

TypingCat commented 3 years ago

The new function resample is tested on commit 6aca68f03453e26f60186850d4117b9d63fc700f.

It's hard to resample graph directly, because resampling causes information loss. Even the graph has no priority: In other words, it cannot decide what to throw away for resampling. Therefore I convert the graph to spanning tree using priority queue. It means that near nodes are more important than far nodes. Results are as follows:

test_resample

The left is the second sample of test #7, and the middle is the resampling result with resolution 0.3. All the edges have same length, all intersections are maintained. On the other hand, the right is the resampling result with resolution 1.0. The edges towards the end node (-0.5, 6.1) disappeared, and the two central intersections were merged. Each operation took 0.0068 and 0.0018 seconds. I'm satisfied with these results.

TypingCat commented 3 years ago

This approach is deprecated. See issue #7 and test #13 for details.