[WIP] [Plugin] KerbCom Avionics - Analytical engine and RCS thrust balancing

[ZRM]

The release thread is here.

Edit: This mod is now an engine thrust balancer for VTOLs and unbalanced lifters, as well as an RCS thrust balancer. See the latest posts for details.

Everyone knows what a pain it can be to try to maneuver a large craft or station with RCS, as RCS thrusters by default operate using a simple model that does not account for the distribution of thruster ports around the centre of mass. You try to translate, and it rotates whether you like it or not, and vice versa. Thus I am going to try to develop a module that automatically solves this problem with no user input required whatsoever, for arbitrary port layouts.

The general problem, as far as I can see, is how to calculate the combination of thrust values (per thruster port) that produce the desired resultant angular and linear acceleration. You need to solve a linear system of equations and inequalities. The main equation is that of the directional and angular thrust produced by a combination of thrust values, and the inequalities describe the maximum thrust limits of the individual ports. You also ideally want to minimise the fuel expenditure. Mathematically, all of this is a convex¹ optimisation² problem, easily solvable³ using existing numerical methods libraries.

Please note that this is my first foray into modding KSP, so bear with me if progress is slow. I have learnt from other threads that this add-on should be possible, as modules can control the exact thrust of individual ports.

I would also be grateful for any tips regarding the implementation of such a plugin (such as which callbacks to use), though I think I have a grasp of the essentials.

[1] due to the inequalities

[2] due to the minimisation of fuel use and maximisation of movement in desired direction

[3] in theory

Edited July 5, 2013 by ZRM
Added link to release thread.

[EndlessWaves]

Nice to see someone with a bit of mathematical background tackle it, unfortunately mine only goes far enough that I can point out the flaws in simple approaches without having enough experience to suitably frame the problem for solving.

I'm interested you think the problem has no local minimums², that seems far from obvious intuitively. Is not the necessity of needing to counter forces on two others axes possibly going to create local minimums if you're aiming to minimise fuel use as well as maximise thrust?

²which is apparently the definition of convex in this context.

Anyway, uninformed speculation aside I probably can help on the coding side, here's the code I wrote for an RCS Balancer using a much simpler (and not entirely effective algorithm). It should give you some idea of the various commands you'll need to use. It was only a tech demo though, so I didn't bother to remember the original thrust and set it to 1 instead, which is probably something you do want to do for a release version.

You can't actually set thrust per port on the stock 4 port RCS thruster, you can only set it per part. It'll still work on the linear thrusters of course, and a custom RCS module that allowed per port control could be created.

using System;
using System.Collections.Generic;
using UnityEngine;

public class SimpleRCSBalancer : PartModule
{
	private List<ModuleRCS> RCSModules = new List<ModuleRCS>();
	private bool balanceEnabled = true;

	public override void OnActive()
	{
		if(HighLogic.LoadedSceneIsFlight && this.vessel.isActiveVessel)
		{
			foreach(Part aPart in vessel.Parts)
			{
				foreach(PartModule potentialRCSModule in aPart.Modules)
				{
					if(potentialRCSModule is ModuleRCS)
						RCSModules.Add((ModuleRCS)potentialRCSModule);
				}
			}
		}
	}

