Building a Travel Planning Agent with Multi-Step Reasoning

Why travel planning breaks simple LLM wrappers

Ask a plain chatbot to plan a five-day trip to Japan and you'll get a plausible-looking itinerary that quietly falls apart the moment you check it against reality. The flight it suggested doesn't exist on that route. The "10-minute walk" between two temples is actually a 40-minute train ride. The hotel it recommended is fully booked, and the restaurant it name-dropped closed two years ago. This isn't a hallucination bug you can prompt your way out of — it's a structural mismatch. A single LLM call is a one-shot guess. Travel planning is a sequence of dependent decisions: destination constraints shape date choices, dates shape flight and hotel availability, availability shapes budget, and budget loops back to change the destination shortlist.

A travel planning AI agent is a genuinely good test bed for multi-step reasoning because the problem has everything that makes agentic systems hard: incomplete information that must be fetched from external sources, decisions that depend on earlier decisions, real-world constraints that contradict user preferences, and a final output (a bookable itinerary) that has to be internally consistent. If your agent gets the reasoning loop right here, the same architecture generalizes to expense report agents, research assistants, and customer support bots that need to check a database before answering.

In this article we'll build a travel planning agent step by step: define the tools it needs, design a multi-step reasoning loop around them, add planning and self-correction, and handle the messy constraint-satisfaction problem that is "cheap flights that also let me see the sights I care about." Every code sample is Python and framework-agnostic pseudocode you can adapt to LangGraph, a custom loop, or the Claude API's native tool-use format.

What makes this a multi-step reasoning problem

Before writing code, it's worth being precise about what "multi-step" actually means here, because it's not just "call more than one tool."

A single-step agent takes a request, picks one tool, gets a result, and answers. A multi-step travel agent needs to:

• Decompose a vague goal ("a relaxing week in Portugal under $2000") into concrete sub-goals: destination shortlist, date range, budget allocation across flights/lodging/activities
• Fetch information whose results change what it does next — if flights to Lisbon are expensive that week, it needs to either shift dates or reconsider the destination, not just report the price
• Track state across many tool calls — partial itinerary, running budget total, constraints already satisfied
• Detect contradictions — a hotel booked for dates that don't match the flight dates — and repair them
• Know when to stop — when to present the plan versus keep refining it

This is the difference between a workflow (fixed sequence of steps) and an agent (the model decides the sequence based on what it learns along the way). Our travel planner needs to be an agent, because the right sequence of tool calls genuinely depends on the destination and the user's constraints.

Designing the tool set

Everything the agent can *do* has to exist as a tool. Resist the urge to make one giant plan_trip() tool — that just moves all the reasoning back inside a black box you can't debug. Instead, expose small, composable tools and let the model chain them.

from typing import TypedDict

class FlightSearchParams(TypedDict):
    origin: str
    destination: str
    depart_date: str
    return_date: str
    max_price: float

class HotelSearchParams(TypedDict):
    city: str
    checkin: str
    checkout: str
    max_price_per_night: float
    min_rating: float

def search_flights(params: FlightSearchParams) -> list[dict]:
    """Return a list of flight options matching the params.
    Each option includes price, duration, stops, and airline.
    """
    # In production this calls a flights API (Amadeus, Skyscanner, Duffel).
    return flight_api_client.search(**params)

def search_hotels(params: HotelSearchParams) -> list[dict]:
    """Return hotel options for a city and date range."""
    return hotel_api_client.search(**params)

def get_weather_forecast(city: str, month: str) -> dict:
    """Return typical weather patterns for a city in a given month."""
    return weather_api_client.climate_summary(city, month)

def get_points_of_interest(city: str, interests: list[str]) -> list[dict]:
    """Return attractions matching the traveler's stated interests,
    each with an estimated visit duration and neighborhood.
    """
    return poi_api_client.query(city, interests)

def estimate_transit_time(city: str, place_a: str, place_b: str) -> int:
    """Return estimated minutes to travel between two points of interest."""
    return maps_api_client.eta(city, place_a, place_b)

def check_budget(itinerary: dict, budget_cap: float) -> dict:
    """Sum all costs in a draft itinerary and flag if it exceeds the cap."""
    total = sum(item.get("cost", 0) for item in itinerary.get("line_items", []))
    return {"total": total, "over_budget": total > budget_cap, "cap": budget_cap}

