This paper proposes a control method for the multi-agent pickup and delivery problem (MAPD problem) by extending the priority inheritance with backtracking (PIBT) method to make it applicable to more general environments. PIBT is an effective algorithm that introduces a priority to each agent, and at each timestep, the agents, in descending order of priority, decide their next neighboring locations in the next timestep through communications only with the local agents. Unfortunately, PIBT is only applicable to environments that are modeled as a bi-connected area, and if it contains dead-ends, such as tree-shaped paths, PIBT may cause deadlocks. However, in the real-world environment, there are many dead-end paths to locations such as the shelves where materials are stored as well as loading/unloading locations to transportation trucks. Our proposed method enables MAPD tasks to be performed in environments with some tree-shaped paths without deadlock while preserving the PIBT feature; it does this by allowing the agents to have temporary priorities and restricting agents' movements in the trees. First, we demonstrate that agents can always reach their delivery without deadlock. Our experiments indicate that the proposed method is very efficient, even in environments where PIBT is not applicable, by comparing them with those obtained using the well-known token passing method as a baseline.

We propose a distributed method for a multi-agent pick-up and delivery problem with fluctuations in agent movement speeds while agents perform planning, detect and resolve conflicts (collisions) between the plans, and execute actions in the plans in a distributed manner. Our study assumes that the robot's movement speed can fluctuate, owing to various factors, thus delaying their scheduled tasks. Such delays can rapidly cause other agent conflicts to cascade and render long-term plans useless. Our proposed method allows each agent's plans to be executed and modified using an advanced short-sighted conflict resolution mechanism. Hence, although an agent attempts to follow its given sequence of actions, it performs each one after carefully checking for any conflict in the next few steps. Our method is fully distributed and works effectively, even when the number of task endpoints, which are the pick-up and delivery locations, is small and the agents are concentrated. We experimentally confirm that our method works efficiently without collisions in environments having agent speed fluctuations and deadlocks using example problems from robot movement in a construction site. Further, we compare the performance of our method with that of the baseline method.

The multi-agent pickup and delivery (MAPD) problem, in which multiple agents iteratively carry materials without collisions, has received significant attention. However, many conventional MAPD algorithms assume a specifically designed grid-like environment, such as an automated warehouse. Therefore, they have many pickup and delivery locations where agents can stay for a lengthy period, as well as plentiful detours to avoid collisions owing to the freedom of movement in a grid. By contrast, because a maze-like environment such as a search-and-rescue or construction site has fewer pickup/delivery locations and their numbers may be unbalanced, many agents concentrate on such locations resulting in inefficient operations, often becoming stuck or deadlocked. Thus, to improve the transportation efficiency even in a maze-like restricted environment, we propose a deadlock avoidance method, called standby-based deadlock avoidance (SBDA). SBDA uses standby nodes determined in real-time using the articulation-point-finding algorithm, and the agent is guaranteed to stay there for a finite amount of time. We demonstrated that our proposed method outperforms a conventional approach. We also analyzed how the parameters used for selecting standby nodes affect the performance.

Although the multi-agent pickup and delivery (MAPD) problem, wherein multiple agents iteratively carry materials from some storage areas to the respective destinations without colliding, has received considerable attention, conventional MAPD algorithms use simplified, uniform models without considering constraints, by assuming specially designed environments. Thus, such conventional algorithms are not applicable to some realistic applications wherein agents have to move in a more complicated and restricted environment; for example, in a rescue or a construction site, their paths and orientations are strictly restricted owing to the path width, and the sizes of agents and materials they carry. Therefore, we first formulate an N-MAPD problem, which is an extension of the MAPD problem for a non-uniform environment. We then propose an N-MAPD algorithm, the path and action planning with orientation (PAPO), to effectively generate collision-free paths meeting the environmental constraints. The PAPO is an algorithm that considers not only the direction of movement but also the orientation of agents as well as the cost and timing of rotations in our N-MAPD formulation by considering the agent and material sizes, node sizes, and path widths. We experimentally evaluated the performance of the PAPO using our simulated environments and demonstrated that it could efficiently generate not optimal but acceptable paths for non-uniform environments.

本研究ではmulti-agent pickup and delivery（MAPD）の拡張であるMAPD with time synchronization（MAPD-TS）問題を定式化する． MAPD-TSでは輸送エージェントの動きと，建設現場の異なるフロア間に資材を輸送するエレベータなどの外部エージェントの動きの同期を考慮した． 次に，不要な待ち時間を削減して全体効率を向上するため，エージェントによる自律的なタスク選択手法を提案する． MAPDは資材輸送などの応用の抽象化であり，それのみを考慮した閉じたシステムにおける効率化と衝突のない移動を目的とした研究が数多くある． しかし，建設現場などは孤立した閉じたシステムではないため，真の効率化達成にはエージェントは時に外部エージェントと同期しなければならず，MAPD-TSはこの状況の抽象化である． MAPD-TSのための提案手法では，エージェントは同期性向上のため，外部エージェントと接続された搬入出ポートへの到着時刻を近似的に推定し，次のタスクを選択する． 従来手法との比較により，提案手法がエージェントと外部エージェント両方の待ち時間を削減して，全体効率を改善できることを示す．