	public override void OnFixedUpdate()
	{		
		if(HighLogic.LoadedSceneIsFlight && this.vessel.isActiveVessel && balanceEnabled)
		{
			Vector3 directionOfTravel = Vector3.zero;
			Vector3 directionOfBalance = Vector3.zero;
			if(Mathf.Approximately(FlightInputHandler.state.X, 0) == false)
			{
				directionOfTravel = (Vector3.right * FlightInputHandler.state.X).normalized;
				directionOfBalance = Vector3.forward;
			}
			else if(Mathf.Approximately(FlightInputHandler.state.Y, 0) == false)
			{
				directionOfTravel = (Vector3.forward * FlightInputHandler.state.Y).normalized;
				directionOfBalance = Vector3.up;
			}
			else if(Mathf.Approximately(FlightInputHandler.state.Z, 0) == false)
			{
				directionOfTravel = (Vector3.up * FlightInputHandler.state.Z).normalized;
				directionOfBalance = Vector3.forward;
			}
			else
				return;

			float positiveAxisTorque = 0;
			float negativeAxisTorque = 0;

			foreach(ModuleRCS anRCS in RCSModules)
			{
				foreach(Transform aNozzle in anRCS.thrusterTransforms)
				{
					Vector3 nozzlePosition = vessel.transform.InverseTransformPoint(aNozzle.position) - vessel.findLocalCenterOfMass();
					if(Vector3.Angle(aNozzle.transform.forward, directionOfTravel) <= 90)
					{
						float straightLineDistance = Vector3.Project(nozzlePosition, directionOfBalance).magnitude;
						if(straightLineDistance >= 0)
							positiveAxisTorque += straightLineDistance * anRCS.thrusterPower;
						else
							negativeAxisTorque += -straightLineDistance * anRCS.thrusterPower;
					}
				}
			}

			if(positiveAxisTorque > negativeAxisTorque)
			{
				float ratio = negativeAxisTorque / positiveAxisTorque;
				foreach(ModuleRCS anRCS in RCSModules)
				{
					foreach(Transform aNozzle in anRCS.thrusterTransforms)
					{
						Vector3 nozzlePosition = vessel.transform.InverseTransformPoint(aNozzle.position) - vessel.findLocalCenterOfMass();
						float straightLineDistance = Vector3.Project(nozzlePosition, directionOfBalance).magnitude;
						if(straightLineDistance >= 0)
							anRCS.thrusterPower = 1 * ratio;
					}
				}
			}
			if(negativeAxisTorque > positiveAxisTorque)
			{
				float ratio = positiveAxisTorque / negativeAxisTorque;
				foreach(ModuleRCS anRCS in RCSModules)
				{
					foreach(Transform aNozzle in anRCS.thrusterTransforms)
					{
						Vector3 nozzlePosition = vessel.transform.InverseTransformPoint(aNozzle.position) - vessel.findLocalCenterOfMass();
						float straightLineDistance = Vector3.Project(nozzlePosition, directionOfBalance).magnitude;
						if(straightLineDistance <= 0)
							anRCS.thrusterPower = 1 * ratio;
					}
				}
			}
		}
	}
	[KSPAction("Toggle", KSPActionGroup.Custom07)]
	public void toggle(KSPActionParam param)
	{
		balanceEnabled = !balanceEnabled;
		foreach(ModuleRCS anRCS in RCSModules)
		{
			anRCS.thrusterPower = 1;
		}
	}
}

[ZRM]

Thanks for the support. Don't overestimate my mathematical background - I have now realised that I incorrectly used the term convex - I intended it to mean that the space of solutions is bounded by a convex region (specifically an n-dimensional hypercube, where n is the number of ports). However I have hope that the problem does not have local minimums, as (I think) the linear and angular acceleration are linear functions of each of the thrust vectors, but we will see. I am hoping to try solving this problem with a variety of optimisation algorithms¹. If it does turn out to be non-convex (using the correct meaning) I can try to guesstimate the the appropriate starting values for the optimiser using some kind of heuristic.

Regarding the implementation, I had already made a copy of the code you provide from another thread you posted it in. I now realise that unfortunately the thrust is per part, not port. Do you have any insight on the potential usage of the other public variables of ModuleRCS, such as thrustForces? How about how to implement a custom RCS thruster module? If all else fails, I can try constraining the optimisation problem so that it takes into account the lack of control over individual ports.

Edit:

I now see that the desired result should be possible by setting isJustForShow to true on all thrusters, then applying forces manually. Resource will be drained as if the thrusters were operating normally.

[1] Solving the underdetermined system given by just the port transforms for a desired force should give a surface (an n-d plane) of all valid thrust combinations, which can then be clipped to the hypercube of physically possible port thrusts and optimised for fuel usage.

Edited May 8, 2013 by ZRM

[ZRM]

I have now implemented an extended version of ModuleRCS called ModuleARCS¹, which behaves identically to ModuleRCS in every way, except that if you set isExternallyControlled to true on it, it will instead take the thrust values for each port from a public list thrustExternalInputs. "Externally controlled" also shows up as a GUI field in game. It is not a subclass of ModuleRCS, which makes it incompatible with other mods working with ModuleRCS (I may change this).

My RCS balancing module is called ModuleRCSComputer, and is designed to be attached to one part of a vessel. I have the foundation of one solving method implemented (not yet tested), using BLEIC (Bound and Linear Equality/Inequality Constrained) optimisation. This method simply relies on a list of linear constraints and a minimisation function, so no complex matrix decompositions are required. I now need to calculate the total inertia tensor matrix for the entire vessel manually, as I have learnt that findLocalMOI is inaccurate (it is no longer used in MechJeb for this reason) since it just adds up the moments of inertia of point masses representing each part.

