A Novel MDP Decomposition Framework for Scalable UAV Mission Planning in Complex and Uncertain Environments
Md Muzakkir Quamar, Ali Nasir, Sami ELFerik · 2025
Read A Novel MDP Decomposition Framework for Scalable UAV Mission Planning in Complex and Uncertain Environments by Md Muzakkir Quamar, Ali Nasir, Sami ELFerik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00838.txt.
Introduction
Md Muzakkir Quamar, Ali Nasir, and Sami ELFerik present a planning framework for drones in a 2025 paper. Unmanned aerial vehicles must plan missions in complex, uncertain settings, from shifting weather to failing parts. Good plans are often computed with Markov decision processes, which weigh actions, chances, and rewards together.
Those processes grow too large to solve directly as missions scale up. The team's two-stage decomposition breaks the big problem into smaller pieces that can be solved and recombined. The framework is built to be scalable and fault-tolerant. Faster, sturdier planning would let drone fleets take on bigger jobs.
Catalog record
| CREATOR | Md Muzakkir Quamar, Ali Nasir, Sami ELFerik |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-00838
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Novel MDP Decomposition Framework for Scalable UAV Mission Planning in Complex and Uncertain Environments Md Muzakkir Quamar, Ali Nasir, Sami ELFerik Abstract This paper presents a scalable and fault-tolerant framework for unmanned aerial vehicle (UAV) mission management in complex and uncertain environments. The proposed approach addresses the computational bottleneck inherent in solving large-scale Markov Decision Processes (MDPs) by introducing a two-stage decomposition strategy. In the first stage, a factor-based algorithm partitions the global MDP into smaller, goal-specific sub-MDPs by leveraging domain-specific features such as goal priority, fault states, spatial layout, and energy constraints. In the second stage, a priority-based recombination algorithm solves each sub-MDP independently and integrates the results into a unified global policy using a meta-policy for conflict resolution. Importantly, we present a theoretical analysis showing that, under mild probabilistic independence assumptions, the combined policy is provably equivalent to the optimal global MDP policy. Our work advances artificial intelligence (AI) decision scalability by decomposing large MDPs into tractable subproblems with provable global equivalence. The proposed decomposition framework enhances the scalability of Markov Decision Processes, a cornerstone of sequential decision-making in artificial intelligence, enabling real-time policy updates for complex mission environments. Extensive simulations validate the effectiveness of our method, demonstrating orders-of-magnitude reduction in computation time without sacrificing mission reliability or policy optimality. The proposed framework establishes a practical and robust foundation for scalable decision-making in real-time UAV mission execution. [type=editor, auid=000,bioid=1, orcid=0009-0003-5550-9760] [style=chinese] [style=chinese] keywords Markov Decision Process ,Decomposed Markov Decision Process ,Fault tolerant operation ,Decision Making ,Unmanned Aerial vehicle ,UAV Mission Planning ,UAV Mission Management † † credit: Conceptualization of this study, Methodology, Software † † credit: Data curation, Writing - Original draft preparation 1 Introduction Unmanned Aerial Vehicles (UAVs) are increasingly becoming indispensable in critical civilian and military domains where efficiency, responsiveness, and adaptability are of utmost importance. Their unique capabilities—such as compact size, low operational cost, vertical takeoff and landing, high maneuverability, rapid deployment, and extended endurance—make them an attractive alternative to traditional aerial platforms. As a result, UAVs are now widely employed in diverse applications ranging from logistics, surveillance, and environmental monitoring to reconnaissance and tactical strike operations. However, as UAV missions grow in complexity and scale, particularly in multi-UAV scenarios, effective mission management becomes a central challenge [ 1 ] . A central challenge in UAV mission planning lies in maximizing operational effectiveness while accounting for critical constraints such as limited resources, mission completion requirements, and platform survivability. Achieving optimal decision-making in such contexts requires carefully balancing competing factors—mission objectives, resource utilization, and UAV endurance [ 2 ] . For example, in logistics operations, UAVs need to optimize delivery routes to minimize travel time and energy expenditure while adapting to dynamic urban environments with obstacles and airspace restrictions [ 3 , 4 ] . In air combat missions, UAVs must simultaneously execute complex tactical maneuvers, avoid detection or interception, and manage onboard resources to sustain prolonged engagement [ 5 ] . Similarly, In disaster response scenarios, UAVs are often required to collect real-time situational data under rapidly evolving conditions, demanding robust trade-offs between communication bandwidth, flight endurance, and coverage reliability [ 6 ] . These examples highlight that effective UAV mission planning is not simply about task execution but about maintaining a continuous balance among multiple, often conflicting, objectives under uncertainty. Coordinating decision-making under uncertainty, ensuring efficient resource allocation, and maintaining robustness in dynamic and adversarial environments call for advanced planning frameworks that can effectively balance computational efficiency with operational reliability [ 7 ] . Optimizing UAV performance during missions is inherently a multifaceted problem, encompassing not only navigation and obstacle avoidance but also endurance management, fault tolerance, and adaptability to unpredictable events [ 8 ] . Over the years, extensive research has focused on developing optimal path-planning and navigation strategies for UAVs [ 9 , 10 ] , with a variety of optimization approaches proposed to minimize energy consumption and enhance mission efficiency [ 11 , 12 ] . Techniques such as geometric and graph-based methods [ 13 ] , artificial potential fields [ 14 ] , game-theoretic formulations [ 15 ] , and sensor fusion strategies have been widely studied and applied for UAV navigation and obstacle avoidance [ 16 ] . While these contributions represent significant progress, most existing frameworks tend to address isolated aspects of the problem space. They often emphasize path optimization or collision avoidance without sufficiently integrating the broader requirements of mission success, resource-aware decision-making, and resilience to real-world challenges such as environmental uncertainties, system malfunctions, or hostile threats. This gap underscores the need for unified, decision-theoretic approaches that can holistically capture the interplay between mission objectives, resource constraints, and dynamic operational risks. Recent studies emphasize that advancing UAV autonomy requires decision-making frameworks capable of adapting to environmental variability while maintaining mission reliability. For instance, Basharat et al. [ 17 ] provide a detailed survey underscoring the importance of algorithms that allow UAVs to respond to dynamic operational conditions without compromising system integrity or mission success. In parallel, the work in [ 18 ] draws attention to the role of resource management, highlighting how effective allocation of limited onboard resources directly impacts UAV endurance, resilience, and long-term reliability. Another complementary line of research explores the use of queuing-theoretic models for mission task management, where tasks are mapped to service queues in order to support efficient scheduling, prioritization, and execution under uncertainty [ 19 , 20 ] . Together, these contributions reveal that autonomy in UAV systems hinges not only on navigation and control, but also on the seamless integration of adaptability, resource efficiency, and mission-level coordination. A system that can manage this interplay would be capable of handling more sophisticated operations—such as cooperative multi-UAV missions, persistent surveillance, or disaster-response deployments—with minimal human oversight. Such advancements would not only raise mission success rates but also enhance safety, resilience, and sustainability, even in resource-constrained or adversarial settings. In light of these challenges, Markov Decision Processes have gained prominence as a powerful decision-theoretic tool, offering a principled means to model sequential choices under uncertainty and optimize UAV performance across diverse operational scenarios. MDPs have long been recognized as a rigorous framework for sequential decision-making in uncertain environments, offering a principled way to optimize system behavior under stochastic dynamics [ 21 ] . The strength of MDPs lies in their ability to represent complex systems through a set of discrete states and possible actions, where transitions between states are governed by probabilistic models. At each decision point, the agent selects an action, transitions probabilistically to a subsequent state, and incurs an associated cost. By aggregating these stepwise costs over the planning horizon, MDPs enable the derivation of policies that minimize the expected cumulative cost, thereby ensuring efficient and reliable mission performance under uncertainty—whether the horizon is finite or infinite [ 22 ] . This capability has led to their widespread application in UAV operations, particularly for tasks such as navigation in uncertain terrains, real-time obstacle avoidance, and adaptive threat evasion [ 23 ] . Nevertheless, most existing UAV-focused applications treat these problems in isolation and do not fully address the broader requirement of balancing mission success with resource management and operational risks. In practice, UAVs must contend with simultaneous challenges—including limited battery