本研究では，MAPD 問題の制御手法である Priority Inheritance with BackTracking (PIBT) に暫時的な優先度を導入した拡張 PIBT を提案し，PIBT の基本的な性質を変えることなく適用環境の制約を緩めることで適用範囲を拡大すると共に，実験的にその効果を示す．PIBT 手法はステップことに優先度を計算し，その優先度の高いエージェントから順番に，次のステップでの移動先を確定させるアルゴリズムである．このアルゴリズムでは，行き止まりや袋小路のような形状を含むマップでは行き詰まり (デッドロック) が発生するため，環境にその発生を防ぐ制約を設けている．そこで本研究では，エージェントに通常の優先度に加えて暫時的な優先度を持たせ，更に不要な部分への移動を禁止する拡張を施し，先行研究で求められる条件を緩めても継続的な搬送ができることを述べる．よく知られた既存手法である Token Passing との比較実験を通し，その効率が優位であること，特に一般的な応用で想定されるような運搬箇所に集中や偏りがある場合にその効果が極めて高いことを示す．

近年，金融分野における機械学習に基づく定量的予測モデルの開発が活発化している．しかし，機械学習ベースの株価予測モデルは「市場の効率性」と「予測モデルの解釈可能性」の2つの課題により，実用化が困難である．これらの課題に対して，解釈性を担保しつつ短期的に高い予測精度のルールを進化的に実現するTrader-Company（TC）法がある．しかし，TC法はその性質上，市場レジームの急激な変化を考慮しないため，変化によって予測精度が悪化する可能性がある．そこで本研究では，レジームの変化に対する高いロバスト性を実現するため，Multiple-World Trader-Company法を提案する．提案手法では，TC法において単純で解釈可能な予測アルゴリズムであるTraderを管理するCompanyモデルを弱学習器として，レジーム単位で分割した学習データを複数Companyが個別に学習する．実データを用いた実証分析により，提案手法がベースライン手法と比較して良好な予測精度を達成することを示す．

本研究では迷路状の制限された環境でも輸送効率を向上するため，multi-agent pickup and delivery（MAPD）問題に対してグラフ理論を活用したデッドロック回避手法 standby-based deadlock avoidance（SBDA）を提案する．複数エージェントが衝突せずに資材を繰り返し回収・運搬する MAPD 問題が注目されているが，従来の MAPD アルゴリズムの多くは自動倉庫のような特別に設計されたグリッド状の環境を想定する．それらの環境にはエージェントが長時間滞在できる集配場所が多く，グリッド内の移動の自由さから，衝突回避のための迂回路も豊富である．一方，災害現場や建設現場のような迷路状の環境には集配場所が少なく，それらの数が偏るため，多くのエージェントが集配場所に集中する結果，輸送効率の悪化や立ち往生，デッドロックに陥りやすい．SBDA はグラフ理論の articulation-point-finding アルゴリズムを用いてリアルタイムに決定される待機ノードを使用し，エージェントが有限時間そこに滞在することを保証する．我々は実験により，提案手法が従来手法の輸送効率を上回ることを示した．

本研究では，MAPD 問題の制御手法である Priority Inheritance with BackTracking (PIBT) に暫時的な優先度を導入した拡張 PIBT を提案し，PIBT の能力を下げることなく適用環境の制約を緩めることで適用範囲を拡大すると共に，実験的にその効果を示す．PIBT 手法は毎ステップ優先度を計算し，その優先度の高いエージェントから順番に，次のステップでの移動先を確定させるアルゴリズムである．このアルゴリズムでは，袋小路のような形状を含むマップでは行き詰まりが発生するため，実験環境に対しそれを除外する制約を設けている．そこで本研究では，エージェントに通常の優先度に加えて暫時的な優先度を持たせる拡張を施し，先行研究における環境制約を緩めても搬送を継続できることを実験的に示す．

本研究では主に一階層におけるMulti-Agent Pickup and Delivery（MAPD）問題に関する二つの課題に取り組んだ。まず、AGVや運搬資材等のサイズや通路幅等が不均一な環境での輸送計画をN-MAPD問題と定義し、衝突のない経路・動作計画を効率良く生成可能なアルゴリズムを提案、評価した。次にMAPD問題におけるデッドロック回避手法を改善した。専用にデザイン可能なグリッド状の環境を想定した既存手法は、集配場所や迂回路が少ない迷路状の環境では輸送効率が悪化する。迷路状の環境でも運搬の並列性を向上して輸送効率を改善可能な、グラフ理論を活用したデッドロック回避手法を提案、評価した。