Notice check_budget is not calling any external API — it's a reasoning aid, a tool that exists purely to force the model to do arithmetic reliably instead of trying to sum numbers in its head across a long context. This is a pattern worth generalizing: any calculation your agent needs to get exactly right belongs in a tool, not in free-text generation.

The reasoning loop: plan, act, observe, revise

The core of a multi-step agent is a loop, not a single prompt. The classic shape is ReAct-style (Reason, Act, Observe), and it's worth writing it out explicitly rather than hiding it inside a framework, at least the first time, so you understand what's actually happening on each turn.

def run_agent(user_request: str, tools: dict, model_client, max_steps: int = 12):
    messages = [
        {"role": "system", "content": SYSTEM_PROMPT},
        {"role": "user", "content": user_request},
    ]

    for step in range(max_steps):
        response = model_client.generate(
            messages=messages,
            tools=list(tools.values()),
        )

        if response.stop_reason == "end_turn":
            # Model decided it has enough to give a final answer.
            return response.text

        if response.stop_reason == "tool_use":
            messages.append({"role": "assistant", "content": response.tool_calls})

            tool_results = []
            for call in response.tool_calls:
                tool_fn = tools[call.name]["fn"]
                try:
                    result = tool_fn(call.arguments)
                    tool_results.append({
                        "tool_call_id": call.id,
                        "output": result,
                    })
                except Exception as exc:
                    # Feed errors back to the model instead of crashing.
                    tool_results.append({
                        "tool_call_id": call.id,
                        "output": {"error": str(exc)},
                    })

            messages.append({"role": "tool", "content": tool_results})
            continue

    raise RuntimeError("Agent exceeded max_steps without finishing")

The important design decisions here are easy to skim past, so let's name them explicitly:

• The loop, not the model, owns termination. max_steps is a hard ceiling. Without it, a confused agent can loop forever re-searching flights.
• Tool errors become messages, not exceptions. If search_hotels times out, the model needs to see that failure and adapt (try a different city, widen dates) rather than have the whole program crash.
• State lives in `messages`. The entire itinerary-in-progress is implicit in conversation history. For longer trips this gets expensive — we'll fix that with a scratchpad pattern below.

The system prompt is where the planning strategy lives

A common mistake is writing a system prompt that just lists the tools and hoping good reasoning emerges. For a travel agent specifically, you want to bake in an explicit planning order, because the dependency structure of the problem (dates before flights, flights before hotels, hotels before daily activity scheduling) is not something you want the model rediscovering from scratch every time.

SYSTEM_PROMPT = """You are a travel planning agent. Build itineraries by
reasoning step by step and using tools — never invent flight numbers,
prices, hotel names, or opening hours from memory.

Follow this order unless the user's request forces a different sequence:
1. Clarify destination(s), trip length, and hard constraints (budget, dates,
   dietary/accessibility needs) before calling any tool.
2. Check weather for the travel month if the destination is
   climate-sensitive (beach, hiking, skiing).
3. Search flights across a date range if dates are flexible; lock dates
   once a reasonable flight is found.
4. Search hotels for the locked dates.
5. Pull points of interest matching the user's stated interests.
6. Build a day-by-day schedule, using estimate_transit_time to avoid
   impossible back-to-back plans.
7. Run check_budget against the full draft. If over budget, cut the
   most expensive discretionary item first, not the flight or hotel.
8. Present the itinerary with per-day costs and a total.

If a tool call fails or returns nothing usable, say so explicitly and
try an adjusted query (wider dates, nearby airport, different city)
rather than fabricating a plausible-sounding answer.
"""

This is a planning scaffold, not a rigid script — the model can and should deviate when the user's request calls for it (e.g., "I already booked flights, just plan my days"). The point is that you're handing the model a default strategy for decomposing the problem, which measurably reduces the chance it jumps straight to inventing an itinerary without checking anything.

Structured scratchpad state instead of raw chat history

As trips get longer (two weeks, multiple cities), stuffing the entire tool-call history into the context window gets expensive and makes the model prone to losing track of earlier constraints. A better pattern is to maintain an explicit itinerary object as structured state, and have the agent read and write to it rather than relying on it to remember everything from scrollback.

