By performing stability analysis on an optimal tour for problems belonging to classes of the traveling salesman problem (TSP), this paper derives margins of optimality for a solution with respect to disturbances in the problem data. Specifically, we consider the asymmetric sequence-dependent TSP, where the sequence dependence is driven by the dynamics of a stack. This is a generalization of the symmetric non sequence-dependent version of the TSP. Furthermore, we also consider the symmetric sequence-dependent variant and the asymmetric non sequence-dependent variant. Amongst others these problems have applications in logistics and unmanned aircraft mission planning. Changing external conditions such as traffic or weather may alter task costs, which can render an initially optimal itinerary suboptimal. Instead of optimizing the itinerary every time task costs change, stability criteria allow for fast evaluation of whether itineraries remain optimal. This paper develops a method to compute stability regions for the best tour in a set of tours for the symmetric TSP and extends the results to the asymmetric problem as well as their sequence-dependent counterparts. As the TSP is NP-hard, heuristic methods are frequently used to solve it. The presented approach is also applicable to analyze stability regions for a tour obtained through application of the k -opt heuristic with respect to the k -neighborhood. A dimensionless criticality metric for edges is proposed, such that a high criticality of an edge indicates that the optimal tour is more susceptible to cost changes in that edge. Multiple examples demonstrate the application of the developed stability computation method as well as the edge criticality measure that facilitates an intuitive assessment of instances of the TSP.

By performing stability analysis on an optimal runway schedule, this paper derives a method to determine whether an optimized landing sequence of aircraft remains optimal after an arbitrary number of aircraft in that sequence are delayed by an arbitrary amount of time. We consider the problem of scheduling aircraft landing on a single runway with the objective of maximizing throughput under changing external conditions such as delays caused by weather. Instead of optimizing the schedule every time delays occur, stability criteria allow for fast evaluation of whether schedules remain optimal. This paper develops a method to compute stability regions for a set of schedules. Sensitivity analysis of the linear programming relaxation and a nonlinear relationship between the delay of individual aircraft and the incurred cost change for all landing sequences yield the stability information. Furthermore, the properties of a first-come-first-serve policy are studied by giving sufficient conditions and a heuristic condition for the optimality of first-come-first-serve sequences. The given results are shown to be also applicable to landing sequences obtained through local neighborhood search, sequences that obey a position shift constraint, and subsequences of landing sequences as used in a rolling horizon approach.

We propose a novel architecture for a team of machine and human classifiers (i.e., a mixed-initiative team). We adopt a model of performance that is workload-dependent for the human and workload-independent for the machine. The team is structured in a nested architecture that exploits a primary trichotomous classifier (returning true, false, or unknown) with workload-independent performance that turns over the data classified as unknown to a secondary dichotomous classifier (returning true or false) with workload-dependent performance. The novel classifier architecture outperforms other classifiers, such as a single dichotomous classifier or a simple nested two-classifier team.

This paper introduces the minimum-time arbitrarily constrained distributed scheduling problem. The optimal distributed nonsequential backtracking algorithm is used by agents to schedule tasks where the tasks are related by constraints and where the assignment of tasks to agents may change during scheduling. The problem is distributed in that no agent has full knowledge either of the communication network or of the scheduling constraints. Each agent knows the assignments of the agents with which it can communicate and the scheduled times of the tasks assigned to those agents. The minimum-time arbitrarily constrained distributed scheduling problem is for the agents to use this local knowledge to find a schedule that satisfies all constraints and minimizes the time needed to complete all tasks. The optimal distributed nonsequential backtracking algorithm is able to find minimum-time schedules that satisfy all constraints. This algorithm is designed to work concurrently with a distributed assignment algorithm that satisfies certain communication requirements detailed in this paper. This paper presents proof of the algorithm's correctness, completeness, and optimality.

This article is motivated by the need to minimize the number of elements required to establish a self-reproducing system. One such system is a self-reproducing extraterrestrial robotic colony, which reduces the launch payload mass for space exploration compared to current mission configurations. In this work, self-reproduction is achieved by the actions of a robot on available resources. An important consideration for the establishment of any self-reproducing system is the identification of a seed, for instance, a set of resources and a set of robots that utilize them to produce all of the robots in the colony. This article outlines a novel algorithm to determine an optimal seed for self-reproducing systems, with application to a self-reproducing extraterrestrial robotic colony. Optimality is understood as the minimization of a cost function of the resources and, in this article, the robots. Since artificial self-reproduction is currently an open problem, the algorithm is illustrated with a simple robotic self-replicating system from the literature and with a more complicated self-reproducing example from nature.

The objective of this paper is twofold. First, a new model of team optimization is formulated. Second, this model is used to investigate the effects of uncertainty on interaction. A model of team optimization that encompasses the classical team decision problem is introduced. This model is suitable for problems where agents' posterior information is not shared and is possibly inconsistent with the mutual prior information. For a broad class of problems, every agent's dominant beliefs about the posterior information of the other agents are derived. Then, the level of interaction and the level of uncertainty are defined, and the relationship between these two levels is studied. It is shown that the optimal level of interaction decreases as the level of uncertainty increases, and in some cases, the optimal level of interaction tends to zero, suggesting that the optimization problem may be decomposed. The theoretical results are demonstrated on sensor network examples.

We prove that for any modulation, demodulation, and coding schemes and under general assumptions on the wireless channel model, the optimal power-efficient policy for transmit power assignment is necessarily of threshold nature. Although detailed features of this policy are quite complicated, it admits a simple and practical suboptimal version. Since both the optimal and suboptimal policies may have poor location-fairness characteristics, we introduce novel performance metrics (e.g., the average downtime and uptime), which quantify the short-term behavior of these policies, and develop analytical methods for their evaluation. Using these methods, we show that, although threshold policies may be extremely power efficient, users in poor locations relative to the base station may have unacceptable short-term performance characteristics. To alleviate this deficiency, we introduce an adaptive threshold policy, in which the threshold is adjusted to the user's location, and show that it is both relatively power efficient and location fair.

This paper develops an uplink transmission scheduling scheme, referred to as Ranking CDMA, which selects a subset of users for transmission at each time slot. We introduce long- and short-term metrics that characterize its performance, and devise analytical methods for evaluating these performance measures. It turns out that, although Ranking CDMA has excellent long-term power efficiency compared to traditional CDMA, it suffers from a lack of short-term fairness, which is quantified in our calculations. To alleviate this deficiency, we propose Adaptive Ranking CDMA and analytically show that it yields moderate power-efficiency improvement over traditional CDMA, while maintaining short-term fairness.

In this paper, we prove that the optimal power-efficient transmission policy, which ensures a desired throughput in a wireless network, is necessarily of threshold nature. Although detailed properties of this policy might be quite complicated, we show that it can be approximated by a suboptimal one, which is both simple and practical. This suboptimal policy may lead to substantial improvement in power-efficiency (compared to the widely used constant SNR policy), but at the expense of location-fairness. To alleviate this deficiency, we introduce an adaptive threshold policy and show that it is both relatively power-efficient and location-fair.