Graph-Based Planning

Ask about this topic

Overview

Graph-based planning represents places, actions, task dependencies, or possible system states as nodes and connections, then searches the graph for a sequence that meets goals and constraints. Classical approaches include A*, Dijkstra, hybrid and any-angle search, and optimization over graphs of convex sets; they are used in robot navigation, multi-agent pathfinding, and task execution. Newer methods add sparse or topological maps, learned heuristics and graph neural networks, world models, and task graphs for language-model agents. A central challenge is balancing speed and scalability with optimality, safety, and reliable behavior when maps or conditions change.

Latest papers

CardsList

99 papers15 papers in the last four weeks, up 7% on the four weeks before. 0.1% of all new papers.

  1. Graphs of Trajectory Bundles for Nonlinear Motion Planning

    Oct 23, 2026Joris Verhagen, Jon Arrizabalaga, Jana Tumova +1Constrained Motion PlanningKinodynamic Motion Planning

    Authors are with the Division of Robotics, Perception, and Learning, KTH Royal Institute of Technology, Stockholm, Sweden · Authors are with the Department of Aeronautics and Astronautics, MIT, Cambridge, MA, USA

  2. Multi-Token Prediction and Alternative Tokenization Improve Learning Latent Multi-Hop Graph Search at Scale

    Oct 22, 2026Arvid Frydenlund, FuTe Wong, Katherine Lambert +1LLM Reasoning with GraphsGraph-Based Planning

    University of Toronto, Vector Institute, Manulife Applied AI Research · University of Toronto, Vector Institute · University of Toronto +1

  3. GGraph: A GPU-Accelerated Library for Graph-Based Robot Deployment and Learning

    Oct 20, 2026Yash Rampuria, Rohan Garg, Daniele Gammelli +1Robot LearningRobotic RL

    Stanford University, CA

  4. Discovery-Probability Graph Planning for Embodied Agents in Tasks with Hidden Cooperation Requirements

    Oct 19, 2026Zihuang Cai, Changjian Chen, Zhuo Tang +2Multi-Agent PlanningGraph-Based Planning

    College of Computer Science and Electronic Engineering, Hunan University · Geely Holding Group, China

  5. Procedural Memory for Language Agents: A Neurosymbolic Perspective on Explicit Goal Structure

    Oct 19, 2026Jonathan Leung, Zhiqi Shen, Deheng YeProcedural Memory for LLM AgentsAgent Memory

    Tencent-NTU Joint Research Laboratory (CENTURY), Nanyang Technological University, Singapore · College of Computing and Data Science, Nanyang Technological University, Singapore

  6. Not All Graphs Are Maps: A Task-Agnostic Exploration Framework for Mobile GUI Navigation

    Oct 15, 2026Adamo Orsini, Seyed Mehdi Ayyoubzadeh, Sadman Rakib Pinon +5Graph-Based Agent MemoryGraph-Based Planning

    Concordia University · Mila – Quebec AI Institute · McMaster University

  7. ATOM: Abstract Transition and Option Modeling - Experience-Informed Hierarchical Navigation

    Oct 13, 2026Changxuan Yao, Panagiotis TsiotrasRobot NavigationHierarchical Planning

    Institute for Robotics and Intelligent Machines Georgia Institute of Technology, Atlanta, GA

  8. Graph-Based Heuristics for Minimum Constraint Removal in Cluttered Robot Motion Planning

    Oct 8, 2026Antony Thomas, Fulvio Mastrogiovanni, Marco BagliettoMotion PlanningRobot Motion Planning

    Robotics Research Center, IIIT Hyderabad, 500032, Hyderabad, India. · Department of Informatics, Bioengineering, Robotics, and Systems Engineering, University of Genoa, 16145, Genoa, Italy.

  9. STAG: A Sparse Traversability-Aware Graph Representation from Grid-Based Costmaps for Robotic Navigation

    Oct 8, 2026Gabriel Manuel Garcia, Stéphanie Aravecchia, Miguel Angel Olivares-MendezRobot NavigationGraph-Based Planning

    University of Luxembourg, Luxembourg · IRL Georgia Tech-CNRS, Metz, France

  10. The Cost of Classical Multi-Agent Path Finding

    Oct 7, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianMulti-Agent Path FindingGraph-Based Planning

    Chalmers University of Technology Gothenburg, Sweden

  11. Optimal Planning in a Dynamic World

    Oct 2, 2026Devin Wild Thomas, Solomon Eyal Shimony, Wheeler Ruml +3Safe Interval Path PlanningMotion Planning

    University of New Hampshire, USA · Ben-Gurion University of the Negev, Israel · Technion - Israel Institute of Technology, Israel +3

  12. ChronoGraph: Functional 4D Scene Graphs with Vision-Language Models for Interaction Understanding and Grounded Planning

    Sep 30, 2026Chenyangguang Zhang, Malgorzata Gwiazda, Guanlong Jiao +5Graph-Based Planning4D Scene Understanding

    ETH Zurich · Technical University of Munich · University of British Columbia +3

  13. DAGent: Evaluate-then-Grow Planning for Deep Research Agents

    Sep 30, 2026Hanwen Liu, Yuanfu Sun, Qiaoyu TanMulti-Agent LLM SystemsDeep Research Agents

    New York University · New York University Shanghai

  14. Graph World Models for Constrained Epidemic Policy Planning

    Sep 28, 2026Yiqi Su, Rashed Shelim, Lingyi Wang +2Action-Conditioned World ModelsGraph-Based Planning

    Department of Computer Science, Virginia Tech, Alexandria, VA 22305, USA · Department of Electrical and Computer Engineering, Virginia Tech, Alexandria, VA 22305, USA

  15. GuardPIBT: Counterfactually Gated Neural Guidance for Ultra-Large-Scale 3D Multi-Agent Path Finding

    Sep 28, 2026Yuan Zhou, Zhenyu Hou, Guangtong Xu +4Graph-Based PlanningMulti-Agent Path Finding

    Institute of Cyber-Systems and Control, College of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China. · Differential Robotics Technology Company, Hangzhou 311121, China. · Huzhou Institute, Zhejiang University, Huzhou 313000, China. +3

  16. Metro-WM: Long-Horizon Latent Planning with Realisable Sub-Goals

    Sep 25, 2026Royson Lee, Fady Rezk, Titouan Parcollet +2Long-Horizon PlanningGoal-Conditioned Planning

    Samsung AI, Cambridge, UK · University of Edinburgh, UK

  17. dRVG: Quadtree-Guided, Resolution-Complete Online Motion Planning for Polygonal Robots in Unknown Environments

    Sep 25, 2026Duo Zhang, Hechen Zhang, Junshan Huang +1Motion PlanningRoadmap-Based Motion Planning

    Department of Computer Science, Rutgers, the State University of New Jersey, Piscataway, NJ, USA

  18. Peer-Grounded Counterfactual Path Planning for Chronic Health Management

    Sep 25, 2026Saman Khamesian, Hassan GhasemzadehHealthcareCounterfactual Explanations

    College of Health Solutions, Arizona State University, Phoenix, AZ, USA · School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ, USA

  19. A Topological Representation with Object-Path Graphs for Open-Vocabulary Instance Navigation

    Sep 21, 2026Linwei Zheng, Daojie Peng, Bingtao Wang +2Robot NavigationOpen-Vocabulary Object Navigation

    The Hong Kong University of Science and Technology (Guangzhou) · The Hong Kong University of Science and Technology

  20. Smoothed Analysis of Inconsistent A*

    Sep 20, 2026Zhiyang Chen, Hailong YaoGraph-Based Planning

  21. TRACS: A Geometry-Aware Framework for Scalable Multi-Agent Path Finding in Warehouses

    Sep 19, 2026Siddhant Erande, Anuj TiwariMulti-Agent Path FindingMotion Planning

    Department of Engineering Design, Indian Institute of Technology Madras, Chennai 600036, India · Department of Mechanical Engineering at Indian Institute of Technology Madras, Chennai 600036, India

  22. HOPHY: A Hierarchical Hypergraph Representation for Off-Road Path and Mission Planning

    Sep 17, 2026Pranay Meshram, Charuvahan Adhivarahan, Prithvi Poddar +4Hierarchical PlanningGraph-Based Planning

    Department of Computer Science and Engineering, University at Buffalo, NY 14260, USA. · Department of Mechanical and Aerospace Engineering, University at Buffalo, NY 14260, USA.

  23. Customizable and Jointly Optimized Route Planning: A Deep Architecture Enabling Differentiable Shortest-Path Search

    Sep 17, 2026Rui Zhao, Chao Chen, Longfei Xu +4Graph-Based PlanningDifferentiable Optimization

    Alibaba Group Beijing, China · Alibaba Group Hangzhou, China

  24. Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation

    Sep 17, 2026Tung Tran, Viet Bao Mai, Hoang Ta +1Markov Decision ProcessesMonte Carlo Tree Search

    School of ICT Hanoi University of Science and Technology Hanoi, Vietnam

  25. GPEvac: GNN-Based PPO for Adaptive Evacuation Routing During Shooting Events

    Sep 14, 2026Daniel Perkins, Subhadeep ChakrabortyGraph Neural NetworksDisaster Response

    The Bredesen Center for Interdisciplinary Research and Graduate Education · Department of Mechanical and Aerospace Engineering, University of Tennessee

  26. An Information-Space Perspective to Scene Graph Sufficiency for Robotic Task Planning

    Sep 14, 2026Başak Sakçak, Francesco VerdojaState AbstractionRobot Task Planning

    Dept. of Advanced Computing Sciences, Maastricht University, the Netherlands · School of Electrical Engineering, Aalto University, Finland

  27. Universal Observatory Graphs for Distributed Sky Coverage and Artificial Intelligence Based Interplanetary Routing

    Sep 5, 2026Mohammed Abdel RazekGraph-Based Planning

  28. Compact Bellman-Grounded Cognitive Maps for Cost-Aware Navigation

    Sep 4, 2026Yuzhe Han, Mingkun Xu, Yujie WuGraph-Based Agent MemoryRobot Navigation

    Guangdong Institute of Intelligence Science and Technology (GDIIST), Zhuhai, China · Department of Computing, The Hong Kong Polytechnic University, Hong Kong SAR, China

  29. Connectivity-Aware Graph Extension for Decentralized Multi-Robot Exploration

    Sep 1, 2026Béatrice Garcia Cegarra, Elena Vanneaux, Quentin Picard +1Multi-Robot ExplorationMulti-Robot Coordination

    ⋆Pˆole recherche, AMIAD, Palaiseau, France · †UI2S, ENSTA, IP Paris, Palaiseau, France

  30. STEGNav: Spatio-Temporal Event Graph Reasoning for Multimodal Lifelong Object Navigation

    Aug 28, 2026Yang Chen, Zhenyu Huang, Wenbo Fu +4Vision-Language NavigationObject-Goal Navigation

    State Key Laboratory of Novel Software Technology, Nanjing University · School of Intelligence Science and Technology, Nanjing University · School of Artificial Intelligence, Nanjing University