from dataclasses import dataclass, field

@dataclass
class TripState:
    destination: str | None = None
    depart_date: str | None = None
    return_date: str | None = None
    budget_cap: float = 0.0
    flight: dict | None = None
    hotel: dict | None = None
    daily_plan: list[dict] = field(default_factory=list)
    running_total: float = 0.0

    def add_cost(self, amount: float):
        self.running_total += amount

    def remaining_budget(self) -> float:
        return self.budget_cap - self.running_total

    def as_prompt_context(self) -> str:
        """Compact summary injected into the prompt each turn,
        instead of replaying the full tool call history.
        """
        return (
            f"Destination: {self.destination}\n"
            f"Dates: {self.depart_date} to {self.return_date}\n"
            f"Flight: {self.flight or 'not booked'}\n"
            f"Hotel: {self.hotel or 'not booked'}\n"
            f"Days planned: {len(self.daily_plan)}\n"
            f"Spent so far: {self.running_total:.2f} / {self.budget_cap:.2f}"
        )

On each loop iteration, instead of appending every raw tool result to the message history forever, you update TripState and inject as_prompt_context() as a short summary. This is the same idea behind "memory compaction" in longer-running agents: keep the full detail available if the model asks for it again, but don't force it to re-read fifteen JSON blobs of flight search results to remember which one it already picked.

Constraint satisfaction: when preferences conflict

The hardest part of travel planning isn't fetching data — it's what to do when the user's constraints don't fit together. "Beachfront hotel, city-center location, under $80/night, in July" might simply not exist. A well-designed agent needs an explicit strategy for relaxing constraints in a sensible order rather than either failing silently or hallucinating a hotel that meets all four criteria.

def find_hotel_with_relaxation(params: HotelSearchParams, relax_order: list[str]):
    """Try the exact search first; if empty, relax constraints one at a
    time in the given priority order and report what was loosened.
    """
    results = search_hotels(params)
    if results:
        return {"results": results, "relaxed": []}

    relaxed_fields = []
    current = dict(params)
    for field_name in relax_order:
        if field_name == "max_price_per_night":
            current["max_price_per_night"] *= 1.25
        elif field_name == "min_rating":
            current["min_rating"] = max(current["min_rating"] - 0.5, 0)

        relaxed_fields.append(field_name)
        results = search_hotels(current)
        if results:
            return {"results": results, "relaxed": relaxed_fields}

    return {"results": [], "relaxed": relaxed_fields}

The key is that the agent should surface the trade-off to the user, not make it invisibly. "I couldn't find anything under $80/night with a 4+ rating, so I widened the budget to $100/night — here are three options" is a trustworthy answer. Silently returning a $140/night hotel because it was the closest match is not, even if the room itself is objectively nice. This mirrors a broader principle in agent design: when the agent has to make a judgment call on the user's behalf, that call needs to be visible in the output, with the reasoning attached.

Verifying the plan before presenting it

A multi-step agent that never checks its own work will confidently hand back itineraries with overlapping bookings or a total that quietly exceeds budget by 40%. Add an explicit verification pass as the second-to-last step, separate from the generation step.

def verify_itinerary(state: TripState) -> list[str]:
    """Run a battery of consistency checks on the draft itinerary.
    Returns a list of problems found (empty list means it's clean).
    """
    problems = []

    if state.flight and state.hotel:
        if state.hotel.get("checkin") != state.depart_date:
            problems.append(
                f"Hotel check-in ({state.hotel['checkin']}) doesn't match "
                f"flight arrival date ({state.depart_date})."
            )

    if state.running_total > state.budget_cap:
        overage = state.running_total - state.budget_cap
        problems.append(f"Itinerary is {overage:.2f} over the stated budget.")

    for i, day in enumerate(state.daily_plan):
        scheduled_minutes = sum(item["duration_minutes"] for item in day["activities"])
        if scheduled_minutes > 12 * 60:
            problems.append(f"Day {i+1} schedules more than 12 hours of activities.")

    return problems

