💻 computer science

UDAQ: Unified Dynamic and Adaptive Q-iteration for Unknown Environment Path Planning and Exploration

This paper introduces UDAQ, a unified, reward-driven Q-iteration framework that autonomously adapts to dynamically evolving state spaces to simultaneously optimize both point-to-point path planning and efficient environment exploration, significantly outperforming conventional planners and exploration strategies in unknown environments without prior map knowledge.

Original authors: Nasr Abdalmanan, Kamarulzaman Kamarudin, Muqri Zinal, Mohd Rizal Manan, Victor Bennetts

Published 2026-07-30

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Nasr Abdalmanan, Kamarulzaman Kamarudin, Muqri Zinal, Mohd Rizal Manan, Victor Bennetts

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a robot dropped into a pitch-black maze it has never seen before. Its only tools are a pair of "eyes" (sensors) that can see a few steps ahead and a brain that needs to figure out two things at once: "How do I get to that specific spot over there?" and "How do I map out the whole dark room so I don't get lost?" This is the daily life of an autonomous robot, a field of science called mobile robotics. For a robot to survive in the real world, it needs path planning (drawing a safe line from point A to point B) and exploration (systematically checking out unknown areas to build a mental map). Traditionally, engineers have treated these as two separate jobs, hiring one "program" to decide where to go and another "program" to figure out how to get there. But in a world that changes as you look at it, keeping these jobs separate can lead to confusion, like a driver who asks a passenger for directions while the passenger is still trying to read the map.

Enter UDAQ (Unified Dynamic and Adaptive Q-iteration), a new framework proposed by researchers Nasr Abdalmanan and his team from Universiti Malaysia Perlis and Örebro University. Think of UDAQ not as a robot with two separate brains, but as a single, super-adaptive navigator that learns to do everything through a game of "hot and cold." Instead of switching between different modes, UDAQ uses a single set of rules (a reward system) to teach the robot how to behave. If the robot needs to find a specific door, the "game" rewards it for getting closer to that door. If the robot needs to map a whole building, the "game" rewards it for finding new, unexplored corners. The magic trick is that this system automatically adjusts its own difficulty settings as the robot discovers more of the world. If the maze gets bigger, UDAQ scales up its rewards so the robot doesn't get discouraged or confused. In a series of computer simulations, this approach proved to be a faster, smoother, and more efficient way for robots to navigate unknown spaces compared to the standard methods currently used in the industry.

The Problem: The Robot's "Split Personality"

Imagine you are trying to explore a giant, dark cave. You have a flashlight that only lights up a small circle around you. To get to the exit, you need to know the path. To build a map, you need to wander into the dark. Old-school robot navigation often splits these tasks into two separate teams. One team, the Explorer, says, "Go find the edge of the known world!" The other team, the Planner, says, "Okay, now draw a line to that edge."

The problem is that these two teams don't talk to each other well. The Explorer might pick a target that looks close but is actually behind a wall, and the Planner has to waste time figuring out a detour. Or, the map might change while the Planner is working, making the old plan useless. It's like trying to drive a car where the GPS and the steering wheel are controlled by two different people who are arguing about the destination.

The Solution: One Brain, Many Moods

The researchers behind UDAQ decided to stop splitting the team. They built a system where the robot has one brain that handles both exploring and planning, but it changes its "mood" based on what you want it to do. They call this a Unified Dynamic and Adaptive Q-iteration framework.

Here is how it works, using a simple analogy:

The Game of "Hot and Cold"
Imagine the robot is playing a video game where it earns points (rewards) for moving.

Mood 1: The Goal Chaser. If you tell the robot, "Go to the red door," the game gives it a huge pile of points for getting closer to the door. It also gives small penalties for walking in circles. The robot learns to rush toward the door, but if it hits a wall, it instantly recalculates the best path around it.
Mood 2: The Map Maker. If you tell the robot, "Explore everything," the game changes. Now, the robot gets the biggest points for finding frontiers—the fuzzy edges where the known map meets the unknown dark. It ignores the red door and instead rushes to the nearest unexplored corner.
Mood 3: The Directional Explorer. You can even tell the robot, "Explore, but mostly head North." The robot will still look for new areas, but it will prioritize the ones that are North, creating a specific pattern of exploration.

The genius of UDAQ is that it doesn't need to switch software to change moods. It just changes the rules of the game (the reward configuration) while keeping the same brain running.

