Пользователь
30,2
рейтинг
23 января 2013 в 23:41

Разработка → Напиши алгоритм для МКС и выиграй 10 тыс. долларов


Международная космическая станция

НАСА объявило конкурс на оптимизацию алгоритмов движения солнечных панелей для Международной космической станции. Конкурс ISS Longeron Challenge проводится совместно с порталом TopCoder.

На МКС размещено четыре пары крыльев с солнечными панелями. Каждое крыло (Solar Array Wings, SAW) состоит из двух гибких складных панелей и способно вращаться вокруг продольной оси благодаря независимым моторам Beta Gimbal Assembly (BGA). Вдобавок, каждая из двух групп панелей способна вращаться вдоль поперечной оси с помощью Solar Alpha Rotary Joint (SARJ).



Задача: как сгенерировать максимальное количество электричества, учитывая постоянное изменение положение станции относительно Солнца? Решение задачи должно содержать алгоритм, который рассчитывает оптимальное угловое позиционирование каждого из 10 элементов на схеме в каждый из 92 моментов времени. Вдобавок, разрешается менять ориентацию всей станции на небольшой угол (от 0 до 7 градусов, что является константой для всего витка).

Оптимальное позиционирование солнечных батарей — исключительно сложная задача, для решения которой нужно учесть несколько факторов:

1. Станция совершает один оборот вокруг Земли за 92 минуты.
2. Тени, которые панели отбрасывают друг на друга. При вращении крыла уменьшается отбрасываемая тень на соседнее крыло, но уменьшается и генерация электричества с этого крыла.
3. Функциональные ограничения механических конструкций.

Постановка задачи, конкретные параметры орбиты, углы относительно Солнца, формулы для расчёта напряжения на солнечных панелях, точные размеры панелей, тестер/визуализатор для проверки решений — всё это доступно сразу после регистрации в конкурсе.





Для победителей предусмотрен призовой фонд 30 тысяч долларов.
1-е место $10 000
2-е место $5000
3-е место $3000
4-е место $1750
5-е место $1500
6-е место $1250
7-е место $1000
8-е место $750
9-е место $500
10-е место $250
Плюс ещё $5000 за особые достижения.

Вдобавок к денежным призам, имеются бонусы:
  • 100 маек с символикой НАСА
  • пять стикеров, которые побывали на орбите
  • пять рекомендательных писем

Но самое главное не деньги, ведь ваш алгоритм будет работать на Международной космической станции!

Конкурс стартовал 16 января и продлится до 6 февраля 2013 года.

