{"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":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow"],"consensus_categories":[],"category_scores_codex":[0.0003841058,0.000262409,0.0004041331,0.0004733264,0.0001243688,0.00005931426,0.0006654043,0.0002391435,0.000005155646],"category_scores_gemma":[0.00005984872,0.0002785148,0.00009587657,0.0003208382,0.0002389959,0.00009396437,0.0001637735,0.0004315462,0.00005697652],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00007402452,"about_ca_system_score_gemma":0.00006561697,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00002136748,"about_ca_topic_score_gemma":0.000006422836,"domain_scores_codex":[0.9980588,0.00002864203,0.0006705315,0.0007098296,0.0002673116,0.0002649121],"domain_scores_gemma":[0.9986929,0.0001832763,0.0002770133,0.0006591668,0.00008916774,0.00009848466],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.000009210095,0.0001358236,0.000186239,0.00004307901,0.00003798224,0.0000115913,0.0006928734,0.005265935,0.00003468048,0.5348609,0.0002562842,0.4584654],"study_design_scores_gemma":[0.0000575046,0.0001464998,0.000646722,0.0004049977,0.00004027284,0.000004236804,0.0002698097,0.4617149,0.00182735,0.5313458,0.002779405,0.0007625492],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.0000590801,0.0001633151,0.9945285,0.0001121107,0.0005616857,0.0006540667,0.00005323183,0.0002011628,0.003666873],"genre_scores_gemma":[0.01676799,0.001187952,0.9640101,0.00009059873,0.0002335863,0.0005452879,0.0001010069,0.0001042003,0.01695932],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.4577029,"threshold_uncertainty_score":0.9999667,"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."}}