The Secret Sauce: The "Stretchy" Reward

There is a tricky problem with these games. If the robot is in a tiny room, a reward of "10 points" might feel huge. But if the robot suddenly discovers a massive hall, that same "10 points" might feel too small to motivate the robot to cross the whole room. The robot might get confused and stop trying, or it might make bad decisions because the math doesn't add up anymore.

UDAQ solves this with a Dynamic and Adaptive mechanism. Think of it like a stretchy ruler.

The robot constantly measures the size of the space it has discovered so far. It calculates the longest possible path it could walk through the known map (the "geodesic diameter").
Based on this size, it automatically rescales the rewards. If the room is huge, the points are worth more. If the room is small, the points are worth less.
This ensures that the robot always feels the "hot and cold" signals correctly, no matter how big the maze gets. It prevents the robot from getting "stuck" or making bad choices just because the environment changed.

What the Simulations Showed

The researchers tested UDAQ in three different virtual worlds, ranging from a simple open warehouse to a complex building with narrow hallways and many rooms. They compared it against the standard methods used in the industry (like the ROS 2 NavFn planner) and other exploration strategies (like "wall-following" or "random walking").

1. Getting from A to B (Path Planning)
When the robot needed to go from a start point to a goal point in an unknown environment:

UDAQ found paths that were 8–12% shorter than the standard planner.
It finished the trip 20–30% faster.
Even without knowing the map beforehand, UDAQ's paths were almost as good as the "perfect" path a human could draw if they knew the whole map from the start.

2. Exploring the Whole Room (Exploration)
When the robot had to map out the entire environment:

UDAQ was a clear winner. It traveled 36–44% less distance than the standard "frontier-based" method (which is currently the best traditional approach).
It finished the exploration 48–59% faster.
In the most complex map (Map C), the standard "random walk" method actually got stuck in a narrow corridor and failed to finish the job, while UDAQ navigated through smoothly and completed the task.

3. The "Directional" Test
In one experiment, the researchers told the robot to explore the complex building but with a bias toward a specific direction (like "mostly South").

When the direction matched the building's layout (like South), the robot was incredibly efficient, taking the shortest path.
When the direction was "wrong" (like West), the robot took a longer, more winding route.
This proved that UDAQ can be "steered" to explore in a specific order, which could be useful if you know certain rooms are more important than others.

The Catch: It's Still a Simulation

While the results are impressive, the researchers are careful to note that these tests were all done in computer simulations. The robots lived in a perfect digital world where sensors never glitched, wheels never slipped, and maps were always accurate. In the real world, robots face messy problems like bad lighting, slippery floors, and noisy sensors. The paper suggests that UDAQ is a very strong candidate for real-world use, but it hasn't been tested on a physical robot yet. The authors plan to take this "stretchy ruler" brain out of the computer and into the real world in future work.

The Takeaway

UDAQ is a step toward robots that are less like rigid machines following a checklist and more like adaptable explorers. By unifying path planning and exploration into a single, self-adjusting system, it allows robots to navigate the unknown with a level of efficiency and smoothness that traditional, split-system robots struggle to match. It's a reminder that sometimes, the best way to solve a complex problem isn't to build more tools, but to build a smarter way to use the one you have.

Technical Summary: UDAQ – Unified Dynamic and Adaptive Q-iteration for Unknown Environment Path Planning and Exploration

Problem Statement
Autonomous navigation in unknown environments presents a dual challenge: the robot must simultaneously perform efficient point-to-point path planning and reliable full-environment exploration without prior map knowledge. Traditional architectures typically decouple these tasks, separating exploration (determining where to go) from path planning (determining how to get there). This separation often leads to suboptimal behavior, as the exploration layer selects goals without considering path complexity or map uncertainty, while the planning layer operates on potentially outdated map snapshots. Furthermore, applying classical value iteration or dynamic programming to unknown environments is challenging because the navigable state space expands dynamically as new regions are discovered. Fixed reward magnitudes and static state-space representations often fail to maintain stable value propagation in such evolving environments, leading to poor convergence and degraded policy performance.

Methodology
The paper proposes UDAQ (Unified Dynamic and Adaptive Q-iteration), a framework that unifies local path planning, complete environment exploration, and oriented exploration within a single reward-driven Markov Decision Process (MDP) formulation.

