A Flexible Job Shop Scheduling Representation of the Autonomous In-Space Assembly Task Assignment Problem
Joshua Moser Julia Hoffman Robert Hildebrand Erik Komendera
cs.RO 68T40



Modeling the early evolution of the COVID-19 in Brazil: results from a Susceptible-Infectious-Quarantined-Recovered (SIQR) model
    Nuno Crokidakis
    December 30, 2023
================================================================================================================================







As in-space exploration increases, autonomous systems will play a vital role in building the necessary facilities to support exploration. To this end, an autonomous system must be able to assign tasks in a scheme that efficiently completes all of the jobs in the desired project. This research proposes a flexible job shop problem (FJSP) representation to characterize an autonomous assembly project and then proposes both a mixed integer programming (MIP) solution formulation and a reinforcement learning (RL) solution formulation. The MIP formulation encodes all of the constraints and interjob dynamics a priori and was able to solve for the optimal solution to minimize the makespan. The RL formulation did not converge to an optimal solution but did successfully learn implicitly interjob dynamics through interaction with the reward function. Future work will include developing a solution formulation that utilizes the strengths of both proposed solution methods to handle scaling in size and complexity.





§ INTRODUCTION
 
As autonomous robotic systems are deployed to support efforts in industry or exploration it is vital that these systems have the ability to autonomously respond to new environments and off-nominal conditions. As in-space exploration continues to increase, with humanity returning to the moon and journeying to Mars according to the current directive for NASA, the required infrastructures will grow in scale and complexity. Constructing and maintaining these infrastructures with an astronaut workforce raises circular prerequisite errors given these infrastructures will be required to support the presence of astronauts. A solution to this integrates the use of autonomous robotic systems where these autonomous units collaboratively assemble and maintain infrastructures such as living quarters and power acquisition facilities similar to those in Fig. <ref>, prior to the arrival of astronauts <cit.>. Due to the cost of sending equipment into space and the time lost delivering it to a location such as Mars, it is not feasible to deliver pre-assembled facilities. This will lead to a variety of tasks requiring autonomous robotic attention. To ensure that a single robot's failure does not halt construction, there must be ability overlap across the different types of jobs that each robot is capable of completing. This overlap of ability between robotic units creates the possibility of many feasible assembly schemes. Solving for valid schemes that are also efficient will become more important as the number of assemblies increases. In addition to being solved before deployment, new schemes may need to be determined after work has already begun if an off-nominal occurrence causes the original scheme to be invalid.



This work seeks to provide a general problem formulation that describes the in-space assembly task assignment problem, facilitating the application of different solution methods that seek a valid and optimal assembly scheme. Additionally, two possible solution formulations were developed and evaluated. This general formulation takes the form of a flexible job shop scheduling problem (FJSP) which was then utilized in the investigation of two different solution methodologies, mixed integer programming (MIP) and reinforcement learning (RL). A MIP solution methodology was selected due to its extensive use in solving job shop scheduling problems (JSP) <cit.> and its ability to find provably optimal solutions for these problems given enough computation time. An RL approach was chosen due to its inherent ability to learn from elements not explicitly defined in the solution formulation. This ability allows for increasing interactions and prerequisites between jobs without additional complexity to the state space <cit.>. The rest of this paper is structured in the following way. Section <ref> will discuss the general problem formulation as an FJSP. Section <ref> will then define the realistic scenario used in the solution evaluations. Section <ref> will discuss the MIP solution formulation to the FJSP followed by section <ref> which will discuss the RL solution formulation. Section <ref> will describe the simulation details for the MIP and RL formulations and section <ref> will discuss the results from both of these simulations. The final section, section <ref>, will discuss the results and future research.  



§ GENERAL PROBLEM FORMULATION
 
This paper proposes framing the autonomous assembly task assignment problem as a FJSP, an extension of the JSP, where each operation can be processed on any machine. In this formulation, a given job, j ∈ J, will have a set of operations, O_jp, where p ∈ P is a processing plan defining the processing strategy. This processing strategy defines how the operations are processed by the machines (robotic units) represented as m ∈ M. Depending on the the type of operation, different types of robots will have different completion efficiencies. If r ∈ R represents a type of robot working on a specific project (a set of jobs required to complete the desired facility or structure) and q ∈ Q represents a type of operation in J then the completion efficiency for each (r, q) can be represented as an |R|×|Q| efficiency matrix, ℰ. In many projects, the work on a given job cannot begin until a different job in the project has already been completed. To efficiently represent this precedence constraint a directed acyclic graph (DAG), G(V,𝒜), is defined where the set of vertices, V, represent the jobs and the arcs, 𝒜, represent the directed precedence paths between jobs. Additionally, ℋ represents a set of these arcs that require machine-operation continuity.  In an assembly scenario, it is important to include information for the distance between different jobs in the task assignment process. These distances can be represented as the edges, E, of a completed graph, G(V,E), where the vertices are the jobs in the project.  





