B-1 landing without nose landing gear

Cool video of a B-1 landing at Edwards AFB with failed landing gear. Great landing job.

Posted in Aerospace | Tagged | Leave a comment

A* Algorithm in Swift

As an exercise in learning, I set out to develop the A* algorithm, described here, in Swift. Swift is a strongly typed, dynamic programming language developed by Apple, and available on Linux and all Apple operating systems. It is an open source project managed  by swift.org.

My AStar project is also an open source project on my GitHub account available here (including source, unit tests and Xcode project files). 

The A* algorithm is an enhancement of Dijkstra’s algorithm for pathfinding and graph traversal, in that it uses heuristics to help finding the best path. In my implementation, I created three classes: Node, Path and SearchManager.

Node

A Node describes a node on the graph or map. It has a reference to the previous Node, an array of Paths that originate at that Node, along with the cost to travel from the start Node to reach that Node, and the assumed cost from start to end passing through that Node. The total distance includes the actual distance from the start, and the heuristic to the end.

In most cases, a user of this implementation will need to subclass Node to provide application specific details of a Node. One of those is to implement an appropriate heuristic. This algorithm sets the heuristic to 0, meaning it is not used, so it acts like Dijkstra’s algorithm.

//

//  Node.swift

//  AStar

//

//  Created by John Ahrens on 5/22/16.

//  Copyright © 2016 John Ahrens. All rights reserved.

//

 

import Foundation

 

/**

 * Node represents a point on a path. It is an end point that has one or more paths connected to it. Start and End are 

 * nodes, as are any points that you may pass through in between.

 *

 * In a real application, this class will need to be sub-classed to provide the means of handling application unique 

 * features of the Node. One such feature is the means of calculating the heuristic cost to get to the end point.

 */

class Node

{

    var paths:Array<Path>? /// Paths define the connections between two nodes

    var cameFrom: Node? /// The last Node accessed before arriving at this Node.

    var gScore: Double/// The distance from start to this Node

    var fScore: Double/// The distance from start to end, passing through this node

    var heuristic: Double/// This value defaults to 0, but should be overridden by a child class to do something interesting

    

    init()

    {

        self.paths = Array<Path>()

        self.cameFrom = nil

        self.gScore = DBL_MAX

        self.fScore = DBL_MAX

        self.heuristic = 0.0

    }

    

    init(withPaths paths:Array<Path>)

    {

        self.paths = paths

        self.cameFrom = nil

        self.gScore = DBL_MAX

        self.fScore = DBL_MAX

        self.heuristic = 0.0

    }

}

Path

A Path contains two nodes that are adjacent by virtue of our being able to travel from one to another directly without passing through any other Nodes. The other element of the Path is the cost of going between the two Nodes. Note that if you can go both directions between the Nodes, you need to create two Paths, one having the Nodes reversed from the other Node.

//

//  Path.swift

//  AStar

//

//  Created by John Ahrens on 5/22/16.

//  Copyright © 2016 John Ahrens. All rights reserved.

//

 

import Foundation

 

/**

 * A path exists between two points. Both Nodes are listed here as node1 and node2

 */

class Path

{

    var node1: Node? /// Starting Node for a path

    var node2: Node? /// Ending Node for the path

    var cost: Double/// The cost of traversing from node1 to node2

    

    init()

    {

        node1 = nil

        node2 = nil

        cost = 0.0

    }

    

    init(withNode1 node1:Node, node2:Node, cost:Double)

    {

        self.node1 = node1

        self.node2 = node2

        self.cost = cost

    }

}

SearchManager

//

//  SearchManager.swift

//  AStar

//

//  Created by John Ahrens on 5/22/16.

//  Copyright © 2016 John Ahrens. All rights reserved.

//

 

import Foundation

 

/**

 * SearchManager is a controller object in the Model/View/Controller sense of things. It does the work of finding the 

 * path to the end point.

 */

class SearchManager

{

    var closedSet: Array<Node> /// Set of nodes already evaluated

    var openSet: Array<Node> /// Set of nodes still to be evaluated. Initially only the starting point

    var start: Node

    var end: Node

init

The SearchManager class is the controller of all the action, where all the magic happens. After creating all the Nodes and Paths and assigning the Paths to the appropriate Nodes, initialize a SearchManager with the start and end Nodes. The start Node should have the gScore set to zero, since the cost of going from start to start is 0.

