The creation of autonomous decision makers to handle potentially hazardous or logistically complicated tasks is desirable for the purpose of reducing human labor and exposure to risk, and for increasing the general performance of autonomous systems in a wide variety of environments. However, traditional autonomous decision makers perform poorly when faced with the uncertainty, risk, and complexity of these situations. In this dissertation, I explore these problems through three distinct case studies, and make significant improvements in the performance of autonomous decision makers through the application and synthesis of concepts from decision theory, risk assessment, and computational cognition. The first case study is a terrain navigation problem which shows how the availability of information and information fidelity affect performance, and develops and validates techniques to overcome these problems. Next, an automated design problem is used to explore and evaluate techniques for handling intractably large decision spaces. Finally, a mission planning and command simulation is performed to investigate how multiple time delineated decisions can be made efficiently. Through these three case studies, I show that autonomous decision-makers can be made to perform efficiently and effectively under uncertain, high-risk, and incredibly complex circumstances.