§ EXPERIMENTAL SCENARIO
 
To illustrate the implementation of this formulation and provide a realistic experimental example for simulation, consider a solar farm assembly scenario where robotic systems must autonomously assemble solar panels for an in-space application on the surface of the moon. For a mission such as this, it is beneficial to launch the solar panels as base components to maximize the volume usage in the delivery system. These components will then be deposited in a storage area on the edge of the project's workspace. As mentioned in section <ref>, robotic units with a range of abilities would be present to assemble these base components into solar panels. One such unit would be a large robot, capable of unloading the basic components from a lander or moving the components quickly across the workspace. NASA Langley Research Center (LaRC) has developed the Lightweight Surface Manipulation System (LSMS) <cit.> to accomplished this type of task. This assembly scenario will also require robots that are mobile and capable of utilizing grippers to: move assembly components, operate tools used for affixing components, and collaborate in the carrying of larger components. This type of robot will likely take a form akin to the rover and arm planned in the Mars 2020 mission <cit.> where a robotic arm is affixed to a rover chassis capable of traversing the terrain in the assembly workspace. The experimental robot fulfilling this role in the research presented here is the Mobile Assembly Robotic Collaborator (MARC) at the Field and Space Experimental Robotics (FASER) Laboratory <cit.>. In autonomous assembly, precise manipulation is required to align components before they are permanently affixed into place. To accomplish this type of task, LaRC has developed the Assembler robot, a serialized parallel robot consisting of modularizable Stewart platforms <cit.>. Built units of these robots can be seen in Fig. <ref>. The robots used in the following simulations are modeled after these robots. 




As a representation of the solar panel assembly, this work will model the solar panel as three components; two for the frame and one for the solar cell sheet, shown in Fig. <ref> as 1, 2, &  3. These three components will be attached via the connection points A, B, C, &  D shown in the same figure. 



To assemble this solar array, the components will need to be moved, jigged (aligned), and then affixed (welded or attached) at the connection points. These three types of jobs, represented by M, J, &  A respectively, will have operations consisting of combinations of four operation types that constitutes the set Q. The operation types and the set of operations for each job are given in Tables <ref> & <ref> respectively. The completion efficiency for each robot type to each operation type is also given in Table <ref>. To successfully assemble the solar panel, both of the frame components must first be moved to the assembly location. Following this, each component of the frame must be aligned into position with respect to the adjoining piece (for this representation only one component needs to be aligned to a stationary piece for each frame piece). Once aligned, it must be welded into place before the alignment can be released. When the frame is ready to receive the solar cell sheet, it is moved into place. One end is affixed to the frame and then the cell is unrolled before it is affixed to the final side of the frame ending the assembly sequence. The DAG representing these precedence constraints for assembling a solar panel is given in Fig. <ref> and the holding constraints are between the jigging jobs and their respective affixing jobs since the components can not be disturbed between these jobs. This representation of the solar farm assembly problem will be used in the following sections demonstrating the solution formulations to solve for a valid assembly scheme.





§ MIXED INTEGER PROGRAMMING FORMULATION




Mixed integer programming is a powerful tool for solving optimization problems and provides a way to compare solutions to calculated bounds on optimal solutions.  In particular, the backbone of commercial solvers use Branch & Bound to intelligently explore the space of feasible solutions while producing tighter bounds on how good the optimal solution could be.  As a result, a report on a measure of optimality gap (a ratio of how far the best found solution is from optimality) can be given. The formulation originally inspired by <cit.> is written to allow multiple process plans per job, allowing for different types of operations to be done to complete a job, and hence potential for faster job completion.   

The model is described in the following form. For shorthand, ∀ j, p, o, m means ∀ j ∈ J, p ∈ P_j, o ∈ O_jp, m ∈ M, respectively.  Furthermore, a specific process plane is referred to as jp and operations as jpo, to reference which job or plan they come from.  





Sets

 
 	𝒜⊆ J × J     arc set for precedence of jobs

 	ℋ⊆ J × J     operation continuity set 
 	


Parameters


	T_jpom      Operation time of m to do jpo

	S_j j' m     Setup time of m moving from j to j'