    init(withStart start: Node, end: Node)

    {

        closedSet = Array<Node>()

        openSet = Array<Node>(arrayLiteral: start)

        self.start = start

        self.end = end

    }


Note that after initialization, the openSet (known Nodes that have not yet been analyzed) contains only the start Node, and the closedSet (known Nodes that have already been analyzed) is empty.

findPath

After initialization, call the findPath method and evaluate the response. It returns true if it finds a path from start to end, and returns false if no path is available. 

  • While the openSet is not empty
    • Remove the last Node of the openSet as the current Node
    • if the current Node is the end Node
      • return true, you’ve found the optimal path
    • add the current Node to the closedSet
    • for each Path in the current Node
      • Take the node2 Node as the next Node
      • if the next Node is part of the closedSet
        • go on, it’s already been evaluated
      • compute the cost from the start Node to the next Node 
      • if the next Node is not part of the openSet
        • add the next Node to the openSet, you’ve found a new Node
      • otherwise if the cost is greater than or equal to the gScore of the next Node
        • go on, it is not a good path
      • At this point, you’ve found a candidate for a Node on the optimal path, add it
  • If you run out of Nodes and have not reached the end Node, return false

    func findPath() -> Bool

    {

        var current = Node()

        start.fScore = start.heuristic

        while (0 < openSet.count)

        {

            current = openSet.popLast()!

            if current === end

            {

                returntrue

            }

            

            closedSet.append(current)

            for path in current.paths!

            {

                let nextNode = path.node2

                ifclosedSet.contains({$0 === nextNode})

                {

                    // This node has already been evaluated.

                    continue

                }

                

                let cost = current.gScore + path.cost

                if !openSet.contains({$0 === nextNode})

                {

                    // Found a new node

                    openSet.append(nextNode!)

                }

                elseif cost >= nextNode!.gScore

                {

                    // not a good node

                    continue

                }

                

                // The current best node, add it.

                nextNode!.cameFrom = current

                nextNode!.gScore = current.gScore + path.cost

                nextNode!.fScore = (nextNode?.gScore)! + (nextNode?.heuristic)!

                openSet.sortInPlace {

                    $0.fScore > $1.fScore

                }

            }

        }

        

        returnfalse

    }


recreatePath

After getting a successful path, recreate the path through all the nodes by backtracking from the end Node, through the cameFrom members to the start Node, then returning an Array of Nodes in order. This method uses recursion to accomplish that task.

    func recreatePath(fromNode: Node) -> Array<Node>

    {

        var pathToEnd: Array<Node> = []

        if fromNode !== start

        {

            pathToEnd = recreatePath(fromNode.cameFrom!)

        }

        

        pathToEnd.append(fromNode)

        return pathToEnd

    }

}

 

Tests

The framework includes a set of UnitTests. I am using only one here as an example of how I anticipate using the framework.

  1. Initialize the start Node and set the gScore to 0 (cost of going from start to start)
  2. Create Node adjacent to start Node 
  3. Create Path from start Node to adjacent Node
  4. Add Path to start Node
  5. Create Path from adjacent Node to start Node
  6. add Path to adjacent Node
  7. Create next Node adjacent to start Node
  8. Repeat steps 3 through 6 for Node created in step 7
  9. Create end Node
  10. Repeat steps 3 through 6 for step 2 Node and end Node
  11. Repeat steps 3 through 6 for step 7 Node and end Node
  12. Initialize SearchManager with start and end Nodes
  13. call searchManager.findPath()
  14. If it returns true call searchManager.recreatePath() 

    /**

     * Tests the case with two possible paths. The shortest first leg leads to the shortest path.

     * Diagram looks like: Start*—+A

     *                           \   \

     *                           B+—*End

     */

    func testTwoPathsTwoIntermediateNodesShortestFirstLegShortestPath() {

        let start = Node()

        start.gScore = 0.0

        let nodeA = Node()

        let startPathA = Path(withNode1: start, node2: nodeA, cost: 1.0)

        start.paths?.append(startPathA)

        let pathAStart = Path(withNode1: nodeA, node2: start, cost: 1.0)

        nodeA.paths?.append(pathAStart)

        let nodeB = Node()

        let startPathB = Path(withNode1: start, node2: nodeB, cost: 1.5)

        start.paths?.append(startPathB)

        let pathBStart = Path(withNode1: nodeB, node2: start, cost: 1.5)

        nodeB.paths?.append(pathBStart)

        let end = Node()

        let pathAEnd = Path(withNode1: nodeA, node2: end, cost: 1.5)

        nodeA.paths?.append(pathAEnd)

        let endPathA = Path(withNode1: end, node2: nodeA, cost: 1.5)

        end.paths?.append(endPathA)

        let pathBEnd = Path(withNode1: nodeB, node2: end, cost: 1.5)

        nodeB.paths?.append(pathBEnd)

        let endPathB = Path(withNode1: end, node2: nodeB, cost: 1.5)

        end.paths?.append(endPathB)

        let searchManager = SearchManager(withStart: start, end: end)

        

        XCTAssertTrue(searchManager.findPath())

        let totalPath = searchManager.recreatePath(end)

        

        XCTAssertEqual(3, totalPath.count)

        XCTAssertTrue(totalPath[0] === start)

        XCTAssertTrue(totalPath[1] === nodeA)

        XCTAssertTrue(totalPath[2] === end)

    }


