面白そうだったのでFLLロボットゲームにおける自分なりの考察をしました。

※あくまで帰宅部の何もすることない暇人による「暇つぶし考察」です。
※筆者はFLL出ません。(キットもチームもありません[泣])
※計算量はオーダー記法を用いて表しています。

FLL 考察

考察内容

・大会についての考察
・使用言語
・ミッション考察
・ロボット構造の考察
・立ち回りの最適化
・最後に

1.大会についての考察

この大会の構造は、ベースポイント＋ボーナスポイントというものであることを踏まえて、重要だと思ったことを挙げる。

・ミッションの正確な読み取り
かなり複雑な処理が行われるので、マップやミッションを正確に読み取るのが大事。また、この時、ミッションを「縦に押す」「横に押す」「押し込む」などに分類し、さらに処理の向きを考えることが大事である。

・効率的なシミュレーション
UnityやUnrealEngineなどを用いて効率的なシミュレーションを行う。一応物理演算機能はあるが、そこまでの正確性はないのであくまで参考程度に。

・ミッション処理順の最適化
時間が短いので、ミッションの処理順を最適化しなければならない。例えばマップのミッションの位置を重みつき平面グラフとしてとらえ、ダイクストラ法などを使って距離を最適化する考え方は有効かもしれない、と思っていた時期もあった。

・ロボットの操作性
当たり前のことだが、計算量は最適化されることが望ましい。ロボットの行動を最大0.1秒以内で制御できるプログラムを作成しなければ、場外に出てしまい精密トークンを失ってしまう可能性がある。具体的には、一連の処理が、O(10^7)以下の計算量であることが望ましい。

・例外処理の切り捨て
時間が短いので、実験を見ながら例外処理の切り捨てを行わければならない可能性がある。例外処理を切り捨てるときは、上のようにミッションを「縦に押す」「横に押す」「押し込む」などに分類したとき、最も少ないものから切り捨てていくとよい。

これらは、今回の大会に共通し、ロボットゲーム以外においても通じる考え方であるため、ぜひ参考にしてほしい。

2.使用言語

何があるのかもライブラリが用意されているのかもわからないが、以下3つの言語をお勧めする。微妙に(大体10倍ぐらい)速度は違うが、どれも大会に以上をきたすものではない。
・C++
比較的処理が早く、書きやすく学びやすい言語である。入門教材としては、Atcoder社のAPG4bが非常に良い。
https://atcoder.jp/contests/APG4b

・Python
インタプリタ言語なので処理が少し遅いが、学びやすく書きやすい。そして何よりライブラリがありそう。入門教材としては、同じくAtcoder社のAPG4bが非常に良い。
https://atcoder.jp/contests/APG4bPython

・ブロック系のやつ
めちゃくちゃ処理が遅そうだが、別に以上をきたすほどでもないと思う。誰でも書けるため、あるのならこれが一番いいかも。

3.ミッション考察

※項目の最初に出てくるミッションをデフォルト、その他を順にボーナスミッションとして扱っています。(Youtubeでルールを見ただけなのでここらへんあまりわかりませんでした)
1.Coral Nursery
・Defalt
サンゴをひっかける。円盤にロボットをぶちこむ「すくいあげ」と突起にひっかける「押しあげ」の実装が必要。
・B1
「すくいあげ」と「押しあげ」を同時にしてかつDefaltよりも精密な処理が求められる。実装の割に得点効率が悪い。
・B2
「押しあげ」の逆をすればいいので、Defaltの実装ができればできる。

2.Shark
・Defalt
同じく「押しあげ」の逆をすればいいだけ。
・B1
サメを後ろに押し込む技術が必要。これには、「横押し」と「押し込み」が必要。実装の割に得点効率が悪い。

3.Coral Reef
・Defalt
かなり強めの「押し込み」が必要。また、フィールド端ギリギリにあるので、横から押し込むなら注意がいる。得点効率がいい。
・B1
ルートを工夫して実装しなければならない。実装の割に得点効率がくそ悪い。

4.Scuba Diver
・Defalt
1と同様、「すくいあげ」と「押しあげ」で実装できる。
・B1
「すくいあげ」と「押しあげ」に加え、同時に移動処理を行わければいけない。実装がめちゃくちゃムズイが、20点あるので、実装したいところではある。

5.Angler Fish
かなり下段での「横押しこみ」が必要。汎用性の高い実装かつ点数がくそでかいので、実装はほぼマスト。

6.Paise the Mast
「押しあげ」処理が必要。点数がくそでかい。

7.Kraken's Treasure
「押しあげ」と「回収」を同時に行う必要がある。実装の割に得点効率が少し悪い。

8.Artificial Habitat
1と同様、「すくいあげ」「押しあげ」処理での実装。かなり実装難度が高い。ダメ元で実装しよう。

9.Unexpected Encounter
・Defalt
「押し込み」が必要。かなり簡単だが、オブジェクトがロボットに落ちてくるケースは避けたい。
・B1
サメと同じ理論。一応「押し込み」のみで実装できる。