Unified MDP Formulation: The problem is modeled as an MDP $(S, A, P, R, \gamma, \pi)$ where the state space $S$ is derived from a SLAM-generated occupancy grid, segmented into square tiles. States are classified as free, occupied, frontier (boundary between known/unknown), goal, or unknown. The action space consists of eight discrete movements (cardinal and inter-cardinal).
Configurable Reward Functions: UDAQ employs a single value iteration framework where different behaviors are induced by reconfiguring the reward function $R(s, a, s')$ $R (s, a, s^{'})$ :
1. Point-to-Point Planning: Rewards transitions toward a specific goal, scaled by Euclidean proximity, while penalizing obstacles and unnecessary steps.
2. Environment Exploration: Removes goal-specific rewards, assigning high uniform rewards to frontier states to encourage systematic coverage.
3. Oriented Exploration: Introduces an "imaginary goal" outside the environment boundary to bias exploration in a specific direction.
Dynamic State Space and Adaptive Reward Scaling: A core technical innovation is the handling of the dynamically evolving state space. As the SLAM map expands, UDAQ employs an adaptive reward scaling mechanism. It estimates the geodesic diameter ( $L$ ) of the current traversable state space using a medial-axis skeleton and Chebyshev distance transform. Reward magnitudes (step penalties, obstacle penalties, and goal/frontier rewards) are then automatically scaled relative to $L$ and the discount factor $\gamma$ . This ensures that value function propagation remains stable and meaningful regardless of the environment's size or structural complexity, preventing policy degradation as the map grows.
Closed-Loop Operation: The system operates as a fully autonomous closed-loop process. It continuously integrates SLAM updates, updates state classifications, recalculates rewards based on the current map diameter, performs Q-iteration to convergence, and generates navigation commands without human intervention.

Key Contributions

Unified Framework: Demonstrates that diverse autonomous behaviors (navigation, exploration, oriented exploration) can be achieved within a single formulation through reward configuration, eliminating the need for separate planners or task-specific heuristics.
Dynamic State Space Adaptation: Introduces a method for value iteration to operate on an expanding state space by dynamically adjusting reward magnitudes based on the estimated geodesic diameter of the traversable area.
Adaptive Reward Scaling: Proposes an automatic tuning strategy that ensures stable Bellman backups and consistent policy quality as the environment is progressively revealed, addressing the issue of fixed rewards becoming ineffective in larger, evolving maps.

Experimental Results
The method was evaluated in ROS 2 simulations across three environments of increasing complexity (Simple, Moderate, Complex) and compared against the ROS 2 NavFn planner (for navigation) and frontier-based, wall-following, and random-walk strategies (for exploration).

Point-to-Point Navigation: UDAQ consistently outperformed the NavFn planner. It reduced average travel distance by approximately 8–12% and travel duration by 20–30% across test cases, approaching global optimal solutions despite lacking prior map knowledge. It also demonstrated robust dynamic re-planning when new obstacles were introduced.
Environment Exploration: UDAQ significantly outperformed all baseline methods. Compared to frontier-based exploration (the strongest classical baseline), UDAQ reduced travel distance by 36–44% and exploration time by 48–59% across all environments. It also substantially exceeded the performance of wall-following and random-walk strategies. In complex environments, UDAQ maintained smooth trajectories and autonomous termination, whereas other methods often suffered from inefficient traversal or failure to fully cover the map.
Oriented Exploration: Experiments with eight directional configurations showed that directional bias significantly influences exploration efficiency. Configurations aligned with the environment's topology (e.g., South in the tested map) minimized redundant traversal and reduced completion time, while misaligned configurations increased path redundancy.

Significance and Claims
The paper claims that UDAQ provides a robust, efficient, and flexible solution for autonomous navigation in unknown environments. Its primary significance lies in unifying multiple navigation behaviors within a single reward-driven framework, allowing behavior to emerge from reward configuration rather than planner switching. By operating as a fully autonomous closed-loop system that adapts to dynamically evolving state spaces, UDAQ addresses the structural limitations of decoupled exploration and planning architectures.

The authors acknowledge that the results are based on ROS 2 simulations assuming idealized sensing and state estimation. Consequently, while the framework demonstrates effectiveness under controlled conditions, the paper states that future work is required to validate robustness on physical robotic platforms under real-world uncertainties such as sensor noise, actuator inaccuracies, and localization drift.