I also need some way of determining the ideal scaling factor for the inputs - i.e. the responsiveness of the system. If I set this too high, the target acceleration may be out of range of the capability of the thrusters. If I set it too low the system may be sluggish despite the thrusters being more than capable of adequate thrust. Does anyone else have any thoughts about this? I am currently leaning towards providing a GUI panel that lets the user set their desired linear and angular responsiveness, with a notification if their selected values are impossible. This is an improvement over the vanilla interface that does not allow adjustment of responsiveness.

'A' for Advanced. What else?

[EndlessWaves]

So you've got:

Translation X < 0.001

Translation Y < 0.001

Translation Z > N

And you need a sensible value for N?

I presume your choice of algorithm doesn't support any sort of weighting in this case so it needs to be lower than achievable or the translations on the other axes will quickly build up?

Can you do it iteratively and solve several times for increasing values for N until you find a value that can't be solved? You don't need much interaction with the game so you could do the actual calculations on a secondary thread if they're computationally intensive and just use the main thread for grabbing values and setting thrusts.

[ZRM]

The solver works by providing it with the target acceleration vectors. So it's a case of equalities, not inequalities. So in your example (attempting linear Z axis acceleration), it's more like

X = 0

Y = 0

Z = N

is the target vector. If you set N too high it can't be solved and the solver reports failure. (I am not sure what you mean regarding weighting.)

I can determine the maximum value of N just by letting the magnitude of the vector be a free variable then optimising for magnitude, however this requires calculation of a completely different matrix of inputs for the solver. Don't forget that this maximum magnitude N depends on the direction of intended acceleration, so it would need to be determined in every update. I am not yet sure whether performance will be a problem. I could let it update concurrently if necessary, as you suggest, and fix its update rate to a multiple of the game update rate.

Anyway, finding the maximum value of N is not the the real problem. In some cases the maximum possible N may be very high, and if this is achieved the vessel would be too responsive to be controllable, and therefore not the ideal maximum input (for rotational acceleration, at least)¹. This is why I propose letting the user set maximum responsiveness manually for angular and linear acceleration². Also, since N is not constant (it depends, for example, on whether you are translating and rotating at the same time), using it as the scaling factor may be unintuitive and difficult for the user to predict.

[1] Ever tried landing a lightweight lander without SAS and too many RCS thrusters for its own good?

[2] The UI could allow configuration of different settings depending on the situation, e.g. docking or ascent, and the settings would persist with the vessel in KSPFields.

Edited May 10, 2013 by ZRM

[ZRM]

I have just learnt that MechJeb 2 already has an RCS balancing solver. I am still using MechJeb 1.x, so I have not noticed it before. It is even using the same numerical methods library and the same solving algorithm. However it does not use linear constraints to ensure a correct result - it relies on the optimiser for that. This means that it comes up with potentially invalid solutions, and it is probably slower due to the expanded search space. To counter this the solver is put in a separate thread and previous results of the solver are cached. Another drawback is that it only ensures that translation does not incur rotation, not vice versa, and you can't rotate while it is active (that last bit is speculation from looking at the source, and I have not installed MechJeb 2 yet to test this). It also relies on the inaccurate moment of inertia calculation that KSP provides. Possibly the most crucial deficiency is that it does not have control over individual ports - it only controls the overall thrust of a thruster block. Plus I don't think it provides responsiveness adjustment.

For these reasons, I am still developing my own plugin. I hope to include features such as setting a pivot point for rotations so that the RCS computer applies linear thrust with angular thrust to allow rotating about a docking port, or orbiting another vessel. I also want to extend it to include main engine thrust balancing for asymmetrical launch vehicles (think space shuttle) and VTOL craft with movable engines (think Prometheus).

Edited May 11, 2013 by ZRM

[ZRM]

Progress update: The core of the plugin is working perfectly now. I have complete control over every individual port, which is enabled by replacing instances of ModuleRCS with ModuleARCS automatically when a vessel loads or docks¹. The vessel is also correctly controlled by the results of the solver, which has negligible performance impact in my test cases. The only things missing before I publicly release a first version of this plugin are a GUI for selecting responsiveness, accurate inertia tensor calculation to replace the inaccurate value provided by the KSP API and ensuring that the plugin behaves properly in edge cases (such as when connected to launch supports and when only some RCS ports run out of fuel or break).

