Golang implementation of the Optimal Reciprocal Collision Avoidance (ORCA)
This project is under active development and is not yet feature complete, and
may contain bugs. We welcome contributions in the form of new issues and pull
ORCA is useful for local collision avoidance in large systems. The current
“canonical” implementation lacks documentation, and is rather opaque.
go-orca aims to be a re-implementation of the ORCA algorithm with better
documentation and API.
More prosaic documentation of this library will be made available at
go get -u ./... go mod tidy
Here, we have 250 agents of random size and speeds travelling in 2D ambient
space to some random nearby destination. Green circles indicate agent vision
radius, whereas an agent (in black) flashing red indicates the velocity has
changed due to ORCA.
N.B.: WSL does not profile correctly. See
go test -v github.com/downflux/go-orca/... -bench . -benchmem -cpu 1,2,4,8,16,32,64 go test -v github.com/downflux/go-orca/orca -bench BenchmarkStep/N=1000000 -benchmem -cpuprofile cpu.out -memprofile mem.out go tool pprof -tree -nodecount=10 cpu.out
See pprof for more
go test github.com/downflux/go-orca/orca -bench . goos: linux goarch: amd64 pkg: github.com/downflux/go-orca/orca cpu: Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz BenchmarkStep/N=1-8 965041 1229 ns/op BenchmarkStep/N=10-8 69074 18382 ns/op BenchmarkStep/N=100-8 4786 260644 ns/op BenchmarkStep/N=1000-8 373 3262935 ns/op BenchmarkStep/N=10000-8 28 41041814 ns/op BenchmarkStep/N=100000-8 3 518004500 ns/op BenchmarkStep/N=1000000-8 1 5991109700 ns/op PASS ok github.com/downflux/go-orca/orca 38.640s
We have not yet implemented generating velocity objects for polygonal obstacles.
The current implementation only adjusts trajectory for other circular agents.
Performance metrics shoud be compared against Granberg, Snape et al.,
and van den Berg et al.. We estimate that there is about another 50%
optimization achievable in the current implementation of the ORCA algorithm.