仅使用距离和方位查找位置？
三角测量的工作原理是检查您与三个已知目标的角度。
“我知道那是亚历山大灯塔，它位于地图上的 (X,Y) 位置，在我的右侧 90 度角。”针对不同的目标和角度再重复 2 次。
三边测量的工作原理是检查您与三个已知目标的距离。
“我知道那是亚历山大灯塔，它位于地图上的 (X,Y) 位置，而我距离它 100 米。”针对不同的目标和范围再重复 2 次。
但这两种方法都依赖于了解您正在查看的内容。
假设您在森林中，无法区分树木，但您知道关键树木在哪里。这些树被手工挑选为“地标”。
你有一个机器人缓慢地穿过那片森林。
您是否知道有什么方法可以仅根据角度和范围来利用地标之间的几何形状来确定位置？请注意，您还会看到其他树，因此您不知道哪些树是关键树。忽略目标可能被遮挡的事实。我们的预算法会处理这个问题。
1）如果存在，它叫什么？我找不到任何东西。
2) 您认为出现两个相同位置“点击”的可能性有多大？我想这是相当罕见的。
3）如果有两个相同的位置“命中”，下一步移动机器人后如何确定我的确切位置。 （我认为，在我重新定位机器人后，连续出现两次精确角度的可能性在统计上是不可能的，除非像玉米这样成行生长的森林）。我会再次计算位置并希望得到最好的结果吗？或者我会以某种方式将我之前的位置估计纳入我的下一个猜测中吗？
如果存在，我想了解它，如果不存在，则将其开发为一个副项目。我只是现在没有时间重新发明轮子，也没有时间从头开始实现这一点。因此，如果它不存在，我将不得不找出另一种方法来定位机器人，因为这不是这项研究的目的，如果它存在，我们希望它是半简单的。
Triangulation works by checking your angle to three KNOWN targets.
"I know the that's the Lighthouse of Alexandria, it's located here (X,Y) on a map, and it's to my right at 90 degrees." Repeat 2 more times for different targets and angles.
Trilateration works by checking your distance from three KNOWN targets.
"I know the that's the Lighthouse of Alexandria, it's located here (X,Y) on a map, and I'm 100 meters away from that." Repeat 2 more times for different targets and ranges.
But both of those methods rely on knowing WHAT you're looking at.
Say you're in a forest and you can't differentiate between trees, but you know where key trees are. These trees have been hand picked as "landmarks."
You have a robot moving through that forest slowly.
Do you know of any ways to determine location based solely off of angle and range, exploiting geometry between landmarks? Note, you will see other trees as well, so you won't know which trees are key trees. Ignore the fact that a target may be occluded. Our pre-algorithm takes care of that.
1) If this exists, what's it called? I can't find anything.
2) What do you think the odds are of having two identical location 'hits?' I imagine it's fairly rare.
3) If there are two identical location 'hits,' how can I determine my exact location after I move the robot next. (I assume the chances of having 2 occurrences of EXACT angles in a row, after I reposition the robot, would be statistically impossible, barring a forest growing in rows like corn). Would I just calculate the position again and hope for the best? Or would I somehow incorporate my previous position estimate into my next guess?
If this exists, I'd like to read about it, and if not, develop it as a side project. I just don't have time to reinvent the wheel right now, nor have the time to implement this from scratch. So if it doesn't exist, I'll have to figure out another way to localize the robot since that's not the aim of this research, if it does, lets hope it's semi-easy.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
很好的问题。
您正在研究的问题的名称是定位，它与绘图一起是目前机器人技术中最重要和最具挑战性的两个问题。简而言之，定位是“给定一些传感器观察结果，我如何知道自己在哪里？”的问题。
地标识别是支撑机器人技术实践的隐藏“技巧”之一。如果无法唯一地识别一个地标，您最终可能会得到很高比例的错误信息，特别是考虑到真实的传感器是随机的（即/结果会存在一些不确定性）。您选择合适的定位方法几乎肯定取决于您能够如何唯一地识别地标，或者将地标模式与地图关联起来。
在许多情况下，最简单的自本地化方法是蒙特卡洛本地化。实现此目的的一种常见方法是使用粒子过滤器。这样做的优点是，当您没有出色的运动模型、传感器功能并且需要强大的东西来处理意外效果（例如移动障碍物或地标遮挡）时，它们可以很好地应对。一个粒子代表车辆的一种可能状态。最初，粒子是均匀分布的，随着车辆移动并添加更多传感器观察结果。粒子状态被更新以远离不太可能的状态 - 在给定的示例中，粒子将远离范围/方位与当前位置估计中应可见的区域不匹配的区域。如果有足够的时间和观察，粒子往往会聚集到车辆很可能位于的区域。查找 Sebastian Thrun 的作品，特别是“概率机器人学”一书。
Great question.
The name of the problem you're investigating is localization, and it, together with mapping, are two of the most important and challenging problems in robotics at the moment. Put simply, localization is the problem of "given some sensor observations how do I know where I am?"
Landmark identification is one of the hidden 'tricks' that underpin so much of the practice of robotics. If it isn't possible to uniquely identify a landmark, you can end up with a high proportion of misinformation, particularly given that real sensors are stochastic (ie/ there will be some uncertainty associate with the result). Your choice of an appropriate localisation method, will almost certainly depend on how well you can uniquely identify a landmark, or associate patterns of landmarks with a map.
The simplest method of self-localization in many cases is Monte Carlo localization. One common way to implement this is by using particle filters. The advantage of this is that they cope well when you don't have great models of motion, sensor capability and need something robust that can deal with unexpected effects (like moving obstacles or landmark obscuration). A particle represents one possible state of the vehicle. Initially particles are uniformly distributed, as the vehicle moves and add more sensor observations are incorporated. Particle states are updated to move away from unlikely states - in the example given, particles would move away from areas where the range / bearings don't match what should be visible from the current position estimate. Given sufficient time and observations particles tend to clump together into areas where there is a high probability of the vehicle being located. Look up the work of Sebastian Thrun, particularly the book "probabilistic robotics".
您正在寻找的是蒙特卡罗定位（也称为粒子滤波器）。 这里有一个关于该主题的很好的资源。
或者几乎任何来自概率机器人群体的东西，Dellaert、Thrun、Burgard 或 Fox。如果您雄心勃勃，可以尝试寻求完整的 SLAM 解决方案 - 此处发布了一堆库。
或者，如果您确实雄心勃勃，则可以使用因子图从首要原则开始实施。
What you're looking for is Monte Carlo localization (also known as a particle filter). Here's a good resource on the subject.
Or nearly anything from the probabilistic robotics crowd, Dellaert, Thrun, Burgard or Fox. If you're feeling ambitious, you could try to go for a full SLAM solution - a bunch of libraries are posted here.
Or if you're really really ambitious, you could implement from first principles using Factor Graphs.
我假设您想从打开森林内的机器人开始。我进一步假设机器人可以使用角度和距离计算每棵树的位置。
然后，您可以通过迭代树木并计算到其所有邻居的距离来识别地标。在 Matlab 中，您可以使用 pdist 获取所有（唯一）成对距离的列表。
然后您可以迭代树来识别地标。对于每棵树，将其到所有邻居的距离与地标之间的已知距离进行比较。每当您找到候选地标时，您都会检查其可能的地标邻居以获得正确的距离签名。既然你说你总是应该能够在任何给定时间看到五个地标，那么你将尝试匹配 20 个距离，所以我想说误报的可能性并不太高。如果候选地标及其候选同伴地标与完整的相对距离模式不匹配，则检查下一棵树。
找到所有地标后，您只需进行三角测量即可。
请注意，根据您测量角度和距离的准确程度，您需要能够在任何给定时间看到更多地标树。我的猜测是，你需要以足够的密度来间隔地标，如果你有很高的测量精度，你可以一次看到至少三个。
I assume you want to start by turning on the robot inside the forest. I further assume that the robot can calculate the position of every tree using angle and distance.
Then you can identify the landmarks by iterating through the trees and calculating the distance to all its neighbours. In Matlab you can use
pdistto get a list of all (unique) pairwise distances.Then you can iterate through the trees to identify landmarks. For every tree, compare the distances to all its neighbours to the known distances between landmarks. Whenever you find a candidate landmark, you check its possible landmark neighbours for the correct distance signature. Since you say that you always should be able to see five landmarks at any given time, you will be trying to match 20 distances, so I'd say that the chance of false positives is not too high. If the candidate landmark and its candidate fellow landmarks do not match the complete relative distance pattern, you go check the next tree.
Once you have found all the landmarks, you simply triangulate.
Note that depending on how accurately you can measure angles and distances, you need to be able to see more landmark trees at any given time. My guess is that you need to space landmarks with sufficiently density that you can see at least three at a time if you have high measurement accuracy.
我想你只需要到两个地标的距离和看到它们的顺序（即从左到右你看到点A和B）
I guess you need only distance to two landmarks and the order of seeing them (i.e. from left to right you see point A and B)
所以你：
一些，但不是所有的树。
机器人在实际森林中的某个地方
不用看地图，就有
看着附近的树木
生成了所有的内部地图
一个小区域内的树木及其
与他们的相对位置
机器人，每棵树看起来都一样
每隔一棵树。
如果每棵实际的树上都写有机器人可以读取的唯一名称，然后（其中一些）这些树及其名称出现在地图上，那么这将是微不足道的。
一种方法是为每棵树附加一个（不一定是唯一的）“签名”，描述其相对于附近树木的位置。
然后，当你继续前进时，机器人会开到一棵树前并找到该树的“签名”，然后你会找到地图上与该签名“匹配”的所有树。
如果地图上只有一棵唯一的树匹配，那么机器人正在寻找的树可能就是地图上的那棵树（是的，你知道机器人在哪里）——放下一个沉重但暂定的点在地图上机器人与匹配树的相对位置处——机器人旁边的树肯定不是地图上的任何其他树。
如果地图上的几棵树匹配——它们都具有相同的非唯一签名——那么您可以在地图上相对于每一棵树的机器人位置处放置一些权重较小的暂定点。
唉，即使找到一个或多个匹配项，机器人正在查看的树仍然有可能根本不在地图上，并且该树的签名恰好与地图上的一棵或多棵树相同，并且所以机器人可以在地图上的任何地方。
如果地图上没有一棵树匹配，那么机器人正在查看的树肯定不在地图上。 （也许稍后，一旦机器人确切地知道它在哪里，它应该开始添加这些树到地图上？）
当你沿着路径行驶时，你会按照你估计的方向和速度推动这些点。旅行。
然后，当您检查其他树木时，可能在沿着路径行驶得更远之后，您最终会在地图上看到很多点，并且希望在实际位置有一个沉重的、高度重叠的簇，并且希望每个点都是容易被忽略的点孤立的巧合。
最简单的签名是从特定树到附近树的距离列表。
地图上的一棵特定的树与森林中的一棵特定的树“匹配”，当地图上的每棵附近的树都在森林中尽可能远的“相同”距离处有一个相应的附近的树时根据已知的距离和角度误差来判断。
（“附近”，我的意思是“足够近，机器人应该能够明确确认树确实在那里”，尽管用“我的机器人可以看到”之类的东西来近似这一点可能更简单所有树都在 R 的范围内，所以我只会费心尝试来匹配距离我的机器人 R*1/3 圆圈内的树，以及我的距离列表包括与我尝试匹配的特定树相距 R*2/3 的圆内的树”）。
如果您非常粗略地知道自己的南北方向，则可以创建“更独特”的签名，即在地图上和（希望如此）在真实森林中的虚假匹配较少。
当地图上的每棵附近的树在森林中以“相同”的距离和方向存在一棵对应的树（就您已知的距离而言）时，就会发生机器人旁边的树的“匹配”和角度误差。
假设您看到地图上的树“Fred”在 N 到 W 象限中距它 10 米处有另一棵树，但机器人旁边的一棵树在 N 到 W 象限中的那个距离内肯定没有任何树木，但它南边10米处有一棵树。
在这种情况下，那么（使用更复杂的签名）您绝对可以告诉机器人不在 Fred 旁边，即使简单的签名会给出（错误）匹配。
另一种方法：
“数字纸”解决了类似的问题……你能以专门设计的易于识别的图案种植几棵树吗？
So you:
some, but not all trees on it.
robot somewhere in the actual forest
that, without looking at the map, has
looked at the nearby trees and
generated an internal map of a all
the trees in a tiny area and its
relative position to them
robot, every tree looks the same as
every other tree.
If only each actual tree had a unique name written on it that the robot could read, and then (some of) those trees and their names were on the map, this would be trivial.
One approach is to attach a (not necessarily unique) "signature" to each tree that describes its position relative to nearby trees.
Then, as you travel along, the robot drives up to a tree and finds a "signature" for that tree, and you find all the trees on the map that "match" that signature.
If only one unique tree on the map matches, then the tree the robot is looking might be that tree on the map (yay, you know where the robot is) -- put down a weighty but tentative dot on the map at the robot's relative position to the matching tree -- the tree the robot is next to is certainly not any of the other trees on the map.
If several of the trees on the map match -- they all have the same non-unique signature -- then you could put some less-weighty tentative dots on the map at the robots position relative to each one of them.
Alas, even if find one or more matches, it is still possible that the tree the robot is looking at is not on the map at all, and the signature of that tree is coincidentally the same as one or more trees on the map, and so the robot could be anywhere on the map.
If none of the trees on the map matches, then the tree the robot is looking at is definitely not on the map. (Perhaps later on, once the robot knows exactly where it is, it should start adding these trees to the map?)
As you drive down the path, you push the dots in your estimated direction and speed of travel.
Then as you inspect other trees, possibly after driving down the path a little further, you eventually have lots of dots on the map, and hopefully one heavy, highly overlapping cluster at the actual position, and hopefully each other dot is an easily-ignored isolated coincidences.
The simplest signature is a list of distances from a particular tree to nearby trees.
A particular tree on the map is "matched" to a particular tree in the forest when, for each and every nearby tree on the map, there is a corresponding nearby tree in the forest at "the same" distance, as far as you can tell with your known distance and angular errors.
(By "nearby", I mean "close enough that the robot should be able to definitely confirm that the tree is actually there", although it's probably simpler to approximate this with something like "My robot can see all trees out to a range of R, so I'm only going to bother even trying to match trees that are within a circle of R*1/3 from my robot, and my list of distances only include trees that are within a circle of R*2/3 from the particular tree I'm trying to match").
If you know your north-south orientation even very roughly, you can create signatures that are "more unique", i.e., have fewer spurious matches on the map and (hopefully) in the real forest.
A "match" for the tree the robot is next to occurs when, for each nearby tree on the map, there is a corresponding tree in the forest at "the same" distance and direction, as far as you can tell with your known distance and angular errors.
Say you see that tree "Fred" on the map has another tree 10 meters in the N to W quadrant from it, but the robot is next to a tree that definitely doesn't have any trees at that distance in the N to W quadrant, but it has a tree 10 meters away to the South.
In that case, then (using a more complex signature) you can definitely tell the robot is not next to Fred, even though the simple signature would give a (false) match.
Another approach:
The "digital paper" solves a similar problem ... Can you plant a few trees in a pattern that is specifically designed to be easily recognized?