To speed things along I would be grateful for descriptions of the exact cases in which each callback (i.e. OnStart, OnAwake, OnActive) is called, and tips for implementing the GUI.

[1] Thus assimilating (or "infecting") all RCS modules that the vessel comes into contact with.

[ZRM]

I now have the plugin working well enough for a pre-release (IMO). The inertia tensor calculations will require more rigorous testing before I can be sure that they are correct, so the values provided by the KSP API are used in the interim.

[ZRM]

Uh, mods, I have just realised that this thread should be in plugin development. Please could you move it?

[pantheis]

This sounds amazing! Any chance you could get with the Mechjeb folks and get this integrated in place of their RCS balancer? And maybe help them with some of the control issues 2.x has with always attempting to maintain a specific roll level? It will roll you to a specific value before pitching when trying to do things such as point from prograde to Orbit+ when it should just pitch, no roll needed.

[Conarr]

And do you have a location yet on where the pre-release can be downloaded?

[ZRM]

Here is the link to the release thread

http://forum.kerbalspaceprogram.com/showthread.php/29387-0-19-1-KerbCom-Avionics-Coordinated-RCS

[ZRM]

This sounds amazing! Any chance you could get with the Mechjeb folks and get this integrated in place of their RCS balancer? And maybe help them with some of the control issues 2.x has with always attempting to maintain a specific roll level? It will roll you to a specific value before pitching when trying to do things such as point from prograde to Orbit+ when it should just pitch, no roll needed.

The MechJeb RCS balancer actually uses a very similar solving algorithm to my approach. I just use it in a different way. I'm going to keep development separate for the time being, as it would take a while to get up to speed with the MechJeb code base, plus I have other things in mind than just RCS balancing, such as main engine balancing and VTOL balancing. I am also planning to later use an entirely different algorithm (a form of matrix decomposition) for the solving to improve robustness, performance and usability in one go.

[Conarr]

Thanks ZRM, I'll give it a go tonight

[pantheis]

The MechJeb RCS balancer actually uses a very similar solving algorithm to my approach. I just use it in a different way. I'm going to keep development separate for the time being, as it would take a while to get up to speed with the MechJeb code base, plus I have other things in mind than just RCS balancing, such as main engine balancing and VTOL balancing. I am also planning to later use an entirely different algorithm (a form of matrix decomposition) for the solving to improve robustness, performance and usability in one go.

That sounds great! On the engine/VTOL balancing, would your plugin be able to negotiate handling a set of active, thrusting engines rotating from vertical to horizontal? I would love something that could do automatic smooth take off/landing in VTOL mode. Even MechJeb just can't handle it, and it doesn't handle engines that rotate very well at all. Been rather annoying trying some interesting designs only to have it think forward needs to be up and tipping my craft all the way back.

[ZRM]

That sounds great! On the engine/VTOL balancing, would your plugin be able to negotiate handling a set of active, thrusting engines rotating from vertical to horizontal? I would love something that could do automatic smooth take off/landing in VTOL mode. Even MechJeb just can't handle it, and it doesn't handle engines that rotate very well at all. Been rather annoying trying some interesting designs only to have it think forward needs to be up and tipping my craft all the way back.

That is exactly the sort of thing I have in mind. Hopefully it will be just like in the film Prometheus (for example). See the release thread for my current goals for the plugin. There are other plugins that claim to handle VTOL control, but they are not precise enough or general enough for my liking.

Do you have any tips for making robust rotating engines? I tried damned robotics, but no matter how I tweaked the config file, I couldn't make the rotatron strong enough - it always flexes to the point that all of the engines are hanging down under the craft. I wouldn't mind some examples of good designs that I can use for testing purposes.

[Tallinu]

The B9 Aerospace pack has swiveling VTOL engines. I think they only have two positions, but they should do the trick if you need engines that change their direction of thrust instead of just building with different engines pointing different directions.

[ZRM]

The B9 Aerospace pack has swiveling VTOL engines. I think they only have two positions, but they should do the trick if you need engines that change their direction of thrust instead of just building with different engines pointing different directions.

