Manufacturing an aircraft, requires scheduling thousands of tasks. The proposed schedule must respect the dependencies between tasks, take account of the uncertainty about their duration, and optimise resource usage. Resources can be tools, raw materials, aircraft parts, or worker skills.
Workers can have multiple skills and tasks require different skills, therefore workers can participate in different tasks. Resource availability and level can vary over time, for instance to account for raw material fluctuating supply or workers’ working hours and days off. Tasks should be preemptible to allow for a task to be paused when a required resource becomes unavailable (or fully used by other tasks), then restarting the task when the resource becomes available again.
Tasks are linked by precedence constraints under time windows specifying that a given task shall begin within a given time window relative to some other task’s ending time (for instance at most a given number of minutes after the end of some other task, or at the exact time the other task ends).
The scheduler will compute an initial schedule. With the environment being stochastic, the scheduler will provide schedule update propositions to an operator who will decide whether or not to follow the scheduler’s recommendation. The scheduling deviations and their frequencies should be minimized or proven to lie in a known envelope despite the environment’s uncertainties.
The scheduler should be able to explain a change to the schedule, e.g. “supply of material X will be dramatically lower in Y days, so not swapping the tasks using X with other tasks would incur a delay”). Other explanations could help the operator understand why the current schedule is infeasible (e.g. “conflicting precedence constraints between A and B vs C and D”).
Parameters of the problem are partially known. Precedence constraint relations, for instance, are not always formalised, but are known by manufacturing engineers. We can imagine a hybrid modelling of the problem where most logics are formalized but some are automatically learned from previous schedule examples, or iteratively refined by alternating a phase of solution presentation to the manufacturing engineers with a phase of model modification to account for their feedback.
STRENGTHS AND WEAKNESSES OF PURE DSSs (CO-PILOT)
ADVANTAGES OF HYBRID DSS (CO-PILOT)
In the virtual co-pilot example, taking aircraft flight decisions is beyond the scale of purely symbolic methods other than at abstract levels suited only to give advice to the human pilot, not to actually control the aircraft. ML methods like reinforcement learning (RL) can help to address this, yet may suffer from inefficiencies because realistic simulations are time-consuming in this domain. They also may suffer from a lack of robustness (e.g. changing the flight plan as a function of minor weather-prediction changes), and do not give any safety guarantees (e.g. a rare plane-crash event may average out when maximizing expected reward in RL). Hybrid methods leveraging (partly-)symbolic environment models to guide the training process, and to validate robustness and safety through approaches like testing and verification, can help to address these deficiencies.
Any decision proposed by the AI must be safe, i.e. the AI plans allow the aircraft to land safely and respect official aviation regulation, while reasoning under various uncertainties: weather, traffic, aircraft system health, the pilot’s mental stress and physical capabilities.
The AI must provide human-understandable explanations why it is required to change the current plan and why the new proposed plan solves the issue. The algorithm should be able to explain why the constraints are not satisfiable, or why the proposed decision is optimal with regard to other options (e.g. not changing the plan would lead the aircraft to run out of fuel, to hit a mountain, to divert, etc.).
There is no logical model of the planning problem’s transition function. Realistic simulators can be used to learn such a model, or they can directly feed a planning algorithm. However, realistic simulators are too CPU demanding to allow for massive data generation. Therefore, it is expected to enrich data with symbolic human-knowledge models to speed up the learning of the transition model.
The main objective of football clubs is twofold: having success on the pitch and making money over time by selling players, match tickets, and more. Clubs’ technical directors are responsible for selling and buying players and thus need to plan how their squad will evolve over the coming years. The task that we try to solve in this use case is to optimally spend the available budget on buying new players while optimizing specified objectives on and off the pitch
From a technical perspective, developing such an approach would require the following four key capabilities:
- The ability to learn the predictive models that capture the uncertainty about the future (e.g, how a player will evolve over time)
- A planner that can integrate and interact with the predictive models to plan player acquisitions
- Approaches to verify robustness properties of the outcomes – both for the predictive models and the planner
- The ability to explain the outputs of both the predictive models and the overall plan itself
There are multiple uncertainties in this task as the squad is constantly evolving due to players leaving (players sold, players retiring, players temporarily unavailable due to injuries or suspensions) and evolving (younger players improve, older players might lose speed but improve their decision making). In particular, we need to answer the following questions:
- How do a given player’s qualities evolve over time?
- How will a player’s transfer value evolve over time?
- Given a squad and all opponent squads, what will be our chances of reaching our on-pitch target (e.g. become champion, qualify for Champions League, no relegation)?
It will be crucial that the Squad Builder will not respond dramatically to irrelevant changes in the input or small fluctuations in the environment, like players playing one good match, picking up a minor injury or simply time passing by. It is preferable that the Squad Builder comes to similar conclusions during a day and won’t change its advice drastically if irrelevant things change. Scouts and technical directors will lose their trust in the solution if it turns out not to be robust and it changes its advice constantly.
Interactive explanations will be important to elucidate which types of players should and should not be considered as transfer targets and why this is the case. The ability to explain the system’s reasoning will help scouts have more trust in its output.
Management of waste collection at urban level involves sending several trucks to collect bins over a large area. The decision maker has to choose how many trucks and drivers to employ, which zones and bins are assigned to each truck, and which route should be performed by each truck. Travel times and bin levels can be difficult to estimate, and both truck capacities and shift duration cannot be exceeded. We want to keep costs low and provide high quality and fair service, all while ensuring acceptable working conditions for the drivers, and minimising impacts (e.g. traffic congestions) on the citizens.
STRENGTHS AND WEAKNESSES OF PURELY SYMBOLIC DSS IN WASTE COLLECTION
In symbolic DSS for the waste collection use case, the developer has to manually encode the available decisions and constraints: this implies that the results are interpretable to some degree. Desired behaviors can be forced by simply adding constraints. The system would return only solutions that meet all specified constraints. On the other hand, any constraint that is not explicitly known (e.g. best practices, or long-standing agreements on work shift) would be completely disregarded; some constraints may be very complex to formulate; and constraint satisfaction guarantees can still fail if quantitative estimates are inaccurate (e.g. bin levels). A data-driven approach requires either a large amount of data or to set up a simulation environment. In this case, implicit constraints are naturally taken into account and complex constraints may be easier to implement. However, it is normally difficult to explain the actions suggested by the policy, and the system may end up occasionally making critical mistakes.
ADVANTAGES OF HYBRID DSS IN WASTE COLLECTION
In the waste collection use case, travel times and bin levels may come from a ML model that relies on weekday and weather information. If the estimator and the DSS are designed and trained separately, mistakes made by the ML model may trick the DSS into making bad decisions, such as handling bins with a single truck when multiple trucks were actually needed, or forcing a driver to have an overly long working day. On the other hand, an algorithmic technique capable of training the ML model to optimize directly the DSS performance could weight errors depending on their cost, rather than on abstract accuracy. As a result, improved solutions are consistently obtained.
The process is subject to significant uncertainty regarding demand (quantity of waste), service-time duration and travel-time duration. Robust solution represents a tangible upgrade, that would improve both effectiveness and acceptability by the users.
Solutions should incorporate the key criteria used by the decision makers to evaluate quality: lack of compactness or the service of contiguous bins by different routes often reduce acceptability, even when they make sense from an optimisation standpoint. Providing advanced interpretation criteria to the user will represent a significant innovation to improve DSS adoption.
Smart Energy Systems
Explainable and robust tools to improve hourly unit commitment of multi-commodity energy plants in Smart Energy Systems.
Smart energy systems, especially in the District Energy industry, are becoming increasingly complex, managing a wide range of generation technologies, aiming to maximise not only an economic, but also environmental sets of objectives in a volatile environment both on the demand (heat/electricity) and offer (energy prices) side.
Optit has a long lasting experience developing DSS to improve management and planning of complex Combined Heat & Power plants for leading Italian and EU utilities. Based on this experience, a resolution approach was developed that spans from Demand forecasting to long (one year) to short-term (next day) planning optimization, evolving further towards intraday (same-day) energy trading. This includes use of diverse Machine Learning techniques for predictive modelling, Mixed Integer Linear Programming (MILP) models for planning modules, supported by a series of math-heuristic approaches.
STRENGTHS AND WEAKNESSES OF PURELY SYMBOLIC DSS IN ENERGY SUPPLY OPTIMIZATION
In symbolic DSS for the energy supply optimization case, the developer has a very detailed control on how the generation units are modelled, but this also requires a large set of information to be collected and set up in the model by the developer or the process engineer. There could also be a number of different solutions with very similar economic value, if not identical especially in case of storage of energy for later use (different charging and discharging patterns could have no straightforward effect on resource usage and cost), and a symbolic way, for expressing which is the “best solution” could be hard to be set up, especially in case the user is not able to express his/her preference in a formal and consistent way, beside the fact that the solver could be burdened of choosing between a huge number of solution of very similar quality. In addition, uncertainty on heat and electricity demand and prices could lead to less-than-robust solutions.
ADVANTAGES OF HYBRID DSS IN ENERGY SUPPLY OPTIMIZATION
Hybrid DSS could leverage on the user experience, first leading to more familiar and explainable results among the economically optimal (or almost optimal) ones, and second finding a plan that is hopefully less sensible to the uncertainty on heat and electricity demands and prices. This kind of results could also assist a symbolic solver in finding a plan with higher perceived quality, without losing time in considering similar plans with lower perceived quality.
The business issue presents several elements of uncertainty, like heat (or power) demand, electric market prices and production unit unavailability. Solutions need to be robust against this uncertainty, incorporating reliable predictions and tolerating prediction errors.
The capability to provide explainable and convincing solutions to the end user is a key factor for DSS adoption in this application, resulting one of the competitive factors for Optit in the market.