Математический форум Math Help Planet
http://mathhelpplanet.com/

Алгоритм объединения кластеров маяков в единую группу?
http://mathhelpplanet.com/viewtopic.php?f=33&t=35755
Страница 1 из 1

Автор:  marvelmind [ 28 сен 2014, 13:04 ]
Заголовок сообщения:  Алгоритм объединения кластеров маяков в единую группу?

Добрый день, коллеги,

Спасибо за интерес к заданию.

Нужно написать алгоритм объединения нескольких кластеров ультразвуковых маяков в одну группу:
- Например, есть 5 ультразвуковых маяков, каждый из который, слышит другого – Кластер 1
- Маяки могут определять взаимные расстояния и формировать карту своего расположения друг относительно друга - трилатерация
- И есть другие кластеры маяков
- Но кластера пересекаются друг с другом лишь в двух-трех маяках – они общие для этих кластеров. Иногда, пересекаются в большем количестве маяков, но не менее трех. Если возможен алгоритм с двумя общими маяками – еще лучше.

Нужно написать алгоритм устойчивого объединения кластеров маяков в одну карту, учитывая физику работы ультразвуковых маяков и их ограничения по точности определения расстояния и так далее.

Изображение

Высылаю скан наброска. Большинство ограничений и схема расположения маяков описано на наброске. Если остались вопросы, пожалуйста, задавайте.

Кластера могут пытаться зеркалиться, но эта проблема может решаться двумя способами, как минимум:
1) Кластера могут объединяться в бублик, как показано на наброске. А в бублик они могут объединиться только одним путем
2) У маяков есть компас. Он не сильно точный и подвержен помехам, иногда, когда рядом металлы, но обнаружить слева ли восток или справа - может. А это позволит устранить зеркальность

Все маяки общаются между собой по радио через роутер. То есть, все данные (взаимные расстояния, ориентация по компасу) из одного маяка доступны центральному роутеру, который и собирает карту из кусков в единое целое. Вот этот алгоритм в роутере для устойчивой сборки карты из кластеров маяков и нужно написать.

Сейчас уже есть работающие алгоритмы, но они не устойчивы. Иногда, соберется карта, а, иногда, и нет.
Из известных проблем:
1) Маяки на одной прямой - проблема зеркала
2) Чем больше маяков, тем точнее должна собираться карта, потому что больше данных и они друг друга должны дополнять и уточнять. А, на практике, если какой-то из маяков получает отраженный сигнал - не прямой, то он выдает данные, которые не укладываются в общую картинку. Например, маяк за стенкой от другого маяка и не должен видеть его. Но по отраженному сигналу он видит (слышит). И расстояние получается 10 метров. Но прямое расстояние между маяками через стену - 1 метр. Система получает эти данные и сходит с ума - не укладывается в алгоритм.
Но данные с маяков избыточные. И без этого маяка можно было бы построить карту. Так вот, алгоритм должен обнаруживать, что данные с какого-то маяка неточные или противоречащие данным с других маяков и не принимать их во внимание.

Если нужно накладывать какие-то специальные ограничения, чтобы алгоритм работал, сообщайте. Обсуждаемо. Часть ограничений может быть приемлема, а часть - нет. Зависит от сути ограничений.

Готов оплатить работу, если предложенный алгоритм заработает на реальных маяках.

Спасибо.

BR,
Maxim

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/