{"id":"W4387171282","doi":"10.3233/faia230531","title":"Intractability of Optimal Multi-Agent Pathfinding on Directed Graphs","year":2023,"lang":"en","type":"book-chapter","venue":"Frontiers in artificial intelligence and applications","topic":"Robotic Path Planning Algorithms","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"Lakehead University","funders":"","keywords":"Pathfinding; Vertex (graph theory); Directed graph; Computer science; Planar graph; Set (abstract data type); Digraph; Combinatorics; Bounded function; Mathematics; Theoretical computer science; Mathematical optimization; Shortest path problem; Graph","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001302681,0.0008301056,0.0008953652,0.0008825538,0.0009835247,0.002461863,0.002405685,0.001476074,0.004593297],"category_scores_gemma":[0.009515526,0.0008130884,0.001229536,0.001839323,0.00209352,0.004167542,0.002007571,0.004001036,0.0005849316],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.001747425,"about_ca_system_score_gemma":0.00130495,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002645094,"about_ca_topic_score_gemma":0.002850663,"domain_scores_codex":[0.9981675,0.0005047221,0.00007526798,0.00050319,0.0004930162,0.0002562048],"domain_scores_gemma":[0.9864738,0.01158034,0.0005729106,0.0007529504,0.0004016888,0.0002182918],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"simulation_or_modeling","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.000404087,0.0001938681,0.002353179,0.001013858,0.0001198681,0.0005904244,0.000859737,0.4493335,0.005574888,0.4358784,0.01507969,0.0885986],"study_design_scores_gemma":[0.000047819,0.00004047115,0.0007137402,0.00006238725,0.00003791079,0.0002173477,0.0001396508,0.4445686,0.002830875,0.5452828,0.006037667,0.00002064176],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2589785,0.003187236,0.6690094,0.005429354,0.0001627119,0.0002393807,0.002193422,0.001260766,0.05953936],"genre_scores_gemma":[0.8222025,0.002520333,0.1583242,0.0006630513,0.0002433045,0.0005609145,0.002990036,0.0004572021,0.01203846],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.004593297,"threshold_uncertainty_score":0.01536608,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.07339087815767956,"score_gpt":0.2960417104497567,"score_spread":0.2226508322920771,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}