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

Высылаю скан наброска. Большинство ограничений и схема расположения маяков описано на наброске. Если остались вопросы, пожалуйста, задавайте.
Кластера могут пытаться зеркалиться, но эта проблема может решаться двумя способами, как минимум: 1) Кластера могут объединяться в бублик, как показано на наброске. А в бублик они могут объединиться только одним путем 2) У маяков есть компас. Он не сильно точный и подвержен помехам, иногда, когда рядом металлы, но обнаружить слева ли восток или справа - может. А это позволит устранить зеркальность
Все маяки общаются между собой по радио через роутер. То есть, все данные (взаимные расстояния, ориентация по компасу) из одного маяка доступны центральному роутеру, который и собирает карту из кусков в единое целое. Вот этот алгоритм в роутере для устойчивой сборки карты из кластеров маяков и нужно написать.
Сейчас уже есть работающие алгоритмы, но они не устойчивы. Иногда, соберется карта, а, иногда, и нет. Из известных проблем: 1) Маяки на одной прямой - проблема зеркала 2) Чем больше маяков, тем точнее должна собираться карта, потому что больше данных и они друг друга должны дополнять и уточнять. А, на практике, если какой-то из маяков получает отраженный сигнал - не прямой, то он выдает данные, которые не укладываются в общую картинку. Например, маяк за стенкой от другого маяка и не должен видеть его. Но по отраженному сигналу он видит (слышит). И расстояние получается 10 метров. Но прямое расстояние между маяками через стену - 1 метр. Система получает эти данные и сходит с ума - не укладывается в алгоритм. Но данные с маяков избыточные. И без этого маяка можно было бы построить карту. Так вот, алгоритм должен обнаруживать, что данные с какого-то маяка неточные или противоречащие данным с других маяков и не принимать их во внимание.
Если нужно накладывать какие-то специальные ограничения, чтобы алгоритм работал, сообщайте. Обсуждаемо. Часть ограничений может быть приемлема, а часть - нет. Зависит от сути ограничений.
Готов оплатить работу, если предложенный алгоритм заработает на реальных маяках.
Спасибо.
BR, Maxim
|