Posted in Swift | Tagged , , | 5 Comments

First 3D printed object made from metal from an asteroid

Planetary Resources announced the first 3D printed object made from the metal from an asteroid.

This is really cool on a number of levels. 3D printing using space resources is where we are going, especially with space applications.

Posted in Commercial Space | Tagged , , , | Comments Off on First 3D printed object made from metal from an asteroid

Pluto and Charon Dance

A cool movie of Pluto and Charon in motion, as taken from the New Horizons spacecraft.

Posted in NASA | Tagged , , | Comments Off on Pluto and Charon Dance

On Competition

The Russians have endemic problems in all their industries, but the most visible outside of Russia is the Space agency problems. Their solution? Combine all the companies into one and put them under government control. Will that solve the problem. Maybe some, for a short time. But the lack of competition means that they will quickly become outdated and too expensive as competition in the rest of the world surges ahead.

Now think how these same lessons may apply in our medical industry here in the United States. It explains why, under Obamacare costs are going up and care is going down.

Posted in Economics | Tagged , , | Comments Off on On Competition

The worst nutrition advice ever

A look at five pieces of nutritional advice that have been killing us.

Posted in Uncategorized | Tagged , | Comments Off on The worst nutrition advice ever

Centimeter Accuracy GPS

It appears that a student team has made a breakthrough that allows low-cost antennas to achieve centimeter accuracy positioning. This will mean a lot for all sorts of applications that need this accuracy. As noted in a comment to the referring article, Armadillo Aerospace and Unreasonable Rocket had huge difficulties achieving this level of accuracy. Now it’s available off the shelf (or at least soon). 

Posted in Engineering | Tagged , | Comments Off on Centimeter Accuracy GPS

The Dragon Flew

SpaceX had a successful Pad Abort test this morning. This test demonstrates the capability of the Dragon 2 spacecraft to escape from the rocket launcher and carry the crew to safety in the event of a failure of the rocket on the launch pad.

 

Update:

Robert Zimmerman has a short report.

This is what Michael Belfiore has to say.

Posted in Commercial Space, NASA | Tagged , , , , | Comments Off on The Dragon Flew

The Space Week in Review

In the Space Review this week, Jeff Foust takes a look at the status of the accident investigations into the Antares and Space Ship 2 accidents last fall. Six months down the road, both companies are well on the way to return to flight with fixes for the problems so far identified.

Also, R.D. Boozer compares the SpaceX Dragon v.2 capsule with the NASA Orion capsule, both of which, are about to perform pad abort tests. The comparison favors the Dragon, which makes sense, particularly when you consider that it can do pretty much everything that Orion can do at almost one-tenth the cost to the taxpayers for development.

Posted in Commercial Space, NASA | Tagged , , , , | Comments Off on The Space Week in Review

The Merlin 1D Rocket engine

Build for human Spaceflight.

Hat tip: Rand Simberg.

Posted in Commercial Space | Tagged , , | Comments Off on The Merlin 1D Rocket engine