10.Send over the Submersible
・Defalt & B1
かなり精密な「押し上げ」が必要。ラストギリギリに行くことが推奨される。

11.Sonar Discovery
・Defalt
「横押し込み」の技術が必要。モーター消費必須。
・B1
さらに「横押し込み」の技術が必要。時間かければできる。

12.Feed the Whale
実装難度異常値。「すくいあげ」「ホールド」「落とす」の3処理が必要でかつほぼ同時処理。これやるぐらいならロボちっちゃくしてデザインで点とるほうがいい。

13.Change Shipping Lanes
「押しあげ」の極み。完全究極体。「押しあげ」技術をここまで持っていきたい。

14.Sample Collection
・Defalt　押すだけ。
・B1
「すくいあげ」「押しあげ」をやりながら、「移動」または「回転」が必要。
・B2
「すくいあげ」をやりながら、「移動(バック)」が必要。実装が割とムズイと思われる。
・B3
多分「横押し込み」で可能。だとしたら、実装の割に点数効率がよい。
・B3.1
無理ゲー。まじでどうするんだよこれ

15.Research Vessel
・Defalt
今までの処理に加えて長めの「ホールド」が必要。
・B1
「押し込み」の処理をかなり正確に。こっちだけ狙うのもあり。

4.ロボット構造の考察

・モーターの使いどころ
モーターの数が決まっているのがかなり厄介。1つのモーターで2つ以上の仕事を併用する方法を考えよう。

・ミッションでの汎用処理
「移動(バック)」「回転」「押しあげ」「すくいあげ」「押し込み」「横押し込み」「ホールド」

・ロボットデザインの評価性
できるだけコンパクトで、機能性の充実したロボットが求められる。汎用性の低い機能は容赦なく捨てましょう。

・プログラム
競技中与えられるクエリ(?)に爆速で答えられるプログラムを作る。また、各ミッションの順番が決まったら、区間ごとのレスポンスタイム(レスポンスタイムってこういうことでも使うのか?)を細かく計測しよう。計算量も一応意識する。
(IT系の用語使い方むずかしい[小言])

5.立ち回りの最適化

今回のミッションはオブジェクトに対してミッション発動位置がいくつかあるので、各ミッションオブジェクトまでの経路を重みつきグラフ化してダイクストラ法などを使って最短経路を求めるやり方はうまくいかなさそうだ。UnityやUnreal-Engineなどを用いて大量にシミュレーションを重ねよう。AIを使って最適化処理を見つけ出すのもありだ。

・章が短すぎるのでプログラムのサンプルのせます。
例)以下のような辺があり、頂点数が15の重み付グラフで、頂点1から頂点15に行くときの重みの総和の最小値をダイクストラ法で求めるプログラム。(C++)
1 - 3 (重み: 3)
3 - 5 (重み: 5)
5 - 7 (重み: 2)
7 - 9 (重み: 4)
9 - 11 (重み: 6)
11 - 13 (重み: 3)
13 - 15 (重み: 7)
15 - 2 (重み: 1)
2 - 4 (重み: 2)
4 - 6 (重み: 4)
6 - 8 (重み: 5)
8 - 10 (重み: 6)
10 - 12 (重み: 3)
12 - 14 (重み: 2)
14 - 1 (重み: 4)

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

const int INF = numeric_limits<int>::max();
struct E { int to, w; };
void dijk(const vector<vector<E>>& g, int s, vector<int>& d) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    d[s] = 0;
    pq.push({ 0, s });
    while (!pq.empty()) {
        int cd = pq.top().first, u = pq.top().second;
        pq.pop();
        if (cd > d[u]) continue;
        for (const E& e : g[u]) {
            if (d[u] + e.w < d[e.to]) {
                d[e.to] = d[u] + e.w;
                pq.push({ d[e.to], e.to });
            }
        }
    }
}

int main() {
    int n = 15;
    vector<vector<E>> g(n);

    // グラフの辺を追加
    g[0].push_back({ 2, 3 });
    g[1].push_back({ 3, 2 });
    g[2].push_back({ 4, 5 });
    g[3].push_back({ 5, 4 });
    g[4].push_back({ 6, 2 });
    g[5].push_back({ 7, 5 });
    g[6].push_back({ 8, 4 });
    g[7].push_back({ 9, 6 });
    g[8].push_back({ 10, 6 });
    g[9].push_back({ 11, 3 });
    g[10].push_back({ 12, 3 });
    g[11].push_back({ 13, 2 });
    g[12].push_back({ 14, 7 });
    g[13].push_back({ 0, 4 });
    g[14].push_back({ 1, 1 });
    vector<int> d(n, INF);
    dijk(g, 0, d);
    //これが最小値
    cout << d[14] << endl;
    return 0;
}

最後に

・これが自分なりの考察です。改善案死ぬほどあるのでこれを参考にして残りは頑張ってください。ていうか日程確認したらもう地区予選終わってた...