Continuous Variables (non-negative)


	  s_j       the start time of job j

	  c_j        completion time of job j

	  c_max        upper bound of completion times

	  c_jpo      completion time of operation jpo 

	  c_jm      completion time of machine m on job j
	 
	 
	 
	 
	 


Binary Variables
	 
	 
	  x_jp      plan p is selected for job j

	  x_jm     machine m is selected for job j

	  x_jj'm     machine m moves from j to j'≠ j

	  x_jpom      machine m assigned to operation jpo









Mixed Integer Programming Model


Objective function:


    min       c_max

Completion and start time constraints:
The total makespan c_max occurs when all jobs are finished, and jobs are finished when all operations for the job are finished.
Furthermore, from the DAG, jobs cannot start until preceding jobs are completed:  

    c_max   ≥ c_j≥ c_jpo   ∀ j,p,o
    
       s_j    ≥ c_j'   ∀ (j',j) ∈𝒜

If m moving from j' to j, then j must start after completion of j' and travel time of m to j: (L is a large enough number)

    s_j   ≥  c_j' + (S_jj'm+L)x_jj'm - L    ∀ j ≠ j', m

    
    c_j   ≥ s_j + T_jpom x_jpom   ∀ j,p,o,m

    
    
    
    
Assignment constraints:
Exactly 1 process plan chosen for job j:

    ∑_p ∈ P_j x_jp   = 1   ∀ j

If m assigned to operation jpo, then process plan p must be chosen for job j:

    x_jpom   ≤ x_jp   ∀ j,p,o,m

    If jp is chosen, then each  o in jp must be assigned exactly 1 machine:
       
    x_jp    = ∑_m ∈ M∑_o ∈ O_jp x_jpom   ∀ j,p

    If m assigned to jpo, then p must be chosen for j:
    
    ∑_p ∈ P_j∑_o ∈ O_jp
        x_jpom   ≤ x_jm   ∀ j,p,m

    If machine m chosen for job j, then it must have exactly one edge entering and leave that job on its path:
    
    x_jm    = x^end_jm + ∑_j'∈ J∖{j} x_jj'm   ∀ j,m 
    
        x_jm   = x^start_jm + ∑_j' ∈ J∖{j} x_j'jm   ∀ j,m

    m must have path from starting to ending node:
    
    ∑_j ∈ J x^start_jm =
        ∑_j ∈ J x^end_jm   = 1    ∀ m

Operation continuity:
for specific arcs  (j, j') ∈ℋ, if machine m does operation o̅ for j, then it must do operation o̅ for j' and it must transition to job j' next

    ∑_p ∈ P_j x_jpo̅ m   = ∑_p' ∈ P_j x_j'p'o̅ m   ∀ m, (j,j') ∈ℋ,
    
        x_jj'm   ≥∑_p ∈ P_j x_jpo̅ m   ∀ m, (j,j') ∈ℋ.

 
   
    
    
    
     
    
    
    
    





§ REINFORCEMENT LEARNING FORMULATION

As stated previously, a reinforcement learning method was chosen as a solution method in an attempt to implicitly learn some of the environment dynamics that were explicitly encoded in the mixed integer programming formulation. The chosen reinforcement learning algorithm for this evaluation was an off-policy temporal difference algorithm known as Q-learning. The Q-learning equation is defined by

    𝒬(s_t, a_t) ←𝒬(s_t, a_t) +  
    α[r_t+1 + γ amax 𝒬(s_t+1, a) - 𝒬(s_t, a_t) ].


This temporal difference method samples the environment, learning from experiences rather then a dynamics model, giving it similarities to a Monte Carlo Method while updating estimates based partially on previously learned estimates making it akin to a dynamics programming method <cit.>. This method updates 𝒬 (the action-value function) to approximate the optimal action-value function off-policy (i.e. independent of the current policy). The discount factor, γ, controls the weight of the future effect of the action chosen at time t. The learning rate, α, controls the weight at which the present value of the action-value entry is updated from the temporal difference evaluation. To evaluate if the RL was able to learn the precedent and holding constraints the action space was the same size as the state space, allowing the policy to choose any state as the next state. To minimize the total makespan a small penalty was incurred at every time step and a large penalty was given if the policy violated the precedent or holding constraints or if it tried to complete a job that had already been completed. 



§ SIMULATION

