• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The present invention relates to a method for assigning a set of tasks to at least one mining and/or construction machine (200A, 200B;701-703), said machine (200A, 200B;701-703) being arranged to be driven between positions for performing tasks. The method includes: - defining a first set of constraints to be fulfilled when assigning said tasks to said at least one mining and/or construction machine (200A, 200B;701-703); - finding a solution fulfilling said first set of constraints by solving each constraint as a sub-problem, the solution to at least one sub-problem being dependent on the solution of at least one other sub-problem; - said solution fulfilling said first set of constraints being a solution where a first of said sub-problems is validated by solutions of others of said sub-problems, and - assigning tasks to said at least one machine (200A, 200B;701-703) according to the determined validated solution.Fig. 3
    公开号:SE1551256A1
    申请号:SE1551256
    申请日:2015-10-01
    公开日:2017-04-02
    发明作者:Lundh Robert；Joyce Stephen；Mansouri Masoumeh；Andreasson Henrik；Pecora Federico
    申请人:Atlas Copco Rock Drills Ab；
    IPC主号:
    专利说明:

    lO METHOD AND SYSTEM FOR ASSIGNING TASKS TO MINING AND/ORCONSTRUCTION MACHINES Field of the invention The present invention relates to operation of mining and/orconstruction machines, and in particular to a method forassigning tasks to mining and/or construction machinesaccording to the preamble of claim l. The invention also relates to a system and a mining and/or construction machine.
    Background of the invention In mining and tunneling, for example, there is a constantongoing process of improving efficiency, productivity andsafety. Examples of changes/improvements that are carried outto an increasing extent, perhaps in particular in mining, isthe automation, fully or partly, of various processes occurring in mining.
    It is, for example, often desirable that at least part of thevehicles/machines that are used in mining/tunneling can bedriven fully autonomous, i.e. without an operator beingrequired to influence the control/operation. In fact, theoperation of autonomous vehicles/machines are more and morebecoming key components in mining and construction. Methodsfor localizaticn, mapping, control and motion planning have enabled development and deployment of autonomous vehicles.
    Summary of the invention It is an object of the present invention to provide a methodfor assigning tasks to mining and/or construction machines.This object is achieved by means of a method according to claim l. lO The present invention relates to a method for assigning a setof tasks to at least one mining and/or construction machine,said machine being arranged to be driven between positions for performing tasks. The method includes: - defining a first set of constraints to be fulfilled whenassigning said tasks to said at least one mining and/or construction machine; - finding a solution fulfilling said first set of constraintsby solving each constraint as a sub-problem, the solution toat least one sub-problem being dependent on the solution of at least one other sub-problem; - said solution fulfilling said first set of constraints beinga solution where a first of said sub-problems is validated by solutions of others of said sub-problems, and - assigning tasks to said at least one machine according to the determined validated solution.
    The present invention, consequently, provides a method forassigning tasks to at least one machine. This machine can be amanually operated machine or an autonomous machine. When themachine is working autonomously, the assigned tasks can bedispatched, communicated, to the machine, which then carriesout the tasks. It is also contemplated that the machine is amanually operated machine, in which case the tasks can stillbe determined according to the invention and communicated tothe machine, where the tasks can then be displayed to anoperator when performing the tasks using the machine and guidethe operator to maneuver the machine in a manner fulfilling the constraints. lO The assigning of tasks according to the invention can furtherbe arranged to assign said tasks to a plurality of miningand/or construction machines, which can be autonomous machinesor manually operated machines, or a combination thereof.Furthermore, the machines may be arranged to be autonomouslydriven between positions for performing tasks. Tasks of saidset of tasks can be arranged to be carried out at leastpartially overlapping in time by a plurality mining and/orconstruction machines. That is, machines can be carrying out different tasks of said set of tasks concurrently.
    With regard to mining and construction, there are importanthindrances when it comes to employing a plurality ofautonomous vehicles simultaneously. Fleet automation, i.e. theoperation of a plurality of machines simultaneously, ofteninvolves solving several, strongly correlated sub-problemssuch as allocating tasks to vehicles, planning vehiclemotions, and vehicle coordination. This makes solving theoverall problem of assigning tasks difficult. The inventionprovides a solution to solving such problems. According to thepresent invention, it is provided a method where a solution toa problem of assigning tasks to autonomously operatingmachines is obtained, where the number of tasks to beperformed can be large, e.g. in the order of 30 or more, andwhere the solution can accommodate one or multiple machines and tasks can be performed at least partially concurrently.
    The assigning of said set of tasks can therefore be solved asa higher level constraint satisfaction problem, a solution tothe problem of assigning said set of tasks being searched fromsolutions to said sub-problems, each of said sub-problems being solved as a lower level constraint satisfaction problem lO providing a solution to constraints of the higher level constraint satisfaction problem.
    According to the provided solution, the problem of assigningtasks is stated as a set of tasks to be assigned to themachines given a set of constraints with regard to theassigning and carrying out of the tasks. That is, a set ofrequirements that must be fulfilled when the tasks are carriedout. These requirements, in turn, are arranged to form sub-problems, which are solved sub-problem by sub-problem, butwhere sub-problems depend on each other, so that a solution ofone sub-problem will be dependent on the solution of anothersub-problem. According to the invention, this is accounted forwhen searching an overall solution from the solutions of sub-problems by requiring a first sub-problem to be validated by solutions to other sub-problems.
    The solution to the assigning of said tasks is found byvalidating a solution to one of said sub-problems by solutionsof the others of said sub-problems. That is, the solution to asub-problem is considered a valid solution, if the solutionallows solutions also of the other sub-problems that fulfillthe given constraints. Consequently it is ensured that a sub-solution is such that it does not prevent other sub-problems from being solved.
    If a solution to a first sub-problem is not validated bysolutions to other sub-problems the solution to the first sub-problem is discarded and another solution to the first sub-problem be searched and be validated by solutions to othersub-problems. This can be iterated until a solution has been found that fulfills all sub-problems. lO A common representation of the sub-problems can be used, wheresaid tasks are represented by variables. In this way, solveralgorithms of the sub-problems share a common search spacewhen searching a solution to a sub-problem so that thesolution to a sub-problem can be validated by solutions to other sub-problems in an efficient manner.
    The use of constraints substantially reduces allowablesolutions, with the result that much less computational power is required to solve the overall problem of assigning tasks.
    Consequently, according to the invention, the overall problemis divided into a plurality of sub-problems and the mutuallyfeasible solutions to the individual sub-problems are found, where solutions from different sub-problems are combined.
    Furthermore, a heuristically guided backtracking search can beused to find a solution to the overall problem in the joint search spaces of the sub-problems.
    Priorities can be assigned to said sub-problems, so that asolution to the assigning of said tasks can be determined byvalidating a solution to a higher prioritized sub-problem bysolutions to lower prioritized solutions. In this way, it canbe ensured that sub-problems that depend on the existence of asolution of another sub-problem are solved after such solution exists.
    When solving the assignment of tasks, a representation of the tasks to be carried out by means of said machines can be used.For example, the representation may include positions at whichthe tasks are to be carried out, and also data regarding what the task consists of. A representation of said machines can also be used when solving the assignment, where the lO representation of the machines may include a representation of speed and capacity, e.g. in the form of drilling or loading.
    The tasks can be arranged to be carried out within a borderconfining a geographical area, where the machines are not allowed to cross the border.
    According to one embodiment it is determined start times andend times for performing each of said tasks, the start timesand end times of a task being defined in relation to starttimes and end times of the other of said tasks, and saidassignment of said tasks including a start time and end timefor performing said tasks. In this way, machines can bescheduled to perform tasks such that they do not collide when operating in overlapping geographical areas.
    During operation, i.e. when actively performing said tasks,progress data regarding fulfillment of said tasks can betransmitted from said machines, and start times and end timesof the tasks can be recalculated on the basis of receivedprogress data, so that it can be accounted for e.g. taskstaking shorter or longer periods of time to carry out than expected.
    Furthermore, an estimated time of completion and/or time tocompletion of said set of tasks can be determined, anddisplaying said estimated time of completion and/or time tocompletion. In this way, other work, such as other kinds oftasks, to be carried out after the tasks have been completed,e.g. by means of other machines can be scheduled in a cost- effective manner.
    The estimated time of completion and/or time to completion ofsaid tasks can be updated on the basis of progress data received from said machines when carrying out said tasks. In lO this way, a proper estimate can always be obtained, e.g. if the performance of the tasks takes longer than expected.
    The problem of assigning tasks to said machines can bearranged to be re-determined when work is ongoing e.g. ifmachines communicate deviations requiring a re-assignment ofsaid tasks. For example, a machine may suffer a break down, ortasks may take longer than expected to carry out so that tasksmust be reassigned to other machines. Occurrences of this kindcan be accounted for by re-determining the assignment of tasksin view of the changed conditions, so that the ongoingcarrying out the tasks can be continued, however with changes in the assignment of tasks to machines.
    The assigning of said tasks can further include a constraintsuch that, when said machine has finished assigned tasks, adefined end position can be reached by a machine withoutviolating allowed movements within the area in which saidtasks are being carried out. In this way it can be ensuredthat the machine can be moved away from the work area, e.g. ifblasting is to be performed, without destroying work performed by tasks that has been carried out.
    The assignment of said tasks can be performed from a locationremote from at least one of said machines, e.g. from one ofthe machines, or from a control center being separate from all of the machines.
    The invention also relates to a system and a mining and/or construction machine.
    Brief description of the drawings Fig. l shows a surface pit-mine drill plan and geofence restricting machine movements. lO Fig. 2 shows a drill rig which can be utilized according to the invention.
    Fig. 3 shows an exemplary method according to embodiments of the invention.
    Fig. 4A shows an example of decisions in a sequencing of tasks sub-problem according to embodiments of the invention.
    Fig. 4B shows an example of approach angles for drilling for a subset of holes to be drilled.
    Fig. 5 shows a motion pattern of a drill rig close to a geofence.
    Fig. 6 shows a suggested sequence pattern for use when sequencing tasks near geofences.
    Fig. 7 shows an example of scheduling of work of three machines to avoid collisions.
    Detailed description of a preferred embodiment Embodiments of the invention will be exemplified withreference to a specific problem in a mining application. Theinvention is, however, applicable in various other miningapplications as well. Also, as explained above, the inventionis applicable also when only one machine is present, and when the one or more machines are manually operated.
    However, according to the example discussed in the following,a fleet of, i.e. a plurality of, surface drill rigs arearranged to operate autonomously and concurrently within ashared area of the open-pit mine, called a bench. Rock/oreexcavation in mines of this kind often involves drilling of a set of drill targets in the bench. That is, at each predetermined target (position) a blast hole is to be drilled.The blast holes are then filled with explosive material thatis detonated after all targets have been drilled. After theexplosion, the ore is taken away and processed for mineral extraction.
    An example of a bench 100 is shown in fig. 1, where aplurality of holes (drill targets), indicated by a largenumber of black dots 101, are to be drilled for subsequentblasting. The geographical area making up the bench 100 isoutlined and defined by an outer boundary 102, which, as willbe explained below, indicates a geographical area to which themachines are confined and must not traverse in order to avoidaccidents and/or collisions with surrounding obstacles such as rock. The boundary 101 thus constitutes a geofence.
    Each drill target 101 can be seen as a task to be carried out,where a machine (drill rig) autonomously carries out a set ofsub-tasks when completing the task of drilling the hole. Thesesub-tasks may e.g. include auto-tramming (automaticallynavigating) to the target (drill position) from its currentposition, leveling the drill rig (deploying jacks for levelingthe machine in position for drilling, e.g. horizontally),drilling, de-leveling (retracting the jacks so the machine isplaced back on its tracks) and moving away from the drilledhole. Fig. 1 further shows two drill rigs 200A, 200B which areto be used to drill the bench 100, and a control center 106 inwhich e.g. calculation according to the invention can be arranged to be carried out.
    Fig. 2 discloses an exemplary side view of a drill rig 200which may be utilized in a solution according to embodimentsof the invention for drilling holes of a bench according to fig. 1. The drill rig 200 is only exemplary, and there exist various kinds of drill rigs of various designs that can beused according to the invention. The drill rig 200 constitutesa surface drill rig being used to drill vertical orsubstantially vertical holes using a drill tool attached to adrilling machine via a drill string. The drilling machine isslidably arranged along a feed beam. These elements areconventional and not explicitly disclosed. Instead they arerepresented by a drill tower 201 and a schematically indicateddrill string 203 indicating ongoing drilling. The generaltechnology used when drilling using a machine according tofig. 2 is well known per se. Drill rigs may also comprise adust guard 202. Drill rigs may be provided with a dust guardor other kinds of means which to be positioned around thedrill bit during drilling to reduce dust from unnecessaryspreading to ambient air and surrounding ground during drilling.
    The drill rig 200 also comprises crawlers or wheels 205 toallow the drill rig 200 to be moved from one position to another, such as from hole to hole to be drilled.
    The drill rig 200 further comprises a control systemcomprising at least one control unit 206, which controlsvarious of the functions of the drill rig 200 and inparticular operation of the drill rig according to embodimentsof the invention, where the control unit can be arranged tocontrol crawlers, drilling machine etc. by suitable control ofvarious actuators/motors/pumps 207, 208 etc. Drill rigs of thedisclosed kind can comprise more than one control unit, whereeach control unit, respectively, can be arranged to beresponsible for different functions of the machine. Thecontrol system of the drill rig 200 further comprises transceiver means 209 for receiving instructions regarding 11 tasks to be performed and controls crawlers, beam, drillingmachine etc. to carry out the received instructions, and toallow data to be transmitted from the drill rig e.g. to acontrol center, the data e.g. including current work data suchas position, current progress when drilling a hole, completion of a task etc.
    The present invention provides a solution that can be utilizedto use a plurality of autonomous drill digs for automaticallyand simultaneously performing e.g. drilling of holes accordingto a bench 100 according to fig. 1, where drill rigs may bemaneuvered within overlapping portions of the bench 100 while simultaneously being confined to stay within the geofence 102.
    Such autonomous drilling gives rise to a number of problems tobe solved. As drilling across the bench 100 progress, piles ofdrill cuttings will be accumulated at each location where ahole has already been drilled, and hence a drill rig need notonly take the immediately drilled hole into consideration, butthe drill rig must also avoid piles that have accumulatedduring previously drilled holes. The distance between holesmay e.g. be in the order of 0.5-2 times the machine length,which, as drilling progress, may render maneuveringcomplicated to avoid piles from previously drilled holes whilesimultaneously staying within the geofence. Also, drillingmust be performed such that the machine when the drilling ofthe holes of the bench 100 is finished, is not “locked in” bypiles of already drilled holes, but is able to move away fromthe bench, or to a particular position within the bench, prior to blasting.
    A bench may comprise a relatively large number of holes to bedrilled, e.g. in the order of 30-2000. Since drilling of a single hole inherently takes some time use of a plurality lO l2 (i.e. at least two) of concurrently operating drill rigs mayconsiderably reduce overall time for completing drilling ofthe bench so that blasting can be performed at an earlierpoint in time. This imposes additional aspects that must beattended to when performing autonomous drilling using aplurality of machines. For example, it must be ensured thatdrilled holes by one machine do not prevent drilling of holesfor the one or more other machines. Also, it must be ensuredthat drilling performed by one machine does not hinderdrilling of holes for another machine. In addition it must beensured that the machines do not collide with each other, i.e. are not present at the same location at the same time.
    The automation of the operation of the fleet of autonomousoperating machines involves solving of a plurality of problemsthat are strongly correlated. This makes solving the overallproblem difficult, since a large number of solutions exist foreach problem, thereby rendering it difficult from acomputational point of view to find a common solution thatsolves all problems in a manner that also fulfills the furthercriteria, constraints, that usually must be met to obtain aworking solution. Obviously, there are a huge amount oftheoretical possibilities that can be evaluated in order tofind a solution that works, thereby requiring large amounts ofcomputational power. For example, in addition to the largenumber of holes to be drilled, these may be drilled fromvarious directions with respect to a reference direction,different holes can be drilled by different machines etc. Thisrenders solving of the problem complex. As will be explainedbelow, it is preferred if changes to a determined way ofassigning drilling of the holes to the various machines can be carried out underway as drilling progress. lO l3 According to the present invention, constraint satisfactionproblem (CSP) solution is utilized to facilitate problemsolving. CSP is well known per se and therefore not describedin detail. The invention utilizes a two level CSP methodologythat results in an efficient way of solving problems involvingassignment of tasks to a plurality of autonomously operatingmachines that operate in overlapping portions of a geographical area.
    The Drill Pattern Planning Problem of drilling the bench lOOof fig. l (denoted DP3 in the following) consists of computinga drill plan that involves machines (drill rigs) reaching eachdrill target in the bench lOO and performing the necessaryoperations to drill the blast holes. The problem of assigningthe drilling of the holes to a plurality of machines may be subject to the following requirements: - Machines should not collide with obstacles/each other when moving from one target to another; - Drill piles resulting from drilling constitute obstacles that must not be run over by dust guard or other machines; - Once drilling has been performed, the machine is limited inchoice of movement when moving away from the drilled hole.According to the present example, the machine can only driveaway from the target by backing after raising the forward dustguard 202a since this is the only part of the dust guard that can be actuated according to the present example); - Motions should be executable by the machines i.e., motionsshould be kinematically feasible. Hence, the planned motions of the machine must be able to be carried out in reality; 14 - It should be possible to modify the resulting solution oncedrilling has started to account for events that occur once drilling has commenced; - The plan should respect spatial constraints with regard topossible movement of the machines. For example, a geofence according to the above must oftentimes be defined and withinwhich the vehicles must operate to avoid collisions with e.g. surrounding rock or other obstacles or driving over edges.
    An exemplary method 300 according to the invention isdisclosed in fig. 3. The method can be arranged to be carriedout by calculating/computing means, such as a computer orcontrol unit e.g. in a control center 106 or other remotelocation in relation to the drill rigs being utilized fordrilling the bench. According to embodiments of the invention,means, such as calculating/computing means, are included inone or more of the drilling rigs 200A, 200B. For example, themethod can be controlled by one drilling rig instructing the one or more other drilling rigs participating in the task at hand.
    The method of fig. 3 starts in step 301, where it isdetermined whether a drill plan problem consisting ofassigning tasks to autonomously operating machines, in thisexample drill rigs 200A, 200B is to be carried out. When thisis the case the method continues to step 302. In step 302 itis determined if required data to assign the tasks have beenreceived. For example, with regard to the present embodiment,this data comprises the locations of the drill targets, i.e.the positions of the holes 101 to be drilled, and the geofence102 defining the bench 100. The drill targets and geofence areoftentimes based e.g. on a geological survey of the area and on the current production plans of the mine. This data is input into the system prior to solving the drill plan problem DP3. Also other restrictions and heuristics may be input.
    The set of machines to be used for accomplishing the task ofdrilling the holes, in the present example drill rigs 200A,200B, are also determined beforehand, and in general selectedon the basis of the problem at hand, where the size of a fleetof drill rigs to be used can be based e.g. on the size of thebench to be drilled. Also, different kind of machines may berequired if holes of different diameters are to be drilledaccording to the drill plan. The number of and/or types ofmachines being available for the task at hand are input to thesystem. Further input may include initial positions of allmachines, i.e. their current location or user defined startingpositions, as well as desired final “parking” positions of themachines, e.g. in terms of an allowed area or position atwhich a machine is to be located once the drilling of the bench is completed.
    When it is determined that required data has been received theassignment of tasks when drilling the drill plan is calculatedin step 303, including time to completion estimation,according to the below. Steps 300-303 can be performed offlineto compare different scenarios, e.g., different number ofmachines. In step 304 tasks are dispatched, i.e. communicatedto machines. In step 305 progress data is received regardingthe completion of the tasks, and in 306 it is determinedwhether a recalculation of the solution is to be performed. Ifso the method returns to step 303 for recalculation. In step307 the time to completion of all tasks is updated, e.g. basedon tasks taking longer than expected etc. as explained aboveand below. Also, time windows for performing tasks can be updated on the basis of actual progress of performing the 16 tasks. In step 308 it is determined if the tasks have beencarried out, and if so, the method is ended in step 309. If not, the method returns to step 305.
    The calculation in step 303 is carried out according to thefollowing. The requirements set out above regarding the drillplan problem DP3 pose several problems e.g., task allocation(of machines to target poses), motion planning, andcoordination. These problems cannot be treated separately andindependent from each other, since the solutions of eachproblem depend on each other. For instance, coordination mustlead to a sequence of target poses that accounts for the pilesgenerated after drilling (which become obstacles that must be taken into account in motion planning).
    Hence, it is necessary to subject the possible choices made tosolve one problem to the choices made in resolving the otherproblems, e.g., verifying through motion planning that achosen sequence of targets to drill will be kinematicallyfeasible in reality. Because of these interdependencies, thedrill plan problem is a hybrid reasoning problem. According tothe invention, an approach is utilized in which the overallproblem (e.g. drilling the holes of fig. 1) is divided intosub-problems, and the solution to the overall problem is searched for in the joint search space of these sub-problems.
    The drill plan problem according to the present example can be divided into five sub-problems.
    - A sequencing sub-problem. This sub-problem consists ofdeciding a total ordering of targets i.e., sequencing everypair of targets so that it is determined in which order targets (holes) are to be drilled. 17 - A motion planning sub-problem. This sub-problem consists ofdeciding the pose, alignment, of the drilling machines at eachtarget. That is, it is determined the alignment of the machinein relation to e.g. a reference direction for each hole to bedrilled and also the space required and traversed when movingfrom one hole to another. The alignment should be such thatthe holes can be drilled without disturbing piles of alreadydrilled holes, and also ensure that the machine can move awayfrom the drilled hole. Constraints on the orientation of themachine in certain target poses may be given (e.g., due to thepresence of the geofence or other geographical constraintslike cliffs and walls present within the area to be drilled.The decisions are subject to kinematic constraints, obstaclesand geofence, and must account for piles resulting from drilling, as well as the dust guard mechanism.
    - A machine allocation sub-problem. This problem consists ofallocating machines to targets given the available machinesand their positions. Machine allocation also accounts for the need to reach a given end parking position.
    - A coordination sub-problem. This sub-problem consists ofscheduling machines. Solutions to this sub-problem considerspatio temporal overlap between machines, i.e. machines maytraverse a same geographical point at the same or differentpoints in time. The sub-problem also consider overlap betweenmachines and piles, i.e. it must be ensured that piles generated by one machine are not run-over by other machines.
    - A temporal sub-problem consists of deciding when machinesshould carry out motion, drilling, leveling and de-levelingoperations, subject to temporal constraints arising from coordination, sequencing, maximum achievable speeds, etc. 18 According to present example, Constraint Satisfaction Problem(CSP) solving is used to obtain a solution to the posed drillplan problem. CSP is well known per se, and hence the actualrealization of the solving of the sub-problems when criteriaare set can be performed in a conventional manner. A solutionto the overall problem is obtained by reasoning upon thesefive different sub-problems jointly. Candidate solutions for asub-problem are validated by dedicated solvers. Each solverfocuses on a subset of aspects of the overall problem, e.g., amotion planner verifies kinematic feasibility and absence ofcollisions, while a temporal solver verifies that coordinationchoices are temporally feasible. Validated solutions for eachsub-problem can be seen as constraints that account forparticular aspects of the overall problem. They can bemaintained in a common representation, which is sufficientlyexpressive to model the search space of all sub-problemsjointly. The common representation can constitute a constraint network where variables represent tasks.
    According to the present example, a task is represented by a tuple Å{=(gpJpJgP§m,&Y§A), where r represents the machine (drill rig) which should perform the set of activities A ={drilling,leveling,de-leveling} at, respectively, starting pose gp and goal pose gp.
    P is the path that r traverses to reach gp from Q), and is computed based on a map n1 of the environment (bench and drill holes).
    S is a set of polygons representing sweeps of the machine's footprint over P when moving from Q to gp» and 19 T is a set of time intervals representing when r will be ineach polygon contained in S. The time intervals can e.g. beabsolute time intervals, or time intervals with reference to astart time at which the drill rigs begin drilling the drillplan.
    Henceforth, ÅIQ) denotes an element of the task tuple.
    Let M be the set of all tasks in the overall problem at hand(one for each drill target). A solution to the overall problemis such that a value is decided for all elements of a task,for each task in Ål E M. Each element is decided by solving one or more sub-problems.
    Consequently, a task Ål can be viewed as a variable in aConstraint Satisfaction Problem whose domain represents allpossible combinations of values that can be given to eachelement of Ål. Accordingly, a sub-problem can be viewed as theproblem of constraining the domains of tasks so therequirements stated above are met. Hence, the solvers thatvalidate solutions to the sub-problems are seen as proceduresthat post constraints to the common constraint network. Aswill be explained, adopting the CSP metaphor allows employmentof heuristic search strategies for solving the overall problem.
    The sub-problems listed above will be discussed in the following.
    Sequencing sub-problem The sequencing sub-problem consists of finding a total order of the tasks to be performed. A decision variable of this sub- problem is a task AA E M that does not have a preceding task.
    A possible value that can be assigned to this decision variable is a precedence constraint Alj precedes AI, asserting l that task Alj E M should occur before Ali. Ålj is a task for which it has not been already decided that it precedes anothertask. A sequencing solver verifies that tasks are totallyordered. Fig. 4A shows an example of decisions in this sub-problem. Fig. 4A discloses a portion of the bench of fig. 1near the geofence 102 where the machine has to perform a turn.As can be seen the order of drilling the holes closest to thegeofence is changed from the pattern before (consecutive) andafter (also consecutive) the turn at the geofence. Inparticular, the order is 166 -> 137 -> 168 -> 167 -> 138 ->139 etc. The actual track of machine movement when performingthe drilling close to the geofence may be relativelycomplicated, as will be seen below, in relation to thedrilling of holes along a straight line, where movement pattern is straight forward (e.g. along a straight line).
    Motion planning sub-problem The motion planning sub-problem consists of finding a goalpose gp for each task Aß E M. A gp is a tuple in whichx and y represent the (geographical) position of a drill target on the bench, and 0 is the orientation of the machinein relation e.g. to a reference direction. The decisionvariables of the motion planning sub-problem are tasks AI such l that: (1) Ålfigp) does not have a defined orientation, i.e., 0 is not assigned to an angle, lO 2l (2) there exists Alj precedes Aßin the common constraint network, and (3) Ålfigp) has been assigned an orientation.
    The number of possible values that can be assigned to adecision variable can be any suitable number of angles, wherea limited set of angles can be used e.g. improve computational efficiency. According to the present example, a set of eightangles fiÅw,9Jæ¶b2n] are used, which can be evenly distributedover a full rotation.[Q2fl]. A particular choice of approachangle for a target is only feasible if the machine can drive away from the previous target Ålfigp) and navigate to the end pose of a task Alfigp) considering piles created by all the preceding tasks.
    For example, Figure 4B shows a selection of one feasibleapproach angle for some of the tasks discussed with referenceto fig. 4A and hence with respect to existing sequencingconstraints. The approach angles are represented by arrows,and the machines drive away from the targets in the opposite direction of the arrows.
    The eight possible assignments to the decision variable determine eight different possible end poses of the machine{Å4Ågg),...,A4ÅgpQ}, which differ only in the orientation ofthe machine in the goal pose. A possible assignment Ok isvalidated through a path planner, which is given the triple(ALQ¶Û,A4Ågg),A4Åm)), where the start pose is the goal pose ofthe preceding task (ÅLQ¶O=AlÄgp)), and Alfim) is a map of the environment that contains obstacles and a geofence. The obstacles correspond to circular shapes centered in the goal lO 22 poses of the preceding tasks. Through the map Alfim), the pathplanner accounts for targets that have already been drilled prior to task AL.
    The path planner may be invoked potentially several timeswhile solving the motion planning sub-problem. With regard tothe path planner, for example, any suitable path planner canbe used, e.g. a path planner for a car-like mobile robot basedon cubic spirals. Such path planners are known in the art, andcomputes paths consisting of curvature-constrained curvesconstituted by few cubic spirals and straight lines. The output of the path planner is either fail, which indicates that a particular approach angle Ok cannot be achieved, or thespline AIÅP), representing a kinematically-feasible and obstacle-free motion from AL(gÛ to Alfiggj.
    Machine allocation sub-problem In this sub-problem, a decision variable is a set M' §;M such that V1M'(EM', A10) has not been decided, and AI precedes Ål V A1 precedes Alu l l HM, en' That is, a total order of tasks has been decided, but machineshave not yet been allocated. The values are completeassignments of machines to tasks, i.e., an assignment A10) = Rfor each task in M'. The machine allocation sub-problem has ahuge space of possible solutions. Each possible solution hascomplex ramifications on other sub-problems: differentallocations will affect the amount of coordination necessary;allocations must be such that the final task of a machine is not surrounded by piles (drilled by other machines), which lO 23 would make it impossible to navigate to its final parking pose.
    Heuristics with high pruning (skipping) power can be used toexplore the search space of this sub-problem, and theseheuristics must account for other sub-problems. For example,the solver can be guided towards solutions where drill targetsare assigned in rows as much as possible, e.g. least possiblechange in direction of the drill rig for as long rows of holesas possible, and where directions can be given regardingpreferred orientations of the rows. Such data can be inpute.g. by an operator. Heuristics are discussed further below.Solutions to the machine allocation sub-problem are indirectlyvalidated in other sub-problems, hence no particular solver is used for direct validation of possible values.
    Temporal sub-problem A task's path I) is segmented into a sequence of sub-paths based on its curvature. Each segment can e.g. be associated toa convex polygon sk resulting from the sweep of the machine'sfootprint along the sub-path. The resulting sequence{q,...,sm} of convex polygons represents the areas occupied by a machine while navigating along the path. While navigationalong a line of holes can give rise to a very simple movementpattern (straight line), the movement pattern close to thegeofence can be considerably more extensive. Problems becomemuch more difficult if they contain drill targets that areclose to the geofence, whereas when that is not the caseproblems are easier, since machines have enough space tomaneuver regardless of how approach angles are chosen. This isillustrated in fig. 4C, which shows polygons representing footprints when moving from l66 of fig. 4A to l38. Obviously 24 the movement pattern becomes considerably more complex beforehole 140 of fig. 4A has been reached, which according to theexample (see fig. 4B) is the first hole where the machineagain is aligned with the row of holes. This is schematically illustrated in fig. 4D.
    Since the path planner that is used to obtain P is aware ofthe obstacles created by preceding tasks, the convex polygonsdo not intersect piles resulting from drilling. This isillustrated in fig. 5, where black circles represent drillpiles (the orientation of the drill rig is also when drillingis also indicated by arrows), polygons represent the motions of the machine. As can be seen drill piles are not touched.
    In addition to the polygons representing the motion ofmachines, the activities involved in a task Ål (i.e., Å1@®={drilling,leveling,de-levelinq}) have polygons associated tothem. Since these activities all occur while the machine isidle in pose Ålqgfl, their polygons, in the present example,since drilling is performed substantially vertical, coincide with the polygon that covers the last sub-path of AIUÖ. Hence, the set of all convex polygons of task A4 isAl(S)={s1,.. - r sm { Sdrilling/ Sleveling/ Sde-leveling} r Where Sdrilling I Sleveling I Sde-leveling I sm - Each convex polygon in ÅIQÜ is associated to a time interval in the set ÅIÜÜ = {@,...,IWß}. Interval Ik = [IS,Q] is a flexible temporal interval within which machine A10) is in sk, where Is = [I S 1713]/ I :il 6 6 ,u.],l S M,uNe EN represent,respectively, an interval of admissibility of the start and end times of the occurrence of polygon sk E S. lO The temporal sub-problem consists of deciding a start and an end time for each interval Ik. The temporal sub-problem has a decision variable for every machine IÉER.
    Each decision variable is a set of tasks M' Q M such that for all Aß EM': (l) AIÅP) has been decided, (2) AßU)=R, and (3) the start and end times of AJÅT) have not been decided.
    The problem of deciding valid start/end times of the intervalsis reduced to a Simple Temporal Problem (STP). STP:s are wellknown and various algorithms exist for solving STP:s. The STPcan be formulated as a collection of temporal constraints as follows.
    First, for each Å4¿(EM' with intervals ÅIÅT) = {I¿,...,Imß},temporal constraints that reflect the order of the convex polygons along the path AJÅP) are imposed:gg before Ik,k E{2...m+3}. (l) Second, temporal constraints that force the possible start andend times of tasks to adhere to the ordering decided by the sequencing solver are added. That is, for each pair of tasks (A4”1M}) E M' X M' that are subject to a sequencing constraintAL precedes Alj, the following temporal constraint is added among the intervals A4ÅT)= {Hj..., [i m+3 beføre 15' , <2) ljwnana Mj(T)= {11f',...,1¿+3}= lO 26 reflecting the fact that the de-leveling polygon of task ALoccurs before the first motion of task Ålj. Third, we impose minimum durations of the motions and activities of the machines:Duration[d,w) Ik,k E{l...m+3}. (3)For every motion polygon sk,k E{l,...,m}, an initial value for d is computed based on the maximum allowed velocity of machineR. Hence, the earliest time solution of the STP represents thefastest possible execution of all motions and activities in the plan, i.e., an “optimistic” estimate of the start and end times of all operations of all machines.
    During execution, further temporal constraints can be added toreflect contingencies such as machine maintenance, delays, andso on. The association of an interval per polygon allowspredication via temporal constraints how long every movementor activity will take. Solving the STP is polynomial in the number of intervals in the temporal problem, namely ZMfiM' I MKT) I ° Note that there are no temporal constraints among intervalspertaining to different machines, the motions and activities of different machines may be concurrent.
    Coordination sub-problem Since a plurality machines operate in the same environment, itis crucial to address collision/deadlock avoidance. As aconsequence of decisions made in all previous sub-problems,the common constraint network includes polygons, temporalintervals, and temporal constraints (eqs. (l) to (3)) among them. The STP solver computes start and end times for each 27 interval. This determines when machines will occupy motion andactivity polygons in the various tasks. If two polygonspertaining to different vehicles overlap, and theircorresponding temporal intervals intersect, then the twovehicles may collide. Coordination avoids this by imposingadditional constraints that eliminate temporal intersection where needed.
    Decision variables of the coordination sub-problem are pairsof polygons and intervals represented by quadruple (sÅ,sá,Ií,Iá),of tasks i and j respectively, that overlap both spatiallyand temporaiiy, i.e., s; n sj, i ø A I; n 1,1, iøAMíuiniMjuz).The value of a decision variable is one of two possibleconstraints {Ií before Iá,Iá before Ií}, imposing either ofwhich eliminates the temporal overlap between concurrentpolygons. The STP solver will validate the sequencing in timeof these two overlapping polygons accordingly. It will alsocompute the consequent shift in the occurrence of any otherpolygon whose interval is constrained with lá or Ii by means of temporal constraint propagation within the common constraint network.
    The polygons involved in the decision variables represent twotypes of occupancy. The first type corresponds to the motionsof machines as described above. The second corresponds to thepiles created by drilling. By modeling both types of polygonsin the common constraint network, collisions among machinesand with piles are found and thus scheduled. This isexemplified in fig. 7, where there machines 701, 702, 703 eachdrills two rows of holes 704-705, 706-707, and 708-709,respectively. As can be seen from fig. 7, motions of machine 701 partly occupy rows 706 and 707 for maneuvering between 28 rows 704 and 705. This results in machine 702 having to waitjust before the conflicting area, until machine 701 finishesits maneuver. According to the disclosed example, machine 702will occupy some part of rows 708, 709, and hence machine 703will have to wait until machines 701, 702 are finishedswitching rows. The motion planner can ensure that the motionsof machine 702 do not conflict with rows 704 and 705 and hencedo not disturb already drilled holes of these rows2 is handledby the motion planner. This also applies for machine 703 androws 706, 707. As machines start their execution concurrently,their motions would lead to collisions, were it not for thefact that the coordination sub-problem was solved as well. Thetemporal constraints can force machines 702 and 703 to yield when necessary.
    Backtracking search The collection of decision variables for each sub-problemmentioned above constitutes the high-level CSP (henceforthcalled meta-CSP). Search in the meta-CSP consists in findingan assignment of values to decision variables that representhigh-level requirements. Each of these requirements is, inthis case, a sub-problem. Possible values among which theseassignments are selected are verified by a specific solver foreach sub-problem. Thanks to the common representation of thesearch space, each sub-problem solver accounts for theassignments made for decision variables of other sub-problems.For example, the path planner validates with respect to a mapcontaining obstacles resulting from sequencing decisions; andthe coordinator's decisions depend on the machine allocation as well as motion plans.
    The choices of values for decision variables in the various sub-problems contribute parts of the tasks in the common lO 29 representation, and the sub-problem solvers propagate theconsequence of these decisions. The sub-problem solvers used in the present approach are denoted in the following with solve-p, where p E {seq,alloc,time,coord,mp}.
    As has been explained, solve-seq disallows sequencingdecisions that are not totally ordered; solve-mp verifies bymeans of a motion planner that motions are kinematicallyfeasible and obstacle-free; solve-alloc accepts all candidateallocations, as the infeasible ones are discovered indirectlyvia coordination; solve-time is a STP solver which computesfeasible start/end times of task intervals subject to temporalconstraints; solve-coord is also provided by the same STPsolver, which validates and computes the consequences of temporal ordering decisions.
    A CSP-style heuristically guided backtracking search can beused to find values to assign to the decision variables. As iswell known, backtracking algorithms are frequently used insolving CSP problems. Henceforth, let the set of sub-problemsbe indicated by ¥n v i) .fïfincï.ïrš.is'n -s (ä: s: ”iafamzifi E. i~ få .ixë-figfl, fsïÉÉrR-a; :fisxigeg aiuï=eïfr<:š, trim) Iškšm3 oseiåwflmfiåxgfims@mmnifiw§Ä%fl$}4 'Ãïïåw E .åä fäåïïhmiv 3 1iii ~ (Å i:11% {_.-ï-"ÉÄ. 'vä12. >É«~°,._¿ ff __ 13 retnnx fïåzášzefz 14 füfiifn .ïzæffgtïiyï Given the set of tasks M, Algorithm DP3-solver collects allthe decision variables belonging to all the sub-problems (line1), and terminates when no decision variables are left (lines2 and 14). A particular sub-problem is then chosen according(line 3), e.g., h to a sub-problem ranking heuristic h pmb pmbprioritizes machine allocation decision variables overcoordination decision variables, as the latter problemrequires machines to be assigned to tasks (see above). Among the decision variables of a sub-problem, one is chosenaccording to a variable ordering heuristic hff (line 4). Forexample, which target should be selected first among thedecision variables l%w of the motion planning sub-problem.Among possible alternative values, one is chosen according tovalue ordering heuristic hfl (lines 5- 7). For instance, which approach angle has to be selected for a given target in themotion planning sub-problem. This value is added to the commonrepresentation (line 8). The sub-problem solver solve-p verifies that the assignment v is feasible. If so, DP3-solver 31 is called recursively (line 10), which results in selectinganother unassigned variable subject to the newly updatedcommon representation M. Note that if all possible values areattempted for a decision variable d and all are rejected bysolve-p, the algorithm returns failure (lines 6,11-13). Theproblem-, variable- and value-ordering heuristics used in the DP3-solver are explained in the following.Heuristics The DP3-solver must select a set of decision variablespertaining to a sub-problem from the union of all decision variables. This selection can be guided by a heuristic h to prob improve computational efficiency. Let Di < lä indicate that the decision variables of problem i have a higher priority than those of problem j. The partial ordering based on which the h heuristic operates is{[kw < ZLMC < Ia << D Z) < Zäm prob coord f mp < Ia << Dwmd}. Decision variables to branch on (within achosen Zl) are ordered based on hw, and alternative values are chosen according to hwl. Variable ordering heuristics are provided for the sequencing sub-problem and for thecoordination sub-problem. The latter heuristic is based ontemporal flexibility and has been used in the prior art forresource-constrained project scheduling. The former is basedon an analysis of the drill target placements, and is described below.
    Variable Ordering for Sequencing hg.
    The pattern of drill targets is analyzed to reveal itstopology and the possible principal directions of drill target sequencing. For other kinds of mining tasks to be performed, lO 32 similar analysis can be performed. To determine the former, adistance threshold is used; the latter are discovered via a K-Means which is a heuristic algorithm used to cluster the setof angular coefficients of topologically neighboring drilltargets. This yields clusters containing similarly orientededges of the topology. These are used to group drill targetsinto roughly-parallel lines. The topology and the groupingsare used to rank drill targets in groups. Variable in these groups are first in the sequencing sub-problems.
    Value ordering heuristics are defined for the sequencing,allocation, motion planning, and coordination sub-problems. Asfor variable ordering, the decision variables in thecoordination sub-problem are branched upon using a heuristic based on temporal flexibility that is widely used in the scheduling literature. The remaining heuristics hm] hm; are seq f explained below.
    Value Ordering for Sequencing hg.
    A value for a decision variable of the sequencing sub-problemdecides which drill target precedes a given target. There aremany alternatives for this choice. Note that sequencingdecision variables that are resolved first are thosepertaining to drill targets along groups - for such decisionvariables, the heuristic prioritizes one of two possiblepredecessors, namely those adjacent to the current decision variable in the grouping.
    For example, the two values with highest heuristic score fordecision variable MM0 in Figure 4A are MM1 precedes MM0 and Ml39 precedes MM0. lO 33 Also, this heuristic contributes to alleviating thecomputational burden of finding sequences in regions close tothe geofence while transitioning between groups. Finding afeasible sequence in these situations is challenging because amachine has limited space to maneuver. These regions ofhighly-constrained motion span typically eight targets forevery pair of adjacent groups, thus in the worst casesequencing requires verifying, through motion planning, 87possible motions for each pair. For this reason, the heuristicmay use given sequence patterns that reflect common practiceby human operators. A sequence pattern is a topologicaldescription of a human driving behavior, augmented with metricinformation that facilitates assessing whether the pattern isapplicable in a given region. Specifically, a sequence patternis a graph (V,E) where V is a set of nodes representing drilltargets, and E is a sequence of precedence constraints amongthe nodes. A distance threshold d¶wænæ is also given, andrepresents the minimum distance to the geofence required forthe pattern to hold. Also, a ranking < of the nodes in termsof how far they lie from the geofence may be provided. Anexample pattern that can be used by the solver is shown in Figure 6. If the search is considering a decision variable AL that is surrounded by targets that can be mapped to the nodes in the pattern, then the heuristic ranks possible predecessorsof AL according to the edges in E. Suitable patterns can be defined and used by the solver to improve computational efficiency.
    Value Ordering for Motion Planning h߁ This heuristic may e.g. suggest approach angles for a targetthat is similar to those assigned to other drill targets in a same group. lO 34 Value Ordering for Machine Allocation hސ. A solution to the machine allocation sub-problem determines which drill targetis drilled by which machine. Among all possible choices, thosemay be preferred which have three properties: (l) each machineis assigned to a contiguous sequence; (2) start and end tasksof a contiguous sequences are the drill targets close to anopen area, i.e., not close to a geofence and not those thatare entirely surrounded by other drill targets; and (3)targets are evenly distributed among machines or according tomachine capacity when machines of different capacity are used.This heuristic not only contributes to the plan quality interms of similarity to what a human planner would decide, butalso improves the efficiency in planning time by suggesting a restriction on start and exit points for each machine.
    The use of heuristics e.g. according to the above maysubstantially improve computational efficiency when seeking asolution to the problem of assigning the tasks to the machines.
    Adapting solutions during operation Several aspects of the overall problem of assigning tasksbecome known only online. Therefore it may be necessary tocompute at least parts of the solution to the overall problemduring execution, i.e. during drilling according the present example, and/or to adapt existing plans to contingencies.
    For example, the actual durations of activities only becomeapparent during execution. In a bench, various types ofcontingencies may occur, such as unexpected maintenance ofmachines, or increased drilling time due to unknown geologicalcharacteristics of the terrain. Therefore, it may be required to monitor the execution of the tasks and reflect the lO contingencies in the common representation. According to thepresent example, the nominal behavior of the machines is given by a solution of the DP3, obtained via Algorithm above.
    The start and end times associated to the intervals Alflflof every task A1 are computed through temporal propagation. Allthe lower bounds represent the earliest possible times atwhich tasks can be executed, and are used to compute thedesired speeds at which the computed paths should be driven bythe vehicle executives. The control unit 206 controls the themachine to follow the given trajectories. It also reportscurrent progress of the machine. Deviations are used asconstraints by the STP solver to propagate any mismatchbetween prescribed and executed tasks of all machines beingused. The STP solver plays a central role in executionmonitoring. The common representation of the tasks can beupdated e.g. at a frequency of lHz to continuously account fordeviations. A task in ended by adding a temporal constraintinto the common constraint network representing the finishtime of the task as the executive layer informs. Theconsequences of such updates can be easily computed within theperiod of one second because the STP solver performspolynomial inference. Also, due to the fact that addingconstraints cannot “undo” other decisions, unforeseendurations (e.g., encountering hard rock while drilling) can be accounted for at execution time.
    More precisely, the prolongation of an activity represented bya flexible time interval associated to a motion polygon willnot affect the sequencing, the approach angle, the particularmotions, nor machine allocations. It only bears consequenceson the coordination sub-problem, as delays may need to be propagated to other waiting machines. lO 36 According to one embodiment, e.g. if it is crucial to minimizethe Time To Completion TTC, prolongation of an activity may beallowed lead to the re-allocation of the machines, which in turn would result in updating the decisions in the sequencingsub-problems. This allows for re-balancing the workload among the machines.
    The feedback of progress data may also be utilized when onlyone machine is operating, also when the machine is manuallyoperated, since this still will facilitate planning of furtherwork in the mine. Also, rearrangement of tasks may be requiredalso in this case, e.g. if another machine is taken into operation.
    On-line temporal reasoning also caters to another importantrequirement of mining companies, namely the need to know anestimate of the Total Time to Completion (TTC) in order toplan following events and/or resource usage. At planning time,an optimistic TTC can be calculated by initializing theduration constraints with reasonable values: the durations ofintervals corresponding to motion polygons are computed usingthe maximum allowed speed of machines; and the intervalscorresponding to activity polygons are initialized withdurations under nominal conditions (average rock density, andno maintenance). As execution proceeds, TTC is updated as a result of temporal reasoning to reflect the actual situation, which facilitates planning of other activities in the mine.
    The time of completion, i.e. the point of time at which thetasks are expected to be carried out can be displayed andupdated e.g. to an operator. Alternatively or in addition, atime to completion can be displayed, i.e. the time remaining to complete the tasks. lO 37 According to the invention, the overall problem is dividedinto a plurality of sub-problems and the mutually feasible solutions to the individual sub-problems are found.
    The DP3-solver combines solutions from different sub-problems,each of which can be seen as a “classical” robotics problem. Agiven hybrid problem is broken down and interdependenciesamong sub-problems are identified. A heuristically guidedbacktracking search can be used to find a solution to theoverall problem in the joint search spaces of the sub- problems.
    Furthermore, a plurality of solutions to the overall problemof assigning tasks and/or one or more sub-problems can befound. In such situations a solution can be selected on thebasis of a cost function, where the cost function can take anysuitable parameter into account. For example, the costfunction can constitute minimization of a time to completion of said set of tasks.
    The invention has so far been described in connection to asurface mine. The invention, however, is suitable for anymining application where a plurality of movable machines canbe employed to autonomously perform tasks, such as e.g.collection of ore from one location to another, e.g. in underground mines.
    Consequently, the invention is not limited other than in regard of what is stated in the appended claims.
    权利要求:
    Claims (31)
    [1] 1. Method for assigning a set of tasks to at least one miningand/or construction machines (2OOA, 2OOB;70l-703), saidmachine (2OOA, 2OOB;70l-703) being arranged to be drivenbetween positions for performing tasks, characterized in thatthe method includes: - defining a first set of constraints to be fulfilled whenassigning said tasks to said at least one mining and/orconstruction machine (2OOA, 2OOB;70l-703); - finding a solution fulfilling said first set of constraintsby solving each constraint as a sub-problem, the solution toat least one sub-problem being dependent on the solution of atleast one other sub-problem; - said solution fulfilling said first set of constraints beinga solution where a first of said sub-problems is validated bysolutions of others of said sub-problems, and - assigning tasks to said at least one machine (2OOA, 2OOB;70l-703) according to the determined validated solution.
    [2] 2. Method according to claim l, further including:- assigning said set of tasks to a plurality of mining and/or construction machines (2OOA, 2OOB;70l-703).
    [3] 3. Method according to claim 2, wherein tasks of said set oftasks are arranged to be carried out at least partiallyoverlapping in time by a plurality of mining and/or construction machines (2OOA, 2OOB;70l-703).
    [4] 4. Method according to any one of claims l-3, furtherincluding:- validating a solution to said first sub-problem by determining that said solution to said first sub-problem lO 39 allows a solution of other sub-problems being dependent on the solution to said first sub-problem.
    [5] 5. Method according to any one of claims l-4, furtherincluding: - utilizing a common representation of said sub-problems,where said tasks are represented by variables, so that solveralgorithms of the sub-problems, respectively, share a common search space when searching a solution to a sub-problem.
    [6] 6. Method according to any one of claims l-5, furtherincluding: - assigning priorities to said sub-problems, and determining asolution to the assigning of said tasks by validating asolution to a higher prioritized sub-problem by solutions to lower prioritized solutions.
    [7] 7. Method according to any one of the preceding claims, whereina solution to said first sub-problem is discarded whensolutions to other sub-problems validating the first sub- problem cannot be found.
    [8] 8. Method according to any one of the preceding claims,further including: - discarding solutions to said first sub-problem when saidsolutions to said first sub-problem is not validated bysolution to all sub-problems being dependent on the solution to the first sub-problem.
    [9] 9. Method according to any one of the preceding claims, whereinsolving of at least one of said sub-problems require analready present solution of at least one other of said sub- problems. lO
    [10] 10. Method according to any one of the preceding claims,further including: - solving said problem of assigning said tasks using arepresentation of the tasks to be carried out by means of saidat least one machine, and a representation of said at least one machine.
    [11] 11. Method according to any one of the preceding claims,wherein said tasks are arranged to be carried out within a confined geographical area.
    [12] 12. Method according to claim ll, said at least onemachine being allowed to move within overlapping portions of said geographical area.
    [13] 13. Method according to any one of the preceding claims,further including: - assigning a first subset of said set of tasks to a firstmachine, and a second subset of tasks of said set of tasks to a second machine.
    [14] 14. Method according to any one of the preceding claims,wherein, when a first subset of said set of tasks has beenassigned to a first machine and a task of said subset has beencompleted by said machine: - the carrying out of a following task of said subset of tasksby said first machine requires autonomous movement of saidfirst machine from a first location to a second location in said geographical area.
    [15] 15. Method according to any one of the preceding claims,wherein:- one of said sub-problems consists of determining a sequence of execution of said tasks to be assigned to said at least one 41 machine such that each of said tasks is sequenced with respect to the others of said tasks.
    [16] 16. Method according to claim 15, said sub-problem ofdetermining an order of execution of said tasks being said first sub-problem to be solved among said sub-problems.
    [17] 17. Method according to any one of the preceding claims,further including: - determining a start time and an end time for performing eachof said tasks, start time and end time of a task being definedin relation to start times and end times of the others of saidtasks, and said assignment of said tasks including a start time and end time for performing said tasks, respectively.
    [18] 18. Method according to claim 17, further including: - receiving progress data regarding progress of fulfillment ofsaid tasks from said at least one machine, and recalculatingsaid start times and end times for tasks remaining to be carried out on the basis of received progress data.
    [19] 19. Method according to any one of the preceding claims,:- one of said sub-problems being a coordination sub-problemscheduling machines such that when said machines are operatingin overlapping portions of said geographical area, times forperforming said tasks are assigned such that said machines will not collide.
    [20] 20. Method according to any one of said claims, furtherincluding: - determining an estimated time of completion and/or time tocompletion of said tasks, and displaying said estimated time of completion and/or time to completion. 42
    [21] 21. Method according to claim 18, further including: - updating said estimated time of completion and/or time tocompletion of said tasks on the basis of progress datareceived from said at least one machine when carrying out said tasks.
    [22] 22. Method according to any one of the preceding claims,further including, when performing said tasks, said at leastone machine communicating progress regarding fulfillment ofsaid tasks, and - re-solving the assignment of tasks to said at least onemachine when data from said at least one machine indicate a requirement of re-assignment of said tasks.
    [23] 23. Method according to any one of the preceding claims,further including, when solving said problem of assigningtasks to said at least one machine: - determine the assigning of said tasks such that, when saidmachine has finished assigned tasks, a defined end positioncan be reached by a machine without violating allowedmovements within the area in which said tasks are being carried out.
    [24] 24. Method according to any one of the preceding claims,wherein each of said sub-problems are solved by means of a sub-problem specific solver.
    [25] 25. Method according to any one of the preceding claims,further including:- assigning tasks to said at least one machine only if a solution to said first sub-problem is validated.
    [26] 26. Method according to any of the preceding claims,further including, when tasks have been assigned to a machine: - communicating said tasks to said machine. lO 43
    [27] 27. Method according to any of the preceding claims,further including, when a plurality of solutions to theassignment of tasks and/or a sub-problem is found, selecting solution on the basis of a cost function.
    [28] 28. Methods according to claim 27, where the cost function is a time to completion of said set of tasks.
    [29] 29. Method according to any one of the preceding claims,further including:- by means of said at least one machine, carrying out said tasks assigned to said at least one machine.
    [30] 30. System for assigning a set of tasks to at least onemining and/or construction machine (2OOA, 2OOB;70l-703), saidmachine (2OOA, 2OOB;70l-703) being arranged to be drivenbetween positions for performing tasks, characterized in thatthe system includes: - receiving means for receiving a first set of constraints tobe fulfilled when assigning said tasks to said at least onemining and/or construction machine (2OOA, 2OOB;70l-703); - solving means for finding a solution fulfilling said firstset of constraints by solving each constraint as a sub-problem, the solution to at least one sub-problem beingdependent on the solution of at least one other sub-problem,said solution fulfilling said first set of constraints being asolution where a first of said sub-problems is validated bysolutions of the others of said sub-problems, and - means for assigning tasks to said at least one machine(2OOA, 2OOB;70l-703) according to the determined validatedsolution.
    [31] 31. Mining- and/or construction machine (2OOA, 2OOB;70l-703),characterized in that it comprises a system according to claim 30.
    类似技术:
    公开号 | 公开日 | 专利标题
    SE1551256A1|2017-04-02|Method and system for assigning tasks to mining and/or construction machines
    AU2010237608B2|2015-06-25|Drill hole planning
    Sariel et al.2008|Naval mine countermeasure missions
    EP2531014B1|2018-12-26|In use adaptation of schedule for multi-vehicle ground processing operations
    US9404239B2|2016-08-02|Sub-bin refinement for autonomous machines
    US9506224B2|2016-11-29|Grade control cleanup pass using splines
    US9598843B2|2017-03-21|Real-time route terrain validity checker
    Alatartsev et al.2013|On optimizing a sequence of robotic tasks
    Mansouri et al.2016|HYBRID REASONING FOR MULTIROBOT DRILL PLANNING IN OPENPIT MINES
    Lipovetzky et al.2014|Planning for mining operations with time and resource constraints
    AU2015397104B2|2021-08-05|Adaptation of mining operations satellite coverage
    Schulze et al.2017|Staff and machine shift scheduling in a German potash mine
    SE1551257A1|2017-04-02|Method and system for assigning tasks to drill rigs
    CN102459811B|2015-07-15|Teaching model for automatic control of mobile mining machine
    AU2017239532A1|2018-05-10|Operating methods and systems for underground mining
    Åstrand et al.2021|Short-Term Scheduling of Production Fleets in Underground Mines Using CP-Based LNS
    Mansouri et al.2017|Multi vehicle routing with nonholonomic constraints and dense dynamic obstacles
    MahmoudZadeh et al.2019|Augmented Reactive Mission Planning Architecture
    CAMUS2015|European Project NeTTUN–Making it happen
    Reddicharla et al.2017|A New Dimension to Field Development Well Planning Using Smart Integrated Workflow and Data Collaborative Environment for Improving Efficiency
    MahmoudZadeh et al.2019|Advancing autonomy by developing a mission planning architecture |
    Balderud et al.2007|Autonomous control of clusters of UUVS
    CN112539029A|2021-03-23|Apparatus, method and software product for drilling sequence planning
    同族专利:
    公开号 | 公开日
    CA2999429A1|2017-04-06|
    US11168564B2|2021-11-09|
    AU2016331159C1|2021-07-29|
    SE542284C2|2020-04-07|
    US20180266247A1|2018-09-20|
    FI20185283L|2018-03-27|
    WO2017058088A1|2017-04-06|
    ZA201802034B|2019-07-31|
    CL2018000799A1|2018-06-01|
    AU2016331159A1|2018-04-19|
    AU2016331159B2|2021-04-29|
    FI20185283A|2018-03-27|
    MX2018003751A|2018-06-18|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US4679489A|1985-11-04|1987-07-14|Becor Western Inc.|Automatic leveling system for blast hole drills and the like|
    JP4082831B2|1999-10-26|2008-04-30|株式会社小松製作所|Vehicle control device|
    US7548873B2|2004-03-17|2009-06-16|Schlumberger Technology Corporation|Method system and program storage device for automatically calculating and displaying time and cost data in a well planning system using a Monte Carlo simulation software|
    AT504872T|2005-07-26|2011-04-15|Macdonald Dettwiler & Associates Inc|GUIDANCE, NAVIGATION AND CONTROL SYSTEM FOR A VEHICLE|
    FI120191B|2005-10-03|2009-07-31|Sandvik Tamrock Oy|Procedure for driving mining vehicles in a mine and transport system|
    US20070271002A1|2006-05-22|2007-11-22|Hoskinson Reed L|Systems and methods for the autonomous control, automated guidance, and global coordination of moving process machinery|
    US8364189B2|2009-02-24|2013-01-29|Caterpillar Inc.|Fleet communication network|
    AU2010237608B2|2009-04-17|2015-06-25|The University Of Sydney|Drill hole planning|
    CA2760724C|2009-05-01|2017-01-24|The University Of Sydney|Control system for autonomous operation|
    US20100287073A1|2009-05-05|2010-11-11|Exxonmobil Research And Engineering Company|Method for optimizing a transportation scheme|
    US8612084B2|2009-09-15|2013-12-17|The University Of Sydney|System and method for autonomous navigation of a tracked or skid-steer vehicle|
    US8261855B2|2009-11-11|2012-09-11|Flanders Electric, Ltd.|Methods and systems for drilling boreholes|
    ZA201008618B|2009-12-02|2011-08-31|Tech Resources Pty Ltd|A system and method for the autonomous drilling of ground holes|
    US8733473B2|2010-11-02|2014-05-27|Caterpillar Inc.|Sequencing algorithm for planned drill holes|
    CN103608740B|2011-04-11|2017-06-30|克朗设备公司|The method and apparatus that multiple automatic incomplete vehicles are effectively dispatched using coordinated path planner|
    EP2788933A4|2011-12-22|2015-06-03|Ibm|Mixing optimal solutions|
    CA2902236A1|2013-02-27|2014-09-04|Technological Resources Pty Ltd|A method of generating a drill hole sequence plan and drill hole sequence planning equipment|US11162241B2|2018-03-27|2021-11-02|Deere & Company|Controlling mobile machines with a robotic attachment|
    EP3605399A1|2018-07-31|2020-02-05|Tata Consultancy Services Limited|Systems and methods for semantic knowledge based dynamic utility calculation|
    US20200117201A1|2018-10-15|2020-04-16|Caterpillar Paving Products Inc.|Methods for defining work area of autonomous construction vehicle|
    WO2021041723A1|2019-08-27|2021-03-04|Schlumberger Technology Corporation|Drilling rig task management|
    法律状态:
    优先权:
    申请号 | 申请日 | 专利标题
    SE1551256A|SE542284C2|2015-10-01|2015-10-01|Method and system for assigning tasks to mining and/or construction machines|SE1551256A| SE542284C2|2015-10-01|2015-10-01|Method and system for assigning tasks to mining and/or construction machines|
    US15/764,759| US11168564B2|2015-10-01|2016-09-29|Method and system for assigning tasks to mining and/or construction machines|
    CA2999429A| CA2999429A1|2015-10-01|2016-09-29|Method and system for assigning tasks to mining and/or construction machines|
    AU2016331159A| AU2016331159C1|2015-10-01|2016-09-29|Method and system for assigning tasks to mining and/or construction machines|
    PCT/SE2016/050923| WO2017058088A1|2015-10-01|2016-09-29|Method and system for assigning tasks to mining and/or construction machines|
    MX2018003751A| MX2018003751A|2015-10-01|2016-09-29|Method and system for assigning tasks to mining and/or construction machines.|
    ZA2018/02034A| ZA201802034B|2015-10-01|2018-03-27|Method and system for assigning tasks to mining and/or construction machines|
    FI20185283A| FI20185283L|2015-10-01|2018-03-27|Method and system for assigning tasks to mining and/or construction machines|
    CL2018000799A| CL2018000799A1|2015-10-01|2018-03-28|Method and system for assigning tasks to mining and / or construction equipment|
    [返回顶部]