Wire this into the loop so that if verify_itinerary returns problems, they get fed back to the model as a new "tool result" telling it exactly what to fix, and it loops again rather than presenting a broken plan. This closes the self-correction loop: the agent isn't just generating and hoping, it's generating, checking, and repairing — which is the actual definition of "reasoning" as opposed to "one good guess."

Handling ambiguity without stalling the conversation

Real users under-specify. "Plan me a trip to Italy in the spring" doesn't say for how long, with whom, or what budget. A naive agent either barrels ahead with assumptions (annoying if wrong) or asks twenty clarifying questions before doing anything useful (annoying regardless). The better pattern is to ask for the two or three constraints that actually change the plan's shape, make reasonable defaults for the rest, and state those defaults out loud.

REQUIRED_FOR_PLANNING = ["destination", "trip_length_days", "budget_cap"]

def missing_critical_fields(state: TripState, user_message: str) -> list[str]:
    missing = []
    if not state.destination:
        missing.append("destination")
    if not state.depart_date or not state.return_date:
        missing.append("trip_length_days")
    if state.budget_cap == 0.0:
        missing.append("budget_cap")
    return missing

def clarify_or_proceed(state: TripState, user_message: str) -> str | None:
    missing = missing_critical_fields(state, user_message)
    if len(missing) >= 2:
        return (
            "Before I search flights and hotels, I need a couple more "
            f"details: {', '.join(missing)}. Rough numbers are fine."
        )
    if len(missing) == 1 and missing[0] == "budget_cap":
        # One missing field with a sensible default: proceed and disclose.
        state.budget_cap = 2000.0
        return None  # proceed, but the agent should mention the assumption
    return None

This is a small piece of logic, but it's the difference between an agent that feels collaborative and one that feels either interrogative or reckless. The threshold of "ask if 2+ critical fields are missing, otherwise default and disclose" is a judgment call you'll tune based on your users, but having the rule live in code — rather than hoping the system prompt handles it consistently — makes the behavior testable.

Evaluating the agent, not just vibes-checking it

Once the loop, tools, and verification pass exist, you need a way to know if changes actually make it better. Build a small eval set of realistic requests and check concrete properties of the output, not just "does it look plausible."

test_cases = [
    {
        "request": "5 days in Lisbon in October, budget $1500 total, "
                   "flying from Chicago, love food and history",
        "checks": {
            "has_flight": True,
            "has_hotel": True,
            "under_budget": True,
            "min_days_planned": 5,
            "mentions_food_or_history_poi": True,
        },
    },
    {
        "request": "Weekend trip somewhere warm from Toronto, "
                    "budget $400, next month",
        "checks": {
            "has_flight": True,
            "under_budget": True,
            "flags_if_infeasible": True,  # $400 may not be enough
        },
    },
]

def run_eval_suite(test_cases, agent_fn):
    results = []
    for case in test_cases:
        output_state = agent_fn(case["request"])
        problems = verify_itinerary(output_state)
        passed = len(problems) == 0
        results.append({"request": case["request"], "passed": passed, "problems": problems})
    return results

The second test case is deliberately adversarial — a $400 budget for a weekend flight-plus-hotel trip may genuinely be infeasible, and a good agent should say so clearly rather than force-fitting a plan that quietly blows the budget or books a terrible red-eye to make the math work. Evals that include "the correct answer is to push back" are as important as evals that check whether the happy path works.

Bringing it together

A travel planning agent is a small, self-contained example of the exact skills that transfer to almost every serious agentic system: breaking a fuzzy goal into an ordered sequence of tool calls, maintaining structured state instead of relying on raw chat history, handling tool failures and conflicting constraints gracefully, verifying your own output before presenting it, and knowing when to ask the user versus when to proceed with a stated assumption. None of this requires an exotic framework — the loop above is maybe eighty lines of Python, and the rest is careful tool design and a system prompt that encodes a real planning strategy instead of a vague instruction to "be helpful."

If you want to go deeper — building agents that plan across dozens of steps, recover from partial failures, manage long-running state, and get evaluated rigorously before you ship them — that's exactly what we cover hands-on in 30 Days of Hermes Agent, our project-based course on building production-grade AI agents. You'll build systems like this travel planner from scratch, along with harder variants involving multi-agent handoffs and long-horizon memory, with real code review along the way.