To evaluate the solution methodologies with the scenario described above, the completion efficiency values shown in Table <ref> where chosen to reflect the general ability differences of the robots described above. The general spatial layout of this simulation environment is qualitatively shown in Fig. <ref>. In this workspace, the Assembler robot is used in its disassociated state. That is, each Stewart Platform is spatially separated from the others while still being treated as a single robot unit. This is represented by the four red diamonds. Additionally, the LSMS base and its end-effector are denoted by the red hexagons while the MARC units are represented by the red triangles. The blue circles represent the qualitative spatial location of the jobs. In the simulations the spatial distances between jobs are shown in Table <ref>. The time it takes a robot to traverse this distance is the distance value multiplied by the specific robot's ability to locomote divided by a constant value (30 for all robots aside from MARC 2 which used a constant value of 25).




















 §.§ Mixed Integer Programming

For the mixed integer programming solution simulation, the setup time was the amount of time it took a robot to traverse the distance between jobs. The current model formulation allows robots to begin the simulation at any location, which is easily adjusted by changing the fix starting points.  

For this simulation only one process plan was used, which prescribed one machine per task for a given job. The operation time was the completion efficiency of the robot assigned to work on it given in Table <ref>. Using these parameters and the formulation described in section <ref> this simulation was evaluated using the Gurobi solver <cit.>. The results from this simulation will be discussed in section <ref>.



 §.§ Reinforcement Learning

The reinforcement learning simulation used the same setup and completion efficiency data as the MIP. However, due to the limitations stemming from the size of the state space, only a subset of the jobs, M_2, J_A, A_A, J_B, A_B, were used. These five jobs were chosen because they reflect the same constraints seen in the simulation for the MIP formulation. The state space for this Q-learning consisted of the five different jobs multiplied by the 24 possible different permutations based off the process plan yielding a state space of 120 entries, where each state is a job and process plan assignment combination. This leads to a state-action 𝒬-table of the size 120 × 120 since the action space consists of the next job and process plan to proceed to from a given state.  After a coarse grid search γ = 0.4 and α = 0.5 were chosen for the learning parameters. The penalty for violating a constraint or trying to complete a job already completed was -1E4 whereas a the penalty for time unit spent was -1. This RL simulation was programmed using OpenAI's Gym framework <cit.>.



§ RESULTS
 


 §.§ Mixed Integer Programming


The mixed integer program was solved using Gurobi version 9.0 and its Python API <cit.>. Computations were done on a 2014 MacBook Air laptop running macOS Mojave with a 1.7 GHz Intel Core i7, and memory of 8 GB, 1600 MHz DDR3. For the single solar panel example, the MIP finds an optimal solution within 2 seconds and proves optimality in 5 seconds. A larger example with 2 solar panels was also tested where an optimal solution was found in 26 seconds, however, the solver had trouble proving optimality. The optimal schedule output from the MIP for both cases are shown in Figs. <ref> and <ref>. Colored rectangles indicate intervals of time that a job is being worked on, while black lines indicate a machine traveling to a different job.  Some jobs are located in the same place and do not require travel time between those jobs.







 §.§ Reinforcement Learning

The number of jobs had to be reduced in order for the RL to converge to a viable, though nonoptimal, solution. This nonoptimality is highlighted by the fact that the LSMS was not chosen to complete M_2 despite it being the better choice as described in Fig. <ref>. Fig. <ref> shows that the model has converged and with additional training time the chosen actions for the given states will not change. It is important to note that the RL did not always converge to a correct schedule. Fig. <ref> shows the variance between state-action spaces. This is most likely due to the fact that the state-action space is very large compared to the number of correct state-actions it needs to learn for an optimal schedule.




 



§ DISCUSSION & CONCLUSION
 


The work presented here describes a novel application of FJSP to frame the in-space autonomous assembly problem providing a general description that can then be utilized by different solution formulations. The proposed MIP solution efficiently solved to optimality for the test instances. This approach solves the deterministic version of the problem from an offline (predetermined solution) planning perspective. This solution is ideal since it guarantees the most efficient way to complete the project. However, in this formulation, all of the precedence and holding constraints had to be directly encoded in the constraint equations. As autonomous assembly scenarios become more complex, the interjob dynamics will become harder to explicitly define. In contrast to the MIP results, the RL approach did not successfully converge to an optimal schedule. While it did learn the interjob dynamics to create a policy of decisions based on interactions with the environment thus allowing for flexible scheduling based on unforeseen circumstances, it was limited by the state space formulation. Future research will evaluate ways to combine the strengths of these two methods along with understanding stochastic elements of uncertainty to give autonomous systems the ability to autonomously learn and solve for schedules to in-space assembly projects facilitating persistent space exploration.













                                  
                                  
                                  
                                  
                                  
























ieeetr





