This paper describes FOX-GA, an intelligent planning decision support tool for assisting military intelligence and maneuver battlestaff in rapidly generating and assessing battlefield courses of action (COAs). The motivations behind FOX stem from the need to plan and replan rapidly in such a way as to allow users flexibility and control over planning objectives and options. The environment in which plans are executed (the battlefield) is one that is inherently uncertain and rapidly changing, demanding frequent re-planning during execution. Planners, however, are limited, especially at crisis times; there are far more relevant plan options to be considered than time and resources allow. To help meet these rapid replanning needs, we designed a number of efficient representations containing only the most essential high-level aspects of the battlefield and the plans. This use of an "engineering approximation" allows FOX to very rapidly generate and evaluate a broader variety of variety of high quality COAs faster than they could do so themselves. Because the situation in inherently uncertain, plans are assessed in a variety of likely situations, and their average performance is determined. The more situationally robust plans tend to be rated more highly. Fox presents only a few, most highly rated options to users, and allows them to reassess those options according by their own judgment and select a small subset. Initial evaluations on domain experts have been very promising.