ADELPHI, Md. -- Have you ever faced difficulty in making a decision based on the uncertainty of the future and what it will mean for you in the long run? Army researchers developed online machine learning algorithms that can help in such decision making processes, including for Soldiers in combat when faced with tough decisions during a mission.
Many real-time decisions need to be made in military scenarios based on possibly inaccurate predictions about the future, said Dr. Shiqiang Wang, researcher at the IBM Thomas J. Watson Research Center. In these cases, he said, decisions need to be made based on the best available information at hand, while at the same time ensuring that things will not completely go wrong if the information is inaccurate.
“Our Distributed Analytics and Information Science International Technology Alliance-funded research, conducted by the University College London and IBM and supported by the Defence Science and Technology Laboratory and the U.S. Army Combat Capabilities Development Command, now known as DEVCOM, Army Research Laboratory, exactly addresses such situations,” Wang said. “Example applications of our algorithms include determining which services to run at computational nodes at the tactical edge, deciding whether to dispatch forces to a certain location of interest, etc.”
The research focuses on a classical decision making problem, where one needs to choose to either buy an item by paying a high cost upfront and no cost thereafter, or rent an item by paying a small cost for every time interval of a certain length, for example a day, when the item is in use.
This class of online rent-or-buy problems includes the ski rental problem, which first surfaced in a research paper with collaborators from SUNY Binghamton to obtain some novel insights into problems of resource allocation relevant to distributed analytics.
According to the researchers, the ski-rental problem occurs in many practical settings. For example, a computational node at the tactical edge may have limited computation, memory and storage capabilities. Therefore, only a limited set of services can be hosted at the edge.
The problem here, they said, is to determine whether a service should be downloaded and instantiated at the edge, which incurs some cost upfront, or buy, or should the Soldiers’ requests be forwarded, or rent, to a remote processing entity that has a longer response time.
The first option may be beneficial if similar requests are likely to be seen in the long run, whereas the second option can be beneficial if this type of request unlikely occurs again in the near future, researchers said.
Another example in military settings is how to best use a resource that is limited in availability and also difficult to easily relocate or reallocate, said ARL researcher Dr. Kevin Chan. Examples of this are determining where to place cameras in a specific area of a large city, deploying of personnel to a remote location, or storing large databases of information in tactical environments.
The researchers studied how to make the buy or rent decision when an inaccurate prediction on the future demand of the item is available. Different from previous work, they considered a multi-shop setting, where buying and renting can occur at different locations (shops) and one also needs to choose the most cost-efficient shop.
“We developed deterministic and randomized online algorithms to solve the problem with provable consistency and robustness guarantees, where consistency quantifies how well the algorithm performs when perfectly accurate predictions are available, and robustness quantifies the algorithm’s performance in the worst case with the most inaccurate predictions,” Wang said. “Our algorithms include a control parameter that can trade-off between consistency and robustness. In this way, we can perform well when the prediction is accurate, and at the same time not too badly when the prediction is inaccurate. Experiments with both synthetic and real datasets validate the effectiveness of our algorithms.”
Similarly, another algorithm developed related to this research enables a team of agents to collaborate, said Dr. Mark Herbster, senior lecturer in the Computer Science Department at the University College London.
The researchers consider a model of online prediction in a non-stationary environment with multiple interrelated tasks. An asynchronous data stream is associated with each task.
As an example, Herbster said, consider a scenario where a team of drones may need to decontaminate an area of toxic waste. In this example, the tasks correspond to drones. Each drone is receiving a data stream from its sensors. The data streams are non-stationary, but interdependent as the drones are travelling within a common site. At any point in time, a drone receives an instance and is required to predict its label. The aim is to minimize mispredictions.
“This research uses an approach called multitask learning using experts,” Chan said. “The problem is to understand how to optimally switch between a set of configurations or experts to best serve a series of tasks.”
The research also includes the concept of long-term memory in online learning, Chan said, which is designed to prevent the problem of catastrophic forgetting. This is the case where a system adapts to new information without forgetting the old information. It is a balance between adapting to new information while not forgetting information learned from past experiences.
According to Chan, these research efforts will enhance the Army network by providing innovative online learning research that takes steps towards realizing dynamic and effective capabilities to configure and adapt complex networked systems. This is a key aspect of the DAIS ITA Technical Area Dynamic of Secure Coalition Information Infrastructures, he said.
Scenarios where this research could be implemented in the future include strategies to understand how to deploy services and applications such as machine learning models and data on mobile platforms.
“Given that the information environment will be increasingly complex, we need to understand where to place and relocate applications and data throughout coalition resources,” Chan said.
The next step for this work will be to consider the extension of this theoretical framework to a broader range of problems of interest.
“The research is broadly applicable to providing optimal resource allocation, where we have focused on the problem of configuring and deploying services and infrastructures to joint and coalition operations where resources are limited, but can be leveraged and exploited across multi-domain, multinational organizations,” Chan said. “These capabilities have the potential to address other issues that must operate in a complex environment with a variety resource constraints such as size, weight, power consumption, or SWaP, and Delayed/Disconnected, Intermittently-Connected, Low-Bandwidth, or DIL, networks.”
Researchers presented their results at the NeurIPS 2020 international conference, a premier venue for machine learning research.
DEVCOM Army Research Laboratory is an element of the U.S. Army Combat Capabilities Development Command. As the Army’s corporate research laboratory, ARL is operationalizing science to achieve transformational overmatch. Through collaboration across the command’s core technical competencies, DEVCOM leads in the discovery, development and delivery of the technology-based capabilities required to make Soldiers more successful at winning the nation’s wars and come home safely. DEVCOM is a major subordinate command of the Army Futures Command.