I did look at the B9 VTOL engines, but like you say, they only have two settings - vertical or horizontal. This isn't very useful when you are trying to maintain altitude at low speed, for example. However it may be possible to use the models and animation from those engines to make a version with a continuous range of orientations.

[Hyratel]

this may need a recompile. my test cases with 0.20 were unable to come up with a solution for an Apollo-CSM type vehicle

[ZRM]

this may need a recompile. my test cases with 0.20 were unable to come up with a solution for an Apollo-CSM type vehicle

Thanks for the heads up. I am currently (literally right now) working on the next major version (1.0). It's a complete architectural redesign from the ground up, and shares no code with the original. It will hopefully also include most of the features I have alluded to in previous posts (on this and the other thread) and more. Once I get this to a testing phase, I will consider fixing the old version for 0.20.2, however it's unlikely as the original was really just a quickly prototyped proof-of-concept with no thought for code design, so it's pretty difficult to maintain.

Edited May 31, 2013 by ZRM

[earth]

So, what's up?

[ZRM]

So, what's up?

Things I have implemented in the new system:

• Robust initialisation and ModuleRCS migration (so there should be no more FX glitches).
  
• Vessel command negotiation. This means that if a vessel has multiple parts that want to impose CRCS control on the system (e.g. on a vessel that is actually two docked vessels) the CRCS module that is given control over the entire vessel is determined cleanly so that modules do not conflict.
  
• Multithreading support to offload solver calculation to another thread which updates separate from the main thread. So the update rate is independent from the frame rate.
  
• Modular control mode management system. This allows me to add new ways of controlling the vessel (such as VTOL mode, shuttle guidance etc.) easily. It also manages settings persistence of all control modes and provides a GUI environment for each mode so you can access its individual settings.
  
• An example control mode that behaves like stock RCS control. However this version also allows you to change the RCS strength (for delicate maneuvering and saving fuel) and disable RCS rotation control (this is very useful when ASAS is enabled when docking).
  

What I am working on currently:

The new thrust solver. This is the solver that will be used for RCS balancing (useful for docking) and no-gimbal engine balancing (useful for VTOLs and STS-style vehicles). It uses a modified Simplex method that determines the maximum directional thrust of the system automatically. This means that you no longer need to manually tune the solver. It will always find a solution. Also, because it is a purely linear solver, it is 100% accurate¹, so no accuracy setting is required either.

Things I plan to do next for the next release:

• Add an RCS mode and engine-balancing mode using the new solver.
  
• Add accurate Inertia Tensor calculations.
  

Things I plan to work on in the immediate future after the release:

• Implement a nonlinear solver with nonlinear constraints that can solve QCQP problems efficiently. This will be used to balance vessels with engine gimballing, which requires a quadratic solver that handles quadratic constraints. Once this solver is implemented, the full range of VTOLs with gimballing/rotating engines will be supported.
  
• VTOL guidance - An ascent, landing and maneuvering computer for VTOLs.
  

[1] Well, as accurate as floating point calculations can be.

Edited June 12, 2013 by ZRM

[afranius]

Implement a nonlinear solver with nonlinear constraints that can solve QCQP problems efficiently. This will be used to balance vessels with engine gimballing, which requires a quadratic solver that handles quadratic constraints.

Just came here from my thread where you linked this, I guess you had the same idea about CP-based balancing

Instead of QCQP, why don't you use polygonal cone approximations (instead of a cone, use an n-sided polygonal pyramid basis with non-negative coefficients)? These are very commonly used in simulating frictional contacts, and they usually work well and keep the problem linear. That might make your life easier.

[ZRM]

Just came here from my thread where you linked this, I guess you had the same idea about CP-based balancing

Instead of QCQP, why don't you use polygonal cone approximations (instead of a cone, use an n-sided polygonal pyramid basis with non-negative coefficients)? These are very commonly used in simulating frictional contacts, and they usually work well and keep the problem linear. That might make your life easier.

I had thought about this (though I think you would need to approximate it with a pyramid that has a subdivided curved base, not just an n-sided pyramid). I wasn't sure whether it would be too costly (both in terms of modelling and computation) to be worth it compared to some of the good non-linear constrained optimisation algorithms out there.

Anyway, engine gimballing doesn't fit a cone. Instead it's the spherically-bounded square frustum defined by the set of directions reached by rotating about the X axis by at most the gimbal limit then the same for the Y axis (Z is the starting direction).

Edited June 12, 2013 by ZRM