Анатолий Ализар @alizar
карма
749,5
рейтинг 30,2
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (81)

  • +31
    Отсюда:
    Competitors must be:
    (i) a U.S. citizen
    • +18
      Мда. Станция международная, а конкурс нет? :)
      • +4
        Вроде как нет. Я теперь перечитал ещё раз внимательнее, нашёл это: «(iv) a non-U.S. resident authorized in the country in which the member resides while participating in this Competition to perform services as an independent contractor.» (первый раз дочитав до U.S. citizen, подумал, что обязательно). Только что этот юридический термин значит — кто объяснит?
        • +1
          Я не очень силен в этих юридических штучках. Подозреваю, что они имели ввиду, что если человек имеет гражданство в той стране, в которой он проживает, то он может спокойно участвовать в конкурсе. К.О.

          An independent contractor is a natural person, business, or corporation that provides goods or services to another entity under terms specified in a contract or within a verbal agreement. Unlike an employee, an independent contractor does not work regularly for an employer but works as and when required, during which time he or she may be subject to the Law of Agency.
          • +2
            Сдается мне, что citizen != resident.
            Т.е. участник должен быть гражданином US, но может быть и нерезидентом (т.е. проживаюшим в другой стране, но с гражданством US).
            • +1
              Эти пункты независимы. Например, в правилах TopCoder Open 2012 есть ровно такие же строчки и там участвуют и проходят в финал люди со всего мира, в том числе нерезиденты США.
            • +1
              Правильно вам сдается, в общем случае резидент и гражданин это не одно и то же. Кроме того, резидентство бывает разное (например, налоговое). В данном случае речь идет об обычном резидентстве, которое обычно в законах определяется как место проживания.

              Далее, эти 4 пункта связаны отношением «ИЛИ», т.к. между iii и iv стоит «or». Т.е. достаточно быть кем-то из этого списка:

              1. Гражданин США
              2. Законный постоянный резидент США (т.е. обладатель «green card»)
              3. Временный резидент, беженец или обладатель законно полученного разрешения на работу в США, не ограничивающее выбор работодателя на территории США
              4. Нерезидент США, имеющий право заниматься деятельностью приносящей доход в стране резидентства. Т.е. необязательно быть даже ЧП, т.к. работать по разовому договору подряда имеют право все граждане РФ.
              • +1
                Хм, а у нас вроде как нельзя если имееш постоянное место работы.
                Самозанятое лицо — налогоплательщик, который является физическим лицом — предпринимателем или осуществляет независимую профессиональную деятельность при условии, что такое лицо не является работником в пределах такой предпринимательской или независимой профессиональной деятельности
                перевод by google
                • 0
                  Никогда этим аспектом украинских законов не интересовался, но по-моему вывод у вас неправильный. Можно выполнять разовые работы по контракту или иметь ЧП одновременно с постоянным местом работы. Просто если есть постоянное место, то вы уже больше не «самозанятое лицо», а, видимо, «наемный работник».
                  • 0
                    Возможно, я на истину не претендую… Только тогда не совсем понятно как налоги платить ))
                    • +1
                      Налог платится, как для дополнительного иностранного источника дохода физлица (та же статья, что и, к примеру, проценты по вкладам в иностранных банках). В РБ — это 12% в конце отчетного периода, т.е. в начале следующего года.
              • 0
                я думаю тут отфильтровывают страны где нет возможности легально выплатить призовые деньги.
        • +2
          ЧПшником вам надо быть
    • –10
      Ализар, такой Ализар. :)
      • +6
        Нет, это я ошибся, прошу прощения за поспешный комментарий. Изменить уже поздно…
      • +17
        Что-то я как ни зайду в новости от alizar — всегда вижу этот комментарий.
        • +11
          Ну так ализар же, что вы хотели.
    • +5
      Вообще-то это только один из 4 пунктов:
      Competitors must be:

      (i) a U.S. citizen,
      (ii) a lawful permanent resident of the U.S.,
      (iii) a temporary resident, asylee, refugee of the U.S., or have a lawfully issued work authorization card permitting unrestricted employment in the U.S., or
      (iv) a non-U.S. resident authorized in the country in which the member resides while participating in this Competition to perform services as an independent contractor.

      A Competitor is not eligible for this Competition if he/she is a resident of the Quebec province of Canada, Iran, Cuba, North Korea, Sudan or Syria. In addition a Competitor is not eligible for this Competition if the Competitor is on the Specially Designated National list promulgated and amended, from time to time, by the United States Department of the Treasury.


      Только 4 пункт непонятный. Что они имеют в виду этим своим «independent contractor»?
      И чем им Квебек не угодил? :)
      • +3
        Может имеется в виду, что согласно вашему текущему положению, вам разрешено работать на другого работодателя. Ну или как-то так. Например, работникам прокуратуры, насколько я знаю, нельзя получать какой-либо другой доход, кроме оклада. Они как раз бы сюда не подошли.
        • 0
          Да, если перепрочесть оригинальное предложение — это кажется самым подходящим объяснением этой формулировки.
      • 0
        Возможно они это имеют ввиду «Independent contractors are usually paid on a freelance basis»?
        Это wiki так говорит: http://en.wikipedia.org/wiki/Independent_contractor
      • 0
        «independent contractor» можно перевести как «подрядчик» (не зависимый от вашей организации)
      • 0
        Это не Квебек им не угодил, а они Квебеку. Насколько я помню, по законам Квебека любые соревнования, проводящиеся там, обязаны предоставлять условия и на английском, и на французском. ТопКодер, понятно, переводом на французский не заморачивается :-)

        Independent contractor — например, на H1-B (или H4) визе в США нельзя зарабатывать деньги на ТопКодере, это примерно на такой случай для других стран.
      • НЛО прилетело и опубликовало эту надпись здесь
    • –1
      Могу вам помочь обойти это. Это не проблема.
      • 0
        Чорт, а я зарегистрироался со своим адресом — и теперь не смогу участвовать. Пичаль…
  • –9
    Если ты возьмёшь билетов пачку, то получишь… водокачку.
  • +1
    Но самое главное не деньги, ведь ваш алгоритм будет работать на Международной космической станции!

    А если в процессе работы алгоритма станция из-за него грохнется? :-)
    • НЛО прилетело и опубликовало эту надпись здесь
      • +3
        Агоритмиста возьмут не только в роскосмос, но и энергетики, и даже в сельское хозяйство.
        • +2
          Ну и в мостоотряд до кучи.
      • –1
        Мне кажется сам алгоритм уже сможет работать в Роскосмосе вместо людей) Не в обиду сотрудникам Роскосмоса)
  • +1
    А что, ганатируется, что если вы победите, то алгоритм так сразу и запустят на МКС?) Конкурс, конечно, привлекательный, но мне кажется что больше шансов у специализированных компаний и/или институтов, где этим профессора занимаются… Хотя будет интересно посмотреть решения и что в итоге будет реализовано. С другой стороны вспоминается относительно недавний конкурс про составить документ пропущенный через шредер)
    • +5
      На такие мысли всегда есть поговорка:
      Ковчег построил любитель, профессионалы построили «Титаник».
      • 0
        Да на самом деле можно вспоминать примеры вроде создания повсеместного Линукса в каком-то роде неизвестным любителем. Посмотрим что выйдет у «любителей» в космосе.
    • 0
      С другой стороны вспоминается относительно недавний конкурс про составить документ пропущенный через шредер)

      Можно ссылочку?
  • +4
    Хочу майку NASA!
    • 0
      Не знаю, как сейчас, но в одном из прошлых контестов от наса получить футболку было относительно просто. Мне потребовалось пару часов на обдумывание и осмысление задачи, еще 3-4 часа на кодирование, часов 10-15 на доработку и отладку алгоритмов. Учитывая, что контест идет 3 недели, получается в среднем где-то час в день. Учитывая, что очень успешно думать можно в дороге или за обедом, не так уж много. Самое сложное — первый эпап: понять задачу и написать сколько угодно тупое, но работающее решение. С этим каркасом дальше двигаться намного проще и интереснее. После каждой модификации алгоритма ждешь результатов с замиранием сердца!

      По поводу футболок, кстати. Когда мне присылали, я написал размер, посмотрев его на текущей (видимо, китайской) футболке. Получив в итоге нормальный американский XL обнаружил, что меня туда спокойно влезет три штуки по ширине :)
  • +2
    Не очень верится, что NASA не может решить эту задачу, может сотрудников ищут?
    • 0
      Вы подозреваете НАСА в скрытом умысле?
    • +4
      Конечно сотрудников.
      Top Coder это очень специфическое кадровое агенство. Агенство которое проводит конкурсы.

      Может надеются на удачу получить алгоритм чуть лучше чем у них, хотя маловероятно, там же перебор совсем небольшой выходит (для их то мощностей)
      • 0
        Ну как сказать: из сотен предложенных идей всегда можно взять что-нибудь полезное, может это будет не алгоритм целиком, а какие-то отдельные пункты…
      • НЛО прилетело и опубликовало эту надпись здесь
  • +18
    Howard Wolowitz по идее должен победить.
  • 0
    При регистрации на topcoder:
    Your password may contain only letters, numbers and -_.{}[]()
    Мда…
    • 0
      password.goes.here()
  • 0
    А какой собственно прирост в процентах, попадания солнечных лучей на модули они хотят получить?
    • 0
      Наибольший, который получится :)
  • +1
    Если я правильно понял постановку задачи, то им нужен не алгоритм, а 92 * число_степеней_свободы чисел, которые будут задавать положение станции в каждую минуту этого 92-минутного цикла. Имхо, такие числа проще подобрать каким-нибудь алгоритмом случайного поиска вроде генетики, чем пытаться написать алгоритм для их рассчёта.
    • +2
      это если бы земля не вращалась по эллиптической орбите вокруг солнца.
      Если учитывать это вращение, то каждые сутки уникальны.
    • +1
      Как мне видится, возможно решение данной задачи минимум 2 основными способами:
      1. Функция от времени.
      Когда имеем систему уравнений для вычисления положения панелей в зависимости от положения станции относительно Солнца (не Земли). В ней надо будет учесть и движение Земли вокруг Солнца и и изменение орбиты самой станции и еще куча факторов. В результате, формула (алгоритм) получится очень даже громозкой. Из-за изменения орбиты станции или иных факторов ошибки будут накапливаться, в результате достаточно часто придется производить поправки и вносить новые коэффициенты в ту систему уравнений.
      2. Функция от выработанной энергии.
      Если грубо — ищем максимум выработки электроэнергии в текущий момент времени. Здесь имеем другие проблемы. На поворот панелей требуется энергия, тратим моторесурс поворотных механизмов панелей, на поворот панелей также требуется время, что добавляет головной боли. В случае всяких стыковок надо будет отключать систему дабы она не мешала — а то в ответственный момент решит повернуть станцию на разрешенные 7 градусов и стыковка сорвется (в лучшем случае).
      Далее, поиск максимума при 15-20 степенях свободы — та еще задача. Тем более, что максимум выработки электроэнергии на части панелей не будет означать суммарный максимум по всей системе.
      Есть еще пролет станции в тени Земли, когда выработка электроэнергии стремится к нулю и она не зависит от положения панелей. В результате система может стать нестабильной, и начать крутить панелями почем зря.

      Мне видится, что нужен комбинированный алгоритм из описанных мной двух вариантов.
      Устанавливаем панели как функцию от времени и потом поиск локального максимума в небольших пределах.
      • +1
        Крутить станцию там не предлагают — только задать постоянный угол полёта.
        По идее, должна быть функция от направления на солнце. Тогда изменение орбиты не помещает.
        • 0
          1. По заданию разрешено отклонять станцию в пределах 7 градусов.
          2. МКС крутится вокруг себя относительно солнца. (В треде звучало, что станция обращена одной стороной к земле)
          Так, что траектория полета станции относительно солнца получается достаточно замысловатая. Если рассматривать станцию как точку, что ничего сложного на самом деле нет, если же рассмотреть станцию с точки зрения плоскости каждой солнечной панели, то получается не очень и просто.
          При рассмотрении задачи в таком разрезе, то надо найти максимум суммарной плоскости панелей при их расположении относительно солнца под наиболее прямым углом.
          • +1
            1.
            Вдобавок, разрешается менять ориентацию всей станции на небольшой угол (от 0 до 7 градусов, что является константой для всего витка)

            Так что стыковка не сорвётся.
            2. Есть станция, и есть направление на солнце относительно станции в данный момент. Где находится земля, и где находится станция — не важно. Если она в тени земли, то крутить солнечными батареями всё равно бессмысленно. Достаточно просто отключать всю систему позиционирования, пока станция в тени.
  • +26
    Давайте упростим задачу…

    image

    Соответствующее звуковое сопровождение:
    http://www.youtube.com/watch?v=u68KoSujmsg
    • 0
      Аккуратно надо, а то поворот на неправильный угол и «жизнь великого рейнджера закончилась».
  • +1
    «Напиши алгоритм для МКС и утопи ее в океане»
    • +4
  • +5
    В принципе, надо знать сколько требуется энергии для поворота этих панелей и самой МКС.
    Как помню, МКС всегда повернута одной стороной к земле, поэтому может выйти то, что выгодней даже будет некоторые панели держать под одним углом, другие под другим и только корректировать по мере поворота, не делая больших разворотов (т.е. максимум поворот плюс-минус 45 градусов)
    • +2
      И правда, нужно учитывать затраты энергии на поворот солнечных батарей и изменение угла станции (в пределах этих 7-ми градусов). Правда, я думаю сложнее всего будет учитывать изменение падения тени от одних батарей на другие.
  • +2
    Я, конечно, по большей части теоретик, но что мешает решать подобные задачи оверкиллом?
    Посчитать все возможные положения паналей для всех углов станции относительно солнца (с подходящей дискретизацией), выбирать оптимальные на следующие сутки по полученным таблицам? Ну т.е. сперва все посчитать, чтобы потом быстро решать.
    Как мне кажется, мощности, чтобы такое посчитать, вполне существуют.
    В крайнем случае сделать распределенно, т.к. уже преценденты есть.
    • +2
      Похоже на мысли первокурсника о шахматах.

      А вы на топкодере что-нибудь решали вообще? Или codeforces? Или хотя бы projecteuler?
      • +5
        Решал достаточно много на ACM (вроде в двухсотке верхних был) в свое время, считается?

        Насчет первокурсника и шахмат — Deep Blue, с его всего 200 милионов позиций в секунду победил человека, а там перебор был не на последнем месте.

        Теперь если прикинуть, что будем считать с дискретностью 10 градусов станции относительно солнца.
        Примерно получается: 36 * 36 * 36 = 46656 положений станции относительно солнца.
        Для каждого положения надо найти оптимальное положение солнечных панелей. Это с той же дискретностью
        36 * 27 * 27 * 27 * 27 * 9 * 9 * 9 * 9 = 125524238436 вариантов на каждое положение станции.

        Всего надо посчитать энергию для 5856458868470016 расположений станции + панелей. Пусть обсчет положения станции равнозначен расчету позиции в шахматах. Это получается что Deep Blue, который явно уже устарел, посчитал бы все это за 338 дней. Вот и готовы исходные таблицы, по которым с точностью до 10 градусов можно посчитать как вращать панелями.

        Привлеките распределенные вычисления, как это делают всякие seti@home и посчитайте с дискретностью 1 градус, если надо или 0.1 градус.

        Мне просто не понятно, почему в наш век технологий и сверхмощных вычислительных мощностей нельзя использовать такой достаточно примитивный подход «в лоб», просто при помощи оверкила.
        • 0
          Кстати, вспомнилась одна из задач на ACM где мое решение было самым быстрым/качественным.

          Не вспомню точно, что надо было считать, но всего различных вариантов исходных данных было порядка 100 000, из которых только 10 000 не успевало по времени перебором. Решение состояло в таблице для этих 10 000 вариантов, из которой брался правильный ответ, если исходные данные не брались перебором (ограничение по времени на все решения). Таблицу посчитал все тем же перебором где-то за недельку на трех компах, к которым имел доступ.

          Алгоритм более быстрый тогда придумать не получилось, а решить хотелось сильно.
        • +1
          Это только расчет энергии в статическом положении. Нужно еще минимизировать количество поворотов батарей при переходе станции из одного положения в другое, чтобы не тратить лишнюю энергию и не расходовать моторесурс приводов.
          • 0
            Поскольку пока станция крутится ее положение фиксировано +-7 градусов, то имеем не так уж много переменных, только положения панелей. Эта задача скорее всего решается динамическим (memory-cpu trade off) программированием, учитывая что всего 92 шага.
    • 0
      Чтобы все не вычислять, можно еще притянуть генетические алгоритмы.
  • 0
    Когда в видео говорят про «more science from more scientists» в России учёных нет.
    • –7
      image
  • +4
    А подсолнухи как-то без математики справляются…
    • 0
      Подсолнухи друг друга не затеняют, в отличие от батарей МКС.
      • 0
        Да ладно, почему это вдруг?
  • 0
    А там не предусмотрено на концах солнечных батарей маленьких сенсорных сборок, по 5 ортогональных фотодиодов на каждом, чтоб текущее направление на солнце узнавать гарантированно и напрямую, а не вычислять заранее?..
    • 0
      Проблема ведь не в том, что бы найти солнце, а в том, что батареи друг друга затеняют.
  • +6
    Чтобы понять суть задачи, надо обратиться к первоисточникам — автор не упомянул множество деталей, в которых вся соль.

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

    Плюс, напрямую алгоритм использоваться не будет, можно не бояться :-) Модель ISS в задаче сильно упрощена.
    Зато после завершения конкурса от победителя будет требоваться объяснить его работу, после чего, в лучшем случае, этот подход будет использован программистами NASA с применением более сложной и реалистичной модели.

    Если хотите, я выложу куда-нибудь полный текст задачи; только надо проверить сначала, что это разрешается правилами topcoder.
    Просто интересно почитать некоторые детали устройства ISS, в конце концов :-)
    • +1
      Объяснять попросят после выбора победителя? А выбирать будут самое непонятное, что-ли?

      А полный текст задачи — это очень интересно, давайте!
      • 0
        Это же спортивное программирование, ожидать идеального кода не приходится.
        Ну и какой-нибудь умный алгоритм тоже неплохо объяснить.

        PDF с полным описанием сейчас будет; правда, с watermark-ами ;(
  • 0
    Я давно не выкладывал никуда файлов, надеюсь, Яндекс.Диск считается достаточно ок.

    docviewer.yandex.ru/?c=510314a61c66&url=ya-disk%3A%2F%2F%2Fdisk%2FTopCoder_ISS.pdf&name=TopCoder_ISS.pdf
    docviewer.yandex.ru/?c=510314cdead3&url=ya-disk%3A%2F%2F%2Fdisk%2FTopCoder_ISS_tester.pdf&name=TopCoder_ISS_tester.pdf

    Основная дока и описание, как использовать локальную утилиту для тестирования алгоритма. Прямо рисуется простенькая моделька станции, крутится, показывает тени, собранную энергию, занятно)
  • 0
    Забавный нюанс — писать решения на Topcoder можно только на C++, Java и Python (версии 2.4, фу), но условиями этого конкурса допускается использовать вспомогательные скрипты/программы/утилиты на любом языке, если они ваши или opensource.
    Так как в этой задаче все варианты входных значений известны заранее (либо прямо перечислимы, либо известны допустимые диапазоны), то можно посчитать ответы для всех видов инпута в чем угодно, а скрипт на питоне будет только отдавать нужные данные :-)

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