Intelligent Search and Planning Algorithms for Reliable AI Agent Navigation

Reliable deployment of AI agents in real-world environments requires planning algorithms that are both correct (optimal when required) and constraint-aware (satisfying hard operational rules).We study two complementary planning formulations: Optimal routing on a city graph using heuristic search (Greedy Best-First vs. A*) Constraint-aware itinerary planning formulated as a CSP with backtracking and constraint propagation On a 50-city U.S. routing task, A* achieves 100% optimality over 10 random start-goal pairs (vs.30% for Greedy), with lower average path cost (1620 vs. 1850 miles) and millisecond-level runtime.For multi-constraint planning, the CSP solver finds feasible itineraries and exposes infeasibility as constraints tighten, characterizing accuracy-efficiency trade-offs for reliable agent navigation. Background & MotivationMany agent deployments can be framed as planning under constraints: Optimal routing: minimize distance or cost on a graph Constraint-aware planning: satisfy hard policy, topology, or resource constraints This poster evaluates classic, interpretable planning primitives that provide: Correctness guarantees (A* with admissible heuristics) Explicit